hdu4578线段树区间更新

/* 只有在区间中的数字不相同时才pushdown：往子区间传递数字再到子区间更新，同时该区间的flag置0 更新完左右子区间后进行pushup，如果左右子区间数字相同，那么把子区间合并，子区间数字置0 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define ll long long #define mod 10007 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 200000 int n,q,flag[maxn<<2],x[maxn<<2]; inline void pushup(int rt){ if(!flag[rt<<1] || !flag[rt<<1|1]) flag[rt]=0; else if(x[rt<<1]!=x[rt<<1|1]) flag[rt]=0; else flag[rt]=1,x[rt]=x[rt<<1]; } inline void pushdown(int rt){ if(flag[rt]){ flag[rt<<1]=flag[rt<<1|1]=1; x[rt<<1]=x[rt]; x[rt<<1|1]=x[rt]; flag[rt]=0; } } void update(int L,int R,int op,int val,int l,int r,int rt){ if(L<=l && R>=r && flag[rt]){ if(op==1) x[rt]=(x[rt]+val)%mod; else if(op==2) x[rt]=x[rt]*val%mod; else x[rt]=val; return; } pushdown(rt); int m=l+r>>1; if(L<=m) update(L,R,op,val,lson); if(R>m) update(L,R,op,val,rson); pushup(rt); } ll query(int L,int R,int val,int l,int r,int rt){ if(L<=l && R>=r && flag[rt]){ ll ans=1; for(int i=1;i<=val;i++) ans=(ans*x[rt])%mod; ans=(ans*(r-l+1))%mod; return ans; } pushdown(rt); int m=l+r>>1; ll ans=0; if(L<=m) ans+=query(L,R,val,lson); if(R>m) ans+=query(L,R,val,rson); return ans%mod; } int main(){ while(scanf("%d%d",&n,&q),n){ memset(flag,1,sizeof flag); memset(x,0,sizeof x); int op,L,R,val; while(q--){ scanf("%d%d%d%d",&op,&L,&R,&val); if(op<=3 && op>=1) update(L,R,op,val,1,n,1); else printf("%lld\n",query(L,R,val,1,n,1)); } } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/9958450.html