题解 P1438 【无聊的数列】

· · 题解

发现题解中全都用差分的,只有一个不是 (居然撞思路了
但他没有仔细讲他的思路,与思考过程,那我就为他补充一下吧

遇到这种题型不用慌,要不是差分,要不就是拆,也可以称为分离常数,我们假设原数列中有一个数a[i],我们再[l,r](i属于[l,r])中加了一个首项为k,公差为d的数列,那么我们易知

a[i]=a[i]+k+(i-l)*d

继续化简得

a[i]=a[i]+k-d*l+i*d=a[i]+(k-d*l)+i*d

我们发现 对于括号中的部分 与这个数所在的位置无关,也就意味着可以将这个区间直接加上这个数,而对于另一部分,我们把i与d拆开,用另一个线段树维护d,因为是单点查询,我们只要将维护的d[i]乘上当前位置i,再加上第一个维护的线段树的查询结果就可以了
为了方便我写了一个模板，避免了写两棵线段树

Code 
#include<cstdio>
#include<cstring>

template<typename T>
inline T read(T& a) {
    int c,f=1;  a=0;
    while((c=getchar()))  {
        if(c=='-') f=-1;
        if(c>='0'&&c<='9') break;
    }
    do {
        a=a*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return a*=f;
}

const int maxn = 100000 + 5;

class Tree {
    public:
    int s[maxn<<2],add[maxn<<2];

    inline int lc(int o) { return o<<1; }
    inline int rc(int o) { return (o<<1)|1; }

    inline void clear() { memset(s,0,sizeof s); memset(add,0,sizeof add); }

    int build(int o,int L,int R) {
        add[o]=0;
        if(L==R) return read(s[o]);
        int mid=(L+R)>>1;
        return s[o]=build(lc(o),L,mid)+build(rc(o),mid+1,R);
    }

    inline void change(int o,int L,int R,int _add) {
        s[o]+=(R-L+1)*_add; add[o]+=_add;
    }

    inline void pushdown(int o,int L,int R) {
        if(!add[o]) return ;
        int mid=(L+R)>>1;
        change(lc(o),L,mid,add[o]); change(rc(o),mid+1,R,add[o]);
        add[o]=0;
    }

    void updata(int o,int L,int R,int l,int r,int _add) {
        if(l<=L&&r>=R) return change(o,L,R,_add);
        pushdown(o,L,R);
        int mid=(L+R)>>1;
        if(l<=mid) updata(lc(o),L,mid,l,r,_add);
        if(r>mid) updata(rc(o),mid+1,R,l,r,_add);
        s[o]=s[lc(o)]+s[rc(o)];
    }

    int query(int o,int L,int R,int x) {
        if(L==R) return s[o];
        pushdown(o,L,R);
        int mid=(L+R)>>1;
        if(x<=mid) return query(lc(o),L,mid,x);
        return query(rc(o),mid+1,R,x);
    }

};

int n,m;
Tree t1,t2;

int main() {
    register int c,l,r,k,d;
    read(n); read(m);
    t1.build(1,1,n); t2.clear();
    while(m--) {
        read(c); read(l);
        if(c==1) {
            read(r); read(k); read(d);
            t1.updata(1,1,n,l,r,k-l*d);
            t2.updata(1,1,n,l,r,d);
        }
        else printf("%d\n",t1.query(1,1,n,l)+t2.query(1,1,n,l)*l);
    }
    return 0;
}

我们发现只需要会线段树的基本操作，并不需要维护两个标记,代码还简短,思路又简单 (只是跑得没树状数组快
有了这个思想你就可以用两颗树状数组维护区间修改+区间查询了
赶快动手吧，这儿有一道用到这个思想的例题