HDU4578(Transformation)

链接：https://vjudge.net/problem/HDU-4578
思路：之前做过一个平方的，这次多了一个立方，操作一样不过立方要比平方先更新，平方比和先更新，最后更新tag，然后惯例的先更新乘法后更新加法，然后注意变数时不能直接更新到节点否则会超时，这时候先用一个清空标记记录要变的值，push下去时清空下面的加法和乘法标记同时将清空标记传下去，随后再更新加法和乘法标记，注意因为取模不要爆范围，中间一直因为爆范围导致WA。。。。。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+100  ;
long long tagp[maxn<<2],tagm[maxn<<2],clear[maxn<<2];
long long sum[maxn<<2],dou[maxn<<2],tri[maxn<<2];
int n,q;
const int mod = 10007;

inline void pushup(int o){
  sum[o] = (sum[o<<1] + sum[o<<1|1])%mod;
  dou[o] = (dou[o<<1] + dou[o<<1|1])%mod;
  tri[o] = (tri[o<<1] + tri[o<<1|1])%mod;
}

void pushdown(int o,int m){
  if(clear[o]!=-1){
      sum[o<<1] = (m-(m>>1))*clear[o]%mod;
      sum[o<<1|1] = ((m>>1))*clear[o]%mod;
      dou[o<<1] = (m-(m>>1))*clear[o]%mod*clear[o]%mod;
      dou[o<<1|1] = ((m>>1))*clear[o]%mod*clear[o]%mod;
      tri[o<<1] = (m-(m>>1))*clear[o]%mod*clear[o]%mod*clear[o]%mod;
      tri[o<<1|1] = ((m>>1))*clear[o]%mod*clear[o]%mod*clear[o]%mod;
      clear[o<<1] = clear[o<<1|1] = clear[o];
      tagp[o<<1] = tagp[o<<1|1] = 0;
      tagm[o<<1] = tagm[o<<1|1] = 1;
      clear[o] = -1; 
  }
  if(tagm[o]!=1){
    sum[o<<1] = sum[o<<1]*tagm[o]%mod;
    sum[o<<1|1]=sum[o<<1|1]*tagm[o]%mod;
    dou[o<<1]=dou[o<<1]*tagm[o]%mod*tagm[o]%mod;
    dou[o<<1|1] =dou[o<<1|1] * tagm[o]%mod*tagm[o]%mod;
    tri[o<<1] = tri[o<<1] *tagm[o]%mod*tagm[o]%mod*tagm[o]%mod;
    tri[o<<1|1]=tri[o<<1|1]*tagm[o]%mod*tagm[o]%mod*tagm[o]%mod;
    tagm[o<<1] = tagm[o<<1] *tagm[o]%mod;
    tagm[o<<1|1] =tagm[o<<1|1] * tagm[o]%mod;
    tagp[o<<1] = tagp[o<<1] * tagm[o]%mod;
    tagp[o<<1|1] = tagp[o<<1|1] *tagm[o]%mod;
    tagm[o] = 1;
  }
  if(tagp[o]){
      tri[o<<1] = (tri[o<<1] + 3*dou[o<<1]*tagp[o]%mod+3*sum[o<<1]*tagp[o]%mod*tagp[o]%mod+tagp[o]*tagp[o]%mod*tagp[o]%mod*(m-(m>>1)))%mod;
      tri[o<<1|1]= (tri[o<<1|1] + 3*dou[o<<1|1]*tagp[o]%mod+3*sum[o<<1|1]*tagp[o]%mod*tagp[o]%mod+tagp[o]*tagp[o]%mod*tagp[o]%mod*(m>>1))%mod;
      dou[o<<1]= (dou[o<<1] + 2*sum[o<<1]*tagp[o]%mod + tagp[o]*tagp[o]%mod*(m-(m>>1)))%mod;
      dou[o<<1|1] = (dou[o<<1|1] + 2*sum[o<<1|1]*tagp[o]%mod +tagp[o] *tagp[o]%mod*(m>>1))%mod;
      sum[o<<1] = (sum[o<<1] + tagp[o]*(m-(m>>1)))%mod;
      sum[o<<1|1] = (sum[o<<1|1] + tagp[o]*(m>>1))%mod;
      tagp[o<<1] = (tagp[o<<1] + tagp[o])%mod;
      tagp[o<<1|1] = (tagp[o<<1|1] + tagp[o])%mod;
      tagp[o] = 0;
   }
}

void build(int o,int l,int r){
    tagp[o] = 0;
    tagm[o] = 1;
    sum[o] = 0;
    dou[o] = 0;
    tri[o] = 0;
    clear[o] = -1;
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
  }
}

void updatesum(int o,int tl,int tr,int l,int r,int v){
  if(tr<l||r<tl)return;
  if(l<=tl&&tr<=r){
    tagp[o] = (tagp[o] + v)%mod;
    tri[o] = (tri[o] + 3*dou[o]*v%mod +3*sum[o]*v%mod*v%mod+(tr-tl+1)*v%mod*v%mod*v%mod)%mod; 
    dou[o] = (dou[o] + 2*sum[o]*v%mod+(tr-tl+1)*v%mod*v%mod)%mod;
    sum[o] = (sum[o] + (tr-tl+1)*v%mod)%mod;
        return;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  updatesum(o<<1,tl,mid,l,r,v);
  updatesum(o<<1|1,mid+1,tr,l,r,v);
  pushup(o);
} 

void updatemul(int o,int tl,int tr,int l,int r,int v){
  if(tr<l||r<tl)return;
  if(l<=tl&&tr<=r){
    tagm[o] = (tagm[o]*v)%mod;
    tagp[o] = (tagp[o]*v)%mod;
    tri[o] = (tri[o]*v)%mod*v%mod*v%mod; 
    dou[o] = (dou[o]*v%mod*v)%mod;
    sum[o] = sum[o]*v%mod;
        return;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  updatemul(o<<1,tl,mid,l,r,v);
  updatemul(o<<1|1,mid+1,tr,l,r,v);
  pushup(o);
} 

void updatecha(int o,int tl,int tr,int l,int r,int v){
  if(tr<l||r<tl)return;
  if(l<=tl&&tr<=r){
    tri[o] = v*v%mod*v%mod*(tr-tl+1)%mod; 
    dou[o] = (tr-tl+1)*v%mod*v%mod;
    sum[o] = (tr-tl+1)*v%mod;
    tagp[o] = 0;
    tagm[o] = 1;
    clear[o] = v; 
    return;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  updatecha(o<<1,tl,mid,l,r,v);
  updatecha(o<<1|1,mid+1,tr,l,r,v);
  pushup(o);
} 

long long query(int o,int tl,int tr,int l,int r,int p){
  if(tr<l||r<tl)return 0;
  if(l<=tl&&tr<=r){
      if(p==1)
      return sum[o]%mod;
      if(p==2)
      return dou[o]%mod;
      if(p==3)
      return tri[o]%mod;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  long long ret = query(o<<1,tl,mid,l,r,p);
  ret+=query(o<<1|1,mid+1,tr,l,r,p);
  return ret%mod;
}

int main(){
    while(~scanf("%d%d",&n,&q)&&(n||q)){
        build(1,1,n);
        for(int i=0;i<q;i++){
            int c,x,y,p;
            scanf("%d%d%d%d",&c,&x,&y,&p);
            if(c==1){
                updatesum(1,1,n,x,y,p);
            }
            if(c==2)updatemul(1,1,n,x,y,p);
            if(c==3)updatecha(1,1,n,x,y,p);
            if(c==4)printf("%lld\n",query(1,1,n,x,y,p)%mod);
        }
    }
    return 0;
}