HDU4578 Transformation 线段树

这个题让我重新学习了加 乘 在区间的操作

题解：http://blog.csdn.net/guognib/article/details/25324025?utm_source=tuicool&utm_medium=referral

代码：也是参考上面的写的

注：确实有优先级，加只影响自己，乘会影响加，重新设定值会清零所有的标记

      所以向下传的时候，乘和加的操作都晚于最后一次设定值，然后乘的操作要先于加

      所以要先传递set 然后是mul 然后是add

#include <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
const int mod=10007;
int q[3][N<<2],setval[N<<2],add[N<<2],mul[N<<2];
void pushup(int rt){
    for(int i=0;i<3;++i)
      q[i][rt]=(q[i][rt<<1]+q[i][rt<<1|1])%mod;  
}
void downset(int rt,int c,int len){
    int a[4];a[1]=c;
    for(int i=2;i<=3;++i)
      a[i]=a[i-1]*a[1]%mod;
    for(int i=0;i<3;++i)
     q[i][rt]=a[i+1]*len%mod;
    setval[rt]=c;
    add[rt]=0;
    mul[rt]=1;
}
void downadd(int rt,int c,int len){
    int a[4];a[1]=c;
    for(int i=2;i<=3;++i)
       a[i]=a[i-1]*a[1]%mod;
    q[2][rt]=q[2][rt]+a[3]*len%mod+3*a[2]%mod*q[0][rt]%mod+3*a[1]%mod*q[1][rt]%mod;   
    q[1][rt]=q[1][rt]+a[2]*len%mod+2*a[1]%mod*q[0][rt]%mod;
    q[0][rt]=q[0][rt]+a[1]*len%mod;
    for(int i=0;i<3;++i)q[i][rt]%=mod;
    add[rt]=(add[rt]+c)%mod;
}
void downmul(int rt,int c,int len){
   int a[4];a[1]=c;
   for(int i=2;i<=3;++i)
    a[i]=a[i-1]*a[1]%mod;
   for(int i=0;i<3;++i)
    q[i][rt]=(q[i][rt]*a[i+1])%mod;
   mul[rt]=(mul[rt]*c)%mod;
   add[rt]=(add[rt]*c)%mod; 
}
void down(int rt,int l,int r){
    int m=(l+r)>>1;
    if(setval[rt]!=-1){
        downset(rt<<1,setval[rt],m-l+1);
        downset(rt<<1|1,setval[rt],r-m);
        setval[rt]=-1;
    }
    if(mul[rt]!=1){
        downmul(rt<<1,mul[rt],m-l+1);
        downmul(rt<<1|1,mul[rt],r-m);
        mul[rt]=1;
    }
    if(add[rt]!=0){
        downadd(rt<<1,add[rt],m-l+1);
        downadd(rt<<1|1,add[rt],r-m);
        add[rt]=0;
    }
}
int op,c;
void modify(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        if(op==1)downadd(rt,c,r-l+1);
        else if(op==2)downmul(rt,c,r-l+1);
        else downset(rt,c,r-l+1);
        return;
    }
    int m=(l+r)>>1;
    down(rt,l,r);
    if(x<=m)modify(rt<<1,l,m,x,y);
    if(y>m)modify(rt<<1|1,m+1,r,x,y);
    pushup(rt);
}
int ask(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y)return q[c-1][rt];
    int ans=0,m=(l+r)>>1;
    down(rt,l,r);
    if(x<=m)ans=(ans+ask(rt<<1,l,m,x,y))%mod;
    if(y>m)ans=(ans+ask(rt<<1|1,m+1,r,x,y))%mod;
    return ans;
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(!n&&!m)break;
        for(int i=0;i<=4*n;++i){
            q[0][i]=q[1][i]=q[2][i]=add[i]=0;  
            mul[i]=1;
            setval[i]=-1;
        }
        while(m--){
            int x,y;
            scanf("%d%d%d%d",&op,&x,&y,&c);
            if(op<=3)modify(1,1,n,x,y);
            else printf("%d
",ask(1,1,n,x,y));
        }
    }
    return 0;
}