Transformation

hdu4578:http://acm.hdu.edu.cn/showproblem.php?pid=4578

题意：
给一个序列 {an}，有 4 种操作。
1、将一段区间的数全部加 c。
2、将一段区间的数全部乘 c。
3、将一段区间的数全部等于 c。
4、询问一段区间的和（和、平方和、立方和）。
解题思路：
这道题自己完全不会打，虽然知道思路。所以借鉴了大神的代码。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 using namespace std;
  5 const int N = 1e5 + 5;
  6 const int mod = 10007;
  7 #define lson u<<1
  8 #define rson u<<1|1
  9 
 10 inline int sqr2(int x){
 11     return x * x % mod;
 12 }
 13 
 14 inline int sqr3(int x){
 15     return sqr2(x) * x % mod;
 16 }
 17 
 18 struct SegTree{
 19     int l,r;
 20     int sum[4];
 21     int mul,add;
 22     inline int mid(){
 23         return (l+r)>> 1;
 24     }
 25     inline int len(){
 26         return r-l+1;
 27     }
 28     void flag_init(){
 29         add = 0, mul = 1;
 30     }
 31     void to_mul(int m){
 32         (sum[1] *= m) %= mod;
 33         (sum[2] *= sqr2(m)) %= mod;
 34         (sum[3] *= sqr3(m)) %= mod;
 35 
 36         (mul *= m) %= mod;
 37         (add *= m) %= mod;
 38     }
 39     void to_add(int a){
 40         (sum[3] += sqr3(a) * len()) %= mod;
 41         (sum[3] += 3 *  a    * sum[2]) %= mod;
 42         (sum[3] += 3 * sqr2(a) * sum[1]) %= mod;
 43 
 44         (sum[2] += sqr2(a) * len()) %= mod;
 45         (sum[2] += 2 * a  * sum[1]) %= mod;
 46 
 47         (sum[1] += a * len()) %= mod;
 48 
 49         (add += a) %= mod;
 50     }
 51 }T[N<<2];
 52 void build(int u,int l,int r){
 53     T[u].l = l , T[u].r = r;
 54     memset(T[u].sum,0,sizeof(T[u].sum));
 55     T[u].flag_init();
 56     if(l==r)
 57         return ;
 58     int m = T[u].mid();
 59     build(lson,l,m);
 60     build(rson,m+1,r);
 61 }
 62 int op;
 63 void push_down(int u){
 64     T[lson].to_mul(T[u].mul);
 65     T[rson].to_mul(T[u].mul);
 66     T[lson].to_add(T[u].add);
 67     T[rson].to_add(T[u].add);
 68     T[u].flag_init();
 69 }
 70 void push_up(int u){
 71   for(int i=1;i<=3;i++)
 72     T[u].sum[i] = (T[lson].sum[i] + T[rson].sum[i]) % mod;
 73 }
 74 
 75 void updata(int u,int l,int r,int mul,int add){
 76     if(T[u].l == l && T[u].r == r){
 77         T[u].to_mul(mul);
 78         T[u].to_add(add);
 79         return ;
 80     }
 81     push_down(u);
 82     int m = T[u].mid();
 83     if(r <= m)
 84         updata(lson,l,r,mul,add);
 85     else if(l >m)
 86         updata(rson,l,r,mul,add);
 87     else
 88         updata(lson,l,m,mul,add), updata(rson,m+1,r,mul,add);
 89     push_up(u);
 90 }
 91 int query(int u,int l,int r){
 92     if(T[u].l == l && T[u].r == r)
 93         return T[u].sum[op];
 94     push_down(u);
 95     int m = T[u].mid();
 96     if(r <= m)
 97         return query(lson,l,r);
 98     else if(l >m)
 99         return query(rson,l,r);
100     else
101         return (query(lson,l,m)+query(rson,m+1,r)) % mod;
102 }
103 
104 int main(){
105     int n,m,a,b,c;
106     while(scanf("%d%d",&n,&m),n||m){
107         build(1,1,n+1);
108         while(m--){
109             scanf("%d",&op);
110             if(op == 4){
111                 scanf("%d%d%d",&a,&b,&op);
112                 printf("%d
",query(1,a,b));
113             }
114             else{
115                 scanf("%d%d%d",&a,&b,&c);
116                 if(op == 1)
117                     updata(1,a,b,1,c);
118                 else if(op == 2)
119                     updata(1,a,b,c,0);
120                 else
121                     updata(1,a,b,0,c);
122             }
123         }
124     }
125     return 0;
126 }

View Code