[区区区间] 题解

前言

不难的线段树题，散发着一股浓浓的套路的味道。

题目分析

首先可以知道 ”我们小学二年级就学过的“ 等差序列求和公式（这个真的是小学二年级的 (doge

然后对于本题的操作一进行分析：

• 不妨假设修改的区间为:

• 倘若这个区间包含了一个线段树节点 , 这个节点的区间左端点为 , 区间右端点为 ,

• 那么节点 的区间和就是

(首项 加 末项) * 项数 / 2

这个公式我们耳熟能详

• 这里的 首项 就是 , 末项 就是 ，项数 就是 。

• 整理一下就是 :

那么很明显，我们需要记录每次修改的区间左端点 以及给定的 , 于是我们在线段树的懒标记中开两个数组分别记录每次修改给定的 以及区间左端点即可。然后在每次进行修改操作之前都下传标记即可。

想必操作二应该就不用细说了吧，应该都会，吧？

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((L[x] + R[x]) >> 1)
inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

typedef long long LL;
const int MAXN = 2e5 + 50; 
int n, Q; // n 表示序列长度，Q 表示询问 和 修改的次数
int A[MAXN]; // 原始数列

struct SegmentTree {
    int L[MAXN << 2], R[MAXN << 2],laz[MAXN << 2], tl[MAXN << 2];//laz 记录的是修改的 k,tl 表示修改的左端点
    LL sum[MAXN << 2];

    void update(int x) {sum[x] = sum[x << 1] + sum[x << 1 | 1];}

    void build(int x, int l, int r) {
        L[x] = l, R[x] = r; laz[x] = 0;
        if(l == r) {sum[x] = A[l]; return ;}
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1 , r);
        update(x);
        return ;
    }

    void ad(int x, int k ,int l) { // k 如题意所述，x 表示修改的线段树节点编号，l 表示修改的左端点
        int len = R[x] - L[x] + 1;//区间长度
        sum[x] = (LL)len * (LL)(L[x] + R[x] + 2 * (k - l)) / 2; //等差序列求和公式求出区间和
        laz[x] = k, tl[x] = l; // 懒标记记录
        return ;
    }

    void pushdown(int x) {
        if(!laz[x]) return ;
        ad(x << 1, laz[x], tl[x]);
        ad(x << 1 | 1, laz[x], tl[x]);
        laz[x] = 0, tl[x] = 0; //两个都要清空，注意一下
        return ;
    }

    void change(int x, int l, int r, int k) {
        if(L[x] >= l && R[x] <= r) {
            ad(x, k, l); 
            return ;
        }
        pushdown(x);
        if(l <= mid) change(x << 1, l, r, k);
        if(r  > mid) change(x << 1 | 1, l, r, k);
        update(x);
        return ;
    }

    LL GetSum(int x, int l, int r) { //常规区间求和即可
        LL S = 0;
        if(L[x] >= l && R[x] <= r) return sum[x];
        pushdown(x);
        if(l <= mid) S += GetSum(x << 1, l, r);
        if(r  > mid) S += GetSum(x << 1 | 1, l, r);
        return S;
    }

} T;

signed main() {
    n = read(), Q = read();
    for(int i = 1 ; i <= n ; i ++) A[i] = read();
    T.build(1, 1, n);
    while(Q --) {
        int op = read(),l = read(), r = read();
        if(op == 1) T.change(1, l, r, read());
        else printf("%lld\n", T.GetSum(1, l, r));
    }
    return 0;
}