题解 P1438 【无聊的数列】

Adove · 2018-03-22 21:10:27 · 题解

这题先差分后区间修改查询会更方便（我才不会告诉你们我线段树区间加等差数列写残了呢）

标记永久化之后，这份代码应该算普通线段树里跑得相当快的了。

先差分，我们知道（就当作你知道）一阶等差数列差分后会得到常数数列，这样对整个序列差分后区间加就能满足需求了，根据前缀和与差分互为逆运算的性质，查询某个点之前序列前缀和即为答案。

这样问题就被转化为线段树的一般操作了。

上代码↓

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,p,l,r,x,y;
int a[1<<17],num[1<<18],add[1<<18];

void build(int k,int l,int r){
    if(l==r){
        num[k]=a[l];
        return;
    }int i=k<<1,mid=l+r>>1;
    build(i,l,mid);
    build(i|1,mid+1,r);
    num[k]=num[i]+num[i|1];
}

void cadd(int k,int l,int r,int le,int ri,int x){
    if(le<=l&&r<=ri){
        add[k]+=x;
        num[k]+=x*(r-l+1);
        return;
    }int i=k<<1,mid=l+r>>1;
    if(le<=mid) cadd(i,l,mid,le,ri,x);
    if(mid<ri) cadd(i|1,mid+1,r,le,ri,x);
    num[k]=num[i]+num[i|1]+add[k]*(r-l+1);
}

int ask(int k,int l,int r,int le,int ri,int x){
    if(le<=l&&r<=ri) return x*(r-l+1)+num[k];
    int i=k<<1,mid=l+r>>1;
    int sum=0;
    if(le<=mid) sum+=ask(i,l,mid,le,ri,x+add[k]);
    if(mid<ri) sum+=ask(i|1,mid+1,r,le,ri,x+add[k]);
    return sum;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }for(int i=n;i;--i){
        a[i]=a[i]-a[i-1];
    }build(1,1,n);
    while(m--){
        scanf("%d%d",&p,&l);
        if(p==1){
            scanf("%d%d%d",&r,&x,&y);
            cadd(1,1,n,l,l,x);
            if(l<r){
                cadd(1,1,n,l+1,r,y);
                if(r<n) cadd(1,1,n,r+1,r+1,-(x+y*(r-l)));
            }else if(l<n) cadd(1,1,n,l+1,l+1,-x);
        }else{
            printf("%d\n",ask(1,1,n,1,l,0));
        }
    }
    return 0;
}