HDU-4578

给定一个长为 $n$ 的初始全为 $0$ 的序列 $a$ ，有以下四种操作：

1 x y c 表示将区间 $[x,y]$ 内的数都加 $c$ 。

2 x y c 表示将区间 $[x,y]$ 内的数都乘 $c$ 。

3 x y c 表示将区间 $[x,y]$ 内的数都赋成 $c$ 。

4 x y p 表示求 $\sum\limits_{i=x}^ya_i^p$ 。

思路

本题思维上很简单，就是写起来巨烦。

考虑写个线段树，维护区间一次方和 $sum1$ ，区间二次方和 $sum2$ ，区间三次方和 $sum3$ ，以及加延标记 $lp$ ，乘延迟标记 $lm$ ，覆盖延迟标记 $lc$ 。

一二三操作写起来都没啥问题，需要注意的是操作三覆盖后对应区间的标记要初始化。

本题的难点在于标记的下传。

操作三覆盖后标记要初始化，所以覆盖延迟标记的优先级最高，乘延迟标记优先级其次高，加延迟标记优先级最低。

对于二三次方，标记的下传和区间的修改根据 $(x+y)^2=x^2+2xy+y^2$ 与 $(x+y)^3=x^3+3x^2y+3xy^2+y^3$ 来写即可，一次方很简单，略。

例如区间 $[l,r]$ 加 $x$ ，对于单个的 $a_i$ 有 $(a_i+x)^2=a_i^2+2xa_i+x^2$ ， $(a_i+x)^3=a_i^3+3a_i^2x+3a_ix^2+x^3$ ，将所有操作后的 $a_i$ 累加起来即为 $sum2=sum2+2xsum1+(r-l+1)x^2$ ， $sum3=sum3+3xsum2+3x^2sum1+(r-l+1)x^3$ 。

据此写线段树即可。

代码

#include<bits/stdc++.h>
#define ll long long 
#define N 100010 
#define mod 10007

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;

ll val(int p,ll x) {
    ll val=1;
    for(int i=1;i<=p;i++) (val*=x)%=mod;
    return val;
}
class SegmentTree{
  private:
    ll sum[4][N<<2],lazy_plus[N<<2],lazy_mul[N<<2],lazy_cover[N<<2];
    #define s(i,p) sum[i][p]
    #define lp(p) lazy_plus[p]
    #define lm(p) lazy_mul[p]
    #define lc(p) lazy_cover[p]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        for(int i=1;i<=3;i++) s(i,p)=s(i,ls)+s(i,rs);
    }
    void plus(int p,int l,int r,ll x) {
        (s(3,p)+=3*s(2,p)*x%mod+3*s(1,p)*val(2,x)%mod+(r-l+1)*val(3,x))%=mod;
        (s(2,p)+=2*s(1,p)*x%mod+(r-l+1)*val(2,x)%mod)%=mod;
        (s(1,p)+=(r-l+1)*x)%=mod;
        (lp(p)+=x)%=mod;        
    }
    void mul(int p,int l,int r,ll x) {
        (s(3,p)*=val(3,x))%=mod;
        (s(2,p)*=val(2,x))%=mod;
        (s(1,p)*=val(1,x))%=mod;
        (lp(p)*=x)%=mod;
        (lm(p)*=x)%=mod;      
    }
    void cover(int p,int l,int r,ll x) {
        (s(3,p)=(r-l+1)*val(3,x))%=mod;
        (s(2,p)=(r-l+1)*val(2,x))%=mod;
        (s(1,p)=(r-l+1)*val(1,x))%=mod;
        lp(p)=0;
        lm(p)=1;
        lc(p)=x;
    }
    void spread(int p,int l,int r) {
        if(lc(p)!=-1) cover(ls,l,mid,lc(p)),cover(rs,mid+1,r,lc(p));
        if(lm(p)!=1) mul(ls,l,mid,lm(p)),mul(rs,mid+1,r,lm(p));
        if(lp(p)) plus(ls,l,mid,lp(p)),plus(rs,mid+1,r,lp(p));
        lc(p)=-1,lp(p)=0,lm(p)=1;
    }
  public:
    void build(int p,int l,int r) {
        for(int i=1;i<=3;i++) {
            s(i,p)=lp(p)=0;
            lm(p)=1;
            lc(p)=-1;
        }
        if(l==r) return ;
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void change_plus(int p,int l,int r,int L,int R,ll x) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            plus(p,l,r,x);
            return ;
        }
        spread(p,l,r);
        change_plus(ls,l,mid,L,R,x),change_plus(rs,mid+1,r,L,R,x);
        update(p);
    }
    void change_mul(int p,int l,int r,int L,int R,ll x) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            mul(p,l,r,x);
            return ;
        }
        spread(p,l,r);
        change_mul(ls,l,mid,L,R,x),change_mul(rs,mid+1,r,L,R,x);
        update(p);
    }
    void change_cover(int p,int l,int r,int L,int R,ll x) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            cover(p,l,r,x);
            return ;
        }
        spread(p,l,r);
        change_cover(ls,l,mid,L,R,x),change_cover(rs,mid+1,r,L,R,x);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R,int type) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(type,p);
        spread(p,l,r);
        return (ask(ls,l,mid,L,R,type)+ask(rs,mid+1,r,L,R,type))%mod;
    }
}SMT;

int main() {
    n=read(),m=read();
    while(n&&m) {
        SMT.build(1,1,n);
        for(int i=1;i<=m;i++) {
            int op=read(),l=read(),r=read();
            ll x=read();
            if(op==1) SMT.change_plus(1,1,n,l,r,x);
            if(op==2) SMT.change_mul(1,1,n,l,r,x);
            if(op==3) SMT.change_cover(1,1,n,l,r,x);
            if(op==4) printf("%lld\n",SMT.ask(1,1,n,l,r,x));
        }        
        n=read(),m=read();
    }
    system("pause");
    return 0;
}