题解 P1438 【无聊的数列】

· · 题解

线段树模板。

我们维护一个线段树的结点，包含一下信息：

  1. 区间和

  2. 区间等差数列的首项，公差。

没了。

然后我们每次在pushdown的时候，公差显然时不变的。

其次，对应的左儿子的首项也不变。

对应的右儿子首项为：首项+左儿子的长度*公差。

然后胡乱维护一下就好了...（写了10min一遍就A了。

#include <bits/stdc++.h>
#define ls(x) x << 1
#define rs(x) x << 1 | 1

using namespace std;

const int N = 100000 + 10;

int n , m , a[N];

struct Seg {
    int l , r , k , d , dis;
    Seg() {
        l = r = k = d = dis = 0;
    }
}t[N << 2];

int sum (int k , int d , int len) {
    int rsum = 0;
    rsum = len * k + d * len * (len - 1) / 2;
    return rsum;
}

void pushup(int x) {
    t[x].dis = t[ls(x)].dis + t[rs(x)].dis;
}

void built(int x , int l , int r) {
    t[x].l = l , t[x].r = r;
    if(l == r) {
        t[x].dis = a[l]; return;
    }
    int mid = (l + r ) >> 1;
    built(ls(x) , l , mid);
    built(rs(x) , mid + 1 , r);
    pushup(x);
}

void pushdown(int x) {
    t[ls(x)].d += t[x].d;
    t[rs(x)].d += t[x].d;
    t[ls(x)].k += t[x].k;
    t[rs(x)].k += t[x].k + (t[ls(x)].r - t[ls(x)].l + 1) * t[x].d;
    t[ls(x)].dis += sum(t[x].k , t[x].d , t[ls(x)].r - t[ls(x)].l + 1);
    t[rs(x)].dis += sum(t[x].k + (t[ls(x)].r - t[ls(x)].l + 1) * t[x].d , t[x].d , t[rs(x)].r - t[rs(x)].l + 1); 
    t[x].d = t[x].k = 0;
}

void updata(int x , int l , int r , int k , int d) {    

    if(t[x].l >= l && t[x].r <= r) {
        t[x].d += d; 
        int kk = (t[x].l - l) * d + k;
        t[x].k += kk;
        t[x].dis += sum(kk , d , t[x].r - t[x].l + 1);      
        return;
    }
    pushdown(x);
    int mid = (t[x].l + t[x].r) >> 1;
    if(l <= mid) updata(ls(x) , l , r , k , d);
    if(r > mid ) updata(rs(x) , l , r , k , d);
    pushup(x);
}

int query(int x , int p) {
    if(t[x].l == t[x].r) {
        return t[x].dis;
    }
    pushdown(x);
    int mid = (t[x].l + t[x].r) >> 1;
    int ans = 0;
    if(p <= mid) ans =  query(ls(x) , p);
    else ans = query(rs(x) , p);
    pushup(x);
    return ans;
}

int main () {
    scanf("%d %d" , &n , &m);
    for(int i = 1 ; i <= n ; ++ i) scanf("%d" , a + i);
    built(1 , 1 , n);
    while(m -- ) {
        int opt; scanf("%d" , &opt);
        if(opt == 1) {
            int l , r , k , d;
            scanf("%d %d %d %d" , &l , &r , &k , &d);
            updata(1 , l , r , k , d);
        } else {
            int p; scanf("%d" , &p);
            printf("%d\n" , query(1 , p));
        }
    }
    return 0;
}