HDU 4578 Trans formation

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4578
--------------------------------------------
本の操作の比較的に複雑な線分の木のテーマ
線分樹が少ない方は操作を1,2,3ドルずつ加えてください。
直接3つの操作の考えを書くと混乱するかもしれません。
この問題は区間$1から$3の二乗と1の操作について導き出す必要があります。どうやって更新しますか？
区間長は$len 1,2,3の二乗とそれぞれ$sum 1$sum 3$
更新後は$sum 1'$sum 2'$sum 3'$です。
$sum 1'=sum 1+c*len$
$sum 2'=sum 2+sum 1*c*2+  c*c*len$
$sum 3'=sum 3+sum 2*c*3+sum 1*c*3+c*c*c*len$
他の部分は大丈夫です。辛抱強く分析します。コードの量は$2 K+$だけです。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 using namespace std;
  6 const int N = 100010, mod = 10007;
  7 int sum[3][N << 2], flag[3][N << 2];
  8 int n, m;
  9 void update(int x, int L, int R, int tl, int tr, int o, int c);
 10 void build(int x, int tl, int tr)
 11 {
 12     sum[0][x] = sum[1][x] = sum[2][x] = 0;
 13     flag[0][x] = flag[2][x] = 0;
 14     flag[1][x] = 1;
 15     if(tl == tr)
 16         return;
 17     int mid = (tl + tr) >> 1;
 18     build(x << 1, tl, mid);
 19     build(x << 1 | 1, mid + 1, tr);
 20 }
 21 void pushdown(int x, int tl, int tr)
 22 {
 23     int mid = (tl + tr) >> 1;
 24     for(int i = 2; i >= 0; --i)
 25         if(flag[i][x] && !(i == 1 && flag[i][x] == 1))
 26         {
 27             update(x << 1, tl, mid, tl, mid, i, flag[i][x]);
 28             update(x << 1 | 1, mid + 1, tr, mid + 1, tr, i, flag[i][x]);
 29             flag[i][x] = (i == 1 ? 1 : 0);
 30         }
 31 }
 32 void update(int x, int L, int R, int tl, int tr, int o, int c)
 33 {
 34     int mid = (tl + tr) >> 1;
 35     if(L <= tl && tr <= R)
 36     {
 37         if(o == 0)
 38         {
 39             flag[0][x] = (flag[0][x] + c) % mod;
 40             sum[2][x] = (sum[2][x] + sum[1][x] * c * 3 % mod
 41             + sum[0][x] * c % mod * c * 3 % mod + c * c % mod * c % mod * 
 42             (tr - tl + 1) % mod) % mod;
 43             sum[1][x] = (sum[1][x] + sum[0][x] * c * 2 % mod + c * c % mod *
 44             (tr - tl + 1) % mod) % mod;
 45             sum[0][x] = (sum[0][x] + c * (tr - tl + 1) % mod) % mod; 
 46         }
 47         else if(o == 1)
 48         {
 49             flag[0][x] = flag[0][x] * c % mod;
 50             flag[1][x] = flag[1][x] * c % mod;
 51             sum[0][x] = sum[0][x] * c % mod;
 52             sum[1][x] = sum[1][x] * c % mod * c % mod;
 53             sum[2][x] = sum[2][x] * c % mod * c % mod * c % mod;
 54         }
 55         else
 56         {
 57             flag[0][x] = 0;
 58             flag[1][x] = 1;
 59             flag[2][x] = c;
 60             sum[0][x] = (tr - tl + 1) * c % mod;
 61             sum[1][x] = (tr - tl + 1) * c % mod * c % mod;
 62             sum[2][x] = (tr - tl + 1) * c % mod * c % mod * c % mod;
 63         }
 64         return;
 65     }
 66     pushdown(x, tl, tr);
 67     if(L <= mid)
 68         update(x << 1, L, R, tl, mid, o, c);
 69     if(mid < R)
 70         update(x << 1 | 1, L, R, mid + 1, tr, o, c);
 71     for(int i = 0; i < 3; ++i)
 72         sum[i][x] = (sum[i][x << 1] + sum[i][x << 1 | 1]) % mod;
 73 }
 74 int query(int x, int L, int R, int tl, int tr, int p)
 75 {
 76     if(L <= tl && tr <= R)
 77         return sum[p][x];
 78     pushdown(x, tl, tr);
 79     int mid = (tl + tr) >> 1, re= 0;
 80     if(L <= mid)
 81         re += query(x << 1, L, R, tl, mid, p);
 82     if(mid < R)
 83         re += query(x << 1 | 1, L, R, mid + 1, tr, p);
 84     return re % mod;
 85 }
 86 int main()
 87 {
 88     while(scanf("%d%d", &n, &m),n)
 89     {
 90         build(1, 1, n);
 91         int o, x, y, c;
 92         while(m--)
 93         {
 94             scanf("%d%d%d%d", &o, &x, &y, &c);
 95             if(o != 4)
 96                 update(1, x, y, 1, n, o - 1, c);
 97             else
 98                 printf("%d
", query(1, x, y, 1, n, c - 1));
 99         }
100     }
101     return 0;
102 }