题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4578
多种操作,都是对区间的操作,
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> using namespace std; #define mode 10007 #define maxn 100010 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int n,m; int col[maxn<<2]; int val[maxn<<2]; int power(int a,int p){ if(p == 1) return a%mode; else if(p == 2) return (a%mode*a)%mode; else return ((a*a)%mode*a)%mode; } void PushUp(int rt){ if((col[rt<<1]) && (col[rt<<1|1]) && (val[rt<<1] == val[rt<<1|1])){ col[rt] = 1; val[rt] = val[rt<<1]; } } void Pushdown(int rt){ if(col[rt]){ col[rt<<1] = col[rt<<1|1] = 1; val[rt<<1] = val[rt<<1|1] = val[rt]; col[rt] = 0; } } void update(int L,int R,int c,int op,int l,int r,int rt){ if(op == 1 && col[rt] && L <= l && r <= R){ val[rt] =(val[rt] + c) % mode; return ; } if(op == 2 && col[rt] &&L <= l && r <= R){ val[rt] =(val[rt] * c) % mode; return ; } if(op == 3&& L <= l && r <= R){ col[rt] = 1; val[rt] = c%mode; return; } //return ; Pushdown(rt); int m = (l + r) /2; if(L <= m) update(L,R,c,op,lson); if(m < R) update(L,R,c,op,rson); PushUp(rt); } int query(int L,int R,int p,int l,int r,int rt){ if(L <= l && r <= R){ if(col[rt]){ //cout << power(val[rt],p) <<endl; return power(val[rt],p)*(r - l + 1); } } int m = (l + r)/2; Pushdown(rt); int ret = 0; if(L <= m) ret += query(L,R,p,lson); if(m < R) ret += query(L,R,p,rson); return ret%mode; } int main() { while(~scanf("%d %d",&n,&m)){ if(n == 0 && m ==0) break; memset(val,0,sizeof(val)); col[1]= 1; int op,a,b,c; while(m--){ scanf("%d %d %d %d",&op,&a,&b,&c); if(op<4) update(a,b,c,op,1,n,1); else{ int ans = (query(a,b,c,1,n,1) + mode)%mode; printf("%d\n",ans); } } } return 0; }