ACM之路（14）—— 线段树的日常（上）

　　我的线段树简直有毒，各种错误都能忙上半天。做了kuangbin的线段树专题的一半，还有一半留到以后去做。

　　链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66989#overview

　　总结一下题目吧：

　　A和B都是最简单的线段树，也没有成段更新。A就是维护一段区间的和，B题就是维护一段区间的最大值。这两题直接给出代码，当做一个模板吧。

　　A：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 #define t_mid (l+r >> 1)
 6 #define ls (o<<1)
 7 #define rs (o<<1 | 1)
 8 #define lson ls,l,t_mid
 9 #define rson rs,t_mid+1,r
10 
11 const int N = 50000+5;
12 int a[N];
13 int c[N<<2];
14 
15 void up(int o) {c[o]=c[ls]+c[rs];}
16 int build(int o,int l,int r)
17 {
18     if(l==r) return c[o]=a[l];
19     return c[o] = build(lson) + build(rson);
20 }
21 void update(int o,int l,int r,int pos,int dt)
22 {
23     if(l==r)
24     {
25         c[o]+=dt;
26         return;
27     }
28     if(pos <= t_mid) update(lson,pos,dt);
29     if(pos > t_mid) update(rson,pos,dt);
30     up(o);
31 }
32 int query(int o,int l,int r,int ql,int qr)
33 {
34     if(ql == l && qr == r) return c[o];
35     int res = 0;
36     if(qr<=t_mid) res+=query(lson,ql,qr);
37     else if(ql>t_mid) res+=query(rson,ql,qr);
38     else
39     {
40         res+=query(lson,ql,t_mid);
41         res+=query(rson,t_mid+1,qr);
42     }
43     //if(ql <= t_mid) res += query(lson,ql,qr);
44     //if(qr > t_mid) res += query(rson,ql,qr);
45     /*
46         注释掉的地方是另外一种写法，只要把第一行改成
47         if(ql <= l && qr >= r) reutrn c[o];
48         即可
49     */
50     return res;
51 }
52 
53 int main()
54 {
55     int T;
56     scanf("%d",&T);
57     for(int kase=1;kase<=T;kase++)
58     {
59         printf("Case %d:
",kase);
60         int n;
61         scanf("%d",&n);
62         for(int i=1;i<=n;i++) scanf("%d",a+i);
63         build(1,1,n);
64 
65         char s[15];
66         while(scanf("%s",s)==1 && strcmp(s,"End"))
67         {
68             int x,y;
69             scanf("%d%d",&x,&y);
70             if(!strcmp(s,"Add")) update(1,1,n,x,y);
71             else if(!strcmp(s,"Sub")) update(1,1,n,x,-y);
72             else if(!strcmp(s,"Query")) printf("%d
",query(1,1,n,x,y));
73         }
74     }
75 }

View Code

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 #define t_mid (l+r >> 1)
 6 #define ls (o<<1)
 7 #define rs (o<<1 | 1)
 8 #define lson ls,l,t_mid
 9 #define rson rs,t_mid+1,r
10 
11 const int N = 200000+5;
12 int a[N];
13 int c[N<<2];
14 
15 void up(int o) {c[o]=max(c[ls],c[rs]);}
16 int build(int o,int l,int r)
17 {
18     if(l==r) return c[o]=a[l];
19     return c[o] = max(build(lson),build(rson));
20 }
21 void update(int o,int l,int r,int pos,int dt)
22 {
23     if(l==r)
24     {
25         c[o]=dt;
26         return;
27     }
28     if(pos <= t_mid) update(lson,pos,dt);
29     if(pos > t_mid) update(rson,pos,dt);
30     up(o);
31 }
32 int query(int o,int l,int r,int ql,int qr)
33 {
34     if(ql <= l && qr >= r) return c[o];
35     int r1=0,r2=0;
36     if(ql <= t_mid) r1 = query(lson,ql,qr);
37     if(qr > t_mid) r2 = query(rson,ql,qr);
38     return max(r1,r2);
39 }
40 
41 int main()
42 {
43     int n,m;
44     while(scanf("%d%d",&n,&m)==2)
45     {
46         for(int i=1;i<=n;i++) scanf("%d",a+i);
47         build(1,1,n);
48 
49         while(m--)
50         {
51             char s[15];
52             scanf("%s",s);
53             int x,y;
54             scanf("%d%d",&x,&y);
55             if(!strcmp(s,"U")) update(1,1,n,x,y);
56             else if(!strcmp(s,"Q")) printf("%d
",query(1,1,n,x,y));
57         }
58     }
59 }

View Code

　　然后看一下F题，要求维护的是区间内最大的和最小的差值，那么其实维护的就是区间的最小值和最大值。然后在所需区间相减即可。

　　具体见代码：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <set>
 4 #include <vector>
 5 #include <map>
 6 #include <string.h>
 7 #define t_mid (l+r>>1)
 8 #define ls (o<<1)
 9 #define rs (o<<1 | 1)
10 #define lson ls,l,t_mid
11 #define rson rs,t_mid+1,r
12 using namespace std;
13 
14 const int N = 1000000 + 5;
15 
16 struct node
17 {
18     int a,b;
19 }c[N<<2];
20 int h[N];
21 
22 node get(node a,node b)
23 {
24     node ans;
25     ans.a = max(a.a,b.a);
26     ans.b = min(a.b,b.b);
27     return ans;
28 }
29 
30 node build(int o,int l,int r)
31 {
32     if(l==r) return c[o]=(node){h[l],h[l]};
33     node a = build(lson);
34     node b = build(rson);
35     return c[o] = get(a,b);
36 }
37 
38 node query(int o,int l,int r,int ql,int qr)
39 {
40     if(l==ql && r==qr)
41     {
42         return c[o];
43     }
44     
45     node res;
46     if(qr <= t_mid) res=query(lson,ql,qr);
47     else if(ql > t_mid) res=query(rson,ql,qr);
48     else
49     {
50         res=get(query(lson,ql,t_mid),query(rson,t_mid+1,qr));
51     }
52     return res;
53 }
54 
55 int main()
56 {
57     int n,m;
58     while(scanf("%d%d",&n,&m)==2)
59     {
60 
61         for(int i=1;i<=n;i++) scanf("%d",h+i);
62         build(1,1,n);
63 
64         while(m--)
65         {
66             int x,y;
67             scanf("%d%d",&x,&y);
68             node ans = query(1,1,n,x,y);
69             printf("%d
",ans.a-ans.b);
70         }
71     }
72 }

View Code

　　然后就是成段更新的问题了，C和E。要注意的是add数组（或者叫做懒惰标记要清空一下）。

　　这里就给出C题代码：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 #define t_mid (l+r >> 1)
 6 #define ls (o<<1)
 7 #define rs (o<<1 | 1)
 8 #define lson ls,l,t_mid
 9 #define rson rs,t_mid+1,r
10 typedef long long ll;
11 
12 const int N = 100000+5;
13 ll a[N];
14 ll c[N<<2],add[N<<2];
15 
16 void up(int o) {c[o] = c[ls] + c[rs];}
17 void down(int o,int len)
18 {
19     if(add[o])
20     {
21         add[ls] += add[o];
22         add[rs] += add[o];
23         c[ls] += add[o] * (len - (len >> 1) );
24         c[rs] += add[o] * (len >> 1);
25         add[o]=0;
26     }
27 }
28 ll build(int o,int l,int r)
29 {
30     if(l==r) return c[o]=a[l];
31     return c[o] = build(lson) + build(rson);
32 }
33 void update(int o,int l,int r,int ql,int qr,ll dt)
34 {
35     if(ql == l && qr == r)
36     {
37         add[o] += dt;
38         c[o] += dt * (r-l+1);
39         return;
40     }
41     down(o,r-l+1);
42     if(qr <= t_mid) update(lson,ql,qr,dt);
43     else if(ql>t_mid) update(rson,ql,qr,dt);
44     else
45     {
46         update(lson,ql,t_mid,dt);
47         update(rson,t_mid+1,qr,dt);
48     }
49     up(o);
50 }
51 ll query(int o,int l,int r,int ql,int qr)
52 {
53     if(ql == l && qr == r) return c[o];
54     down(o,r-l+1);
55     ll res = 0;
56     if(qr <= t_mid) res+=query(lson,ql,qr);
57     else if(ql>t_mid) res+=query(rson,ql,qr);
58     else
59     {
60         res+=query(lson,ql,t_mid);
61         res+=query(rson,t_mid+1,qr);
62     }
63     return res;
64 }
65 void init()
66 {
67     memset(add,0,sizeof(add));
68 }
69 
70 int main()
71 {
72     int n,m;
73     while(scanf("%d%d",&n,&m)==2)
74     {
75         init();
76 
77         for(int i=1;i<=n;i++) scanf("%I64d",a+i);
78         build(1,1,n);
79 
80         while(m--)
81         {
82             char s[15];
83             scanf("%s",s);
84             if(s[0]=='C')
85             {
86                 int x,y;
87                 ll dt;
88                 scanf("%d%d%I64d",&x,&y,&dt);
89                 update(1,1,n,x,y,dt);
90             }
91             else
92             {
93                 int x,y;
94                 scanf("%d%d",&x,&y);
95                 printf("%I64d
",query(1,1,n,x,y));
96             }
97         }
98     }
99 }

View Code

　　接着其他几题都是比较零散的问题，先看D。这是一个离散化的问题，因为有些区间过长所以离散化成小区间，然后再用线段树，注意这里有个离散技巧，在离散化以后，如果两点间距离相差大于1，就把小的一点+1的值也作为离散后的点这样可以有效的防止有些区间被漏过去，比方说先涂色1-10，再1-4，最后6-10，这样的话如果不这么处理5这个区间就被盖过去了。其实现在讲起来还是有点迷糊，就先这样吧，以后再看。还要注意的是一个地方unique去重的话返回的是最后一个不重复元素的下一个地址，因此要求不重复元素的个数的话要减去的是第一个元素的下标就好了。

　　具体见代码吧：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <set>
  4 #include <vector>
  5 #include <map>
  6 #include <string.h>
  7 #define t_mid (l+r>>1)
  8 #define ls (o<<1)
  9 #define rs (o<<1 | 1)
 10 #define lson ls,l,t_mid
 11 #define rson rs,t_mid+1,r
 12 using namespace std;
 13 
 14 const int N = 10000 + 5;
 15 
 16 int c[N<<4];
 17 bool vis[N];
 18 int arr[N<<4];
 19 int pl[N],pr[N];
 20 int ans=0;
 21 
 22 void pushDown(int o)
 23 {
 24     if(c[o]!=-1)
 25     {
 26         c[ls]=c[rs]=c[o];
 27         c[o]=-1;
 28     }
 29 }
 30 void update(int o,int l,int r,int ql,int qr,int dt)
 31 {
 32     if(ql == l && qr == r)
 33     {
 34         c[o] = dt;
 35         return;
 36     }
 37     pushDown(o);
 38     if(qr <= t_mid) update(lson,ql,qr,dt);
 39     else if(ql > t_mid) update(rson,ql,qr,dt);
 40     else
 41     {
 42         update(lson,ql,t_mid,dt);
 43         update(rson,t_mid+1,qr,dt);
 44     }
 45 }
 46 void query(int o,int l,int r)
 47 {
 48     if(c[o]!=-1)
 49     {
 50         if(!vis[c[o]])
 51         {
 52             vis[c[o]]=1;
 53             ans++;
 54         }
 55         return;
 56     }
 57     if(l==r) return;
 58     query(lson);
 59     query(rson);
 60 }
 61 
 62 int main()
 63 {
 64     int T;
 65     scanf("%d",&T);
 66     while(T--)
 67     {
 68         int n;
 69         scanf("%d",&n);
 70         memset(vis,0,sizeof(vis));
 71         memset(c,-1,sizeof(c));
 72 
 73         int sit=0;
 74         for(int i=1;i<=n;i++)
 75         {
 76             scanf("%d%d",&pl[i],&pr[i]);
 77             arr[++sit] = pl[i];
 78             arr[++sit] = pr[i];
 79         }
 80         sort(arr+1,arr+1+sit);
 81         int num = unique(arr+1,arr+1+sit)-(arr+1);
 82 
 83         for(int i=num;i>=2;i--)
 84         {
 85             if(arr[i]-arr[i-1] > 1) arr[++num] = arr[i-1] + 1;
 86         }
 87         sort(arr+1,arr+1+num);
 88 
 89         for(int i=1;i<=n;i++)
 90         {
 91             int l = lower_bound(arr+1,arr+1+num,pl[i])-arr;
 92             int r = lower_bound(arr+1,arr+1+num,pr[i])-arr;
 93             update(1,1,num,l,r,i);
 94         }
 95 
 96         ans=0;
 97         query(1,1,num);
 98         printf("%d
",ans);
 99     }
100 }

View Code

　　G题是对一个区间每次都开根号的进行操作，思路是就算是一个long long的整数，开8次根号也就变成1了，那么对于都是1的区间就不需要递归了，但是这题也不知道为什么无限WA，留着以后再看。另外这题有毒的一个地方在于，每次给出的区间不一定是后面的大于前面的！。。

　　代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <set>
 4 #include <math.h>
 5 #include <vector>
 6 #include <map>
 7 #include <string.h>
 8 #define t_mid (l+r>>1)
 9 #define ls (o<<1)
10 #define rs (o<<1 | 1)
11 #define lson ls,l,t_mid
12 #define rson rs,t_mid+1,r
13 using namespace std;
14 typedef long long ll;
15 
16 const int N = 100000 + 5;
17 
18 ll c[N<<4];
19 ll a[N];
20 
21 int build(int o,int l,int r)
22 {
23     if(l==r) return c[o]=a[l];
24     return c[o] = build(lson) + build(rson);
25 }
26 void pushup(int o) {c[o]=c[ls]+c[rs];}
27 void update(int o,int l,int r,int ql,int qr)
28 {
29     if(l==ql && r==qr && (ll)(r-l+1) == c[o])
30     {
31         return;
32     }
33     else if(l==r) {c[o] = (ll)(sqrt((double)c[o]));return;}
34     
35     if(qr <= t_mid) update(lson,ql,qr);
36     else if(ql > t_mid) update(rson,ql,qr);
37     else
38     {
39         update(lson,ql,t_mid);
40         update(rson,t_mid+1,qr);
41     }
42     pushup(o);
43 }
44 ll query(int o,int l,int r,int ql,int qr)
45 {
46     if(l==ql && r==qr)
47     {
48         return c[o];
49     }
50     
51     ll res=0;
52     if(qr <= t_mid) res=query(lson,ql,qr);
53     else if(ql > t_mid) res=query(rson,ql,qr);
54     else
55     {
56         res = query(lson,ql,t_mid) + query(rson,t_mid+1,qr);
57     }
58     return res;
59 }
60 
61 int main()
62 {
63     int n,m;
64     int cnt=1;
65     while(scanf("%d",&n)==1)
66     {
67         printf("Case #%d:
",cnt++);
68         for(int i=1;i<=n;i++) scanf("%I64d",a+i);
69         build(1,1,n);
70 
71         scanf("%d",&m);
72         while(m--)
73         {
74             int x,y,z;
75             scanf("%d%d%d",&z,&x,&y);
76             if(z==0) update(1,1,n,min(x,y),max(x,y));
77             else printf("%I64d
",query(1,1,n,min(x,y),max(x,y)));
78         }
79         puts("");
80     }
81 }

View Code

　　H题是一个很奥义的题，题目意思是每次可以拆村庄或者恢复最后一个被破坏的村庄，询问的话就是询问村庄x附近最多有多少个连续的村庄。解释一下代码里面的数组的含义吧：lsum的意思是这个区间里面从最左边开始有多少个连续的村庄，rsum是从右边开始，msum是在这个区间里面最多有多少个连续的村庄。明白了这些以后代码就可以看懂了。具体见代码：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <set>
  4 #include <math.h>
  5 #include <vector>
  6 #include <stack>
  7 #include <map>
  8 #include <string.h>
  9 #define t_mid (l+r>>1)
 10 #define ls (o<<1)
 11 #define rs (o<<1 | 1)
 12 #define lson ls,l,t_mid
 13 #define rson rs,t_mid+1,r
 14 using namespace std;
 15 typedef long long ll;
 16 const int N = 50000 + 5;
 17 
 18 stack<int> S;
 19 int lsum[N<<2],rsum[N<<2],msum[N<<2],c[N<<2];
 20 
 21 void build(int o,int l,int r)
 22 {
 23     lsum[o]=rsum[o]=msum[o]=r-l+1;
 24     if(l==r) return;
 25     build(lson);
 26     build(rson);
 27 }
 28 int query(int o,int l,int r,int ind)
 29 {
 30     if(l==r || msum[o]==0 || msum[o]==r-l+1) return msum[o];
 31     if(ind <= t_mid)
 32     {
 33         if(ind >= t_mid-rsum[ls]+1)
 34         {
 35             return query(lson,ind) + query(rson,t_mid+1); //t_mid+1查右边第一点的连续情况
 36         }
 37         else
 38         {
 39             return query(lson,ind);
 40         }
 41     }
 42     else
 43     {
 44         if(ind <= t_mid+lsum[rs])
 45         {
 46             return query(lson,t_mid) + query(rson,ind); //t_mid查左边第一点的连续情况
 47         }
 48         else
 49         {
 50             return query(rson,ind);
 51         }
 52     }
 53 }
 54 void update(int o,int l,int r,int ind,int f)
 55 {
 56     if(l==r)
 57     {
 58         lsum[o]=rsum[o]=msum[o]=f;
 59         return;
 60     }
 61 
 62     if(ind <= t_mid) update(lson,ind,f);
 63         else update(rson,ind,f);
 64 
 65     if(t_mid - l + 1 == lsum[ls]) lsum[o] = lsum[ls] + lsum[rs];
 66         else lsum[o] = lsum[ls];
 67     if(r - t_mid == rsum[rs]) rsum[o] = rsum[rs] + rsum[ls];
 68         else rsum[o] = rsum[rs];
 69 
 70     msum[o] = max(max(msum[ls],msum[rs]),rsum[ls]+lsum[rs]);
 71 }
 72 
 73 int main()
 74 {
 75     int n,m;
 76     while(scanf("%d%d",&n,&m)==2)
 77     {
 78         while(!S.empty()) S.pop();
 79         build(1,1,n);
 80 
 81         while(m--)
 82         {
 83             char s[10];
 84             scanf("%s",s);
 85             if(s[0] == 'R')
 86             {
 87                 int x = S.top();S.pop();
 88                 update(1,1,n,x,1);
 89             }
 90             else
 91             {
 92                 int x;
 93                 scanf("%d",&x);
 94                 if(s[0] == 'D')
 95                 {
 96                     update(1,1,n,x,0);
 97                     S.push(x);
 98                 }
 99                 else
100                 {
101                     printf("%d
",query(1,1,n,x));
102                 }
103             }
104         }
105     }
106 }

View Code

　　I题是用dfs序号维护的线段树，比较有意思。题意是给一个有向图，每次对x点涂色，该点和其下面的点都会被涂色，然后查询时查询某点的颜色。思路就是先得出dfs序，然后如果更新某点的颜色，就update这点的区间为该点的起始时间和终了之间，因为在这个时间内访问的节点恰恰为这点和他的子节点。同时，要查询颜色的话就是把这点的起始时间当做节点号访问就行。具体见代码：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <set>
  4 #include <math.h>
  5 #include <vector>
  6 #include <stack>
  7 #include <map>
  8 #include <string.h>
  9 #define t_mid (l+r>>1)
 10 #define ls (o<<1)
 11 #define rs (o<<1 | 1)
 12 #define lson ls,l,t_mid
 13 #define rson rs,t_mid+1,r
 14 using namespace std;
 15 typedef long long ll;
 16 const int N = 50000 + 5;
 17 
 18 vector<int> G[N];
 19 int n,dfs_clock,st[N],ed[N],add[N<<2],c[N<<2];
 20 bool use[N];
 21 
 22 void init()
 23 {
 24     dfs_clock=0;
 25     for(int i=1;i<=n;i++) G[i].clear();
 26     memset(st,0,sizeof(st));
 27     memset(ed,0,sizeof(ed));
 28     memset(use,0,sizeof(use));
 29 }
 30 void build(int o,int l,int r)
 31 {
 32     c[o]=add[o]=-1;
 33     if(l==r) return;
 34     build(lson);
 35     build(rson);
 36 }
 37 void pushdown(int o)
 38 {
 39     if(add[o] != -1)
 40     {
 41         add[ls]=add[rs]=add[o];
 42         c[ls]=c[rs]=add[o];
 43         add[o]=-1;
 44     }
 45 }
 46 void dfs(int u)
 47 {
 48     st[u]=++dfs_clock;
 49     for(int i=0;i<G[u].size();i++)
 50     {
 51         int v = G[u][i];
 52         dfs(v);
 53     }
 54     ed[u]=dfs_clock;
 55 }
 56 void update(int o,int l,int r,int ql,int qr,int f)
 57 {
 58     if(ql <= l && qr >= r)
 59     {
 60         c[o] = f;
 61         add[o] = f;
 62         return;
 63     }
 64     pushdown(o);
 65     if(ql <= t_mid) update(lson,ql,qr,f);
 66     if(qr > t_mid) update(rson,ql,qr,f);
 67 }
 68 int query(int o,int l,int r,int ind)
 69 {
 70     if(l==r) return c[o];
 71     pushdown(o);
 72     if(ind <= t_mid) return query(lson,ind);
 73         else return query(rson,ind);
 74 }
 75 
 76 int main()
 77 {
 78     int T,m;
 79     scanf("%d",&T);
 80     for(int kase=1;kase<=T;kase++)
 81     {
 82         printf("Case #%d:
",kase);
 83         init();
 84 
 85         scanf("%d",&n);
 86         for(int i=1;i<n;i++)
 87         {
 88             int u,v;
 89             scanf("%d%d",&u,&v);
 90             G[v].push_back(u);
 91             use[u]=1;
 92         }
 93         for(int i=1;i<=n;i++) if(!use[i]) dfs(i);
 94         build(1,1,n);
 95 
 96         char s[10];
 97         scanf("%d",&m);
 98         while(m--)
 99         {
100             scanf("%s",s);
101             if(s[0] == 'C')
102             {
103                 int x;
104                 scanf("%d",&x);
105                 printf("%d
",query(1,1,n,st[x]));
106             }
107             else
108             {
109                 int x,y;
110                 scanf("%d%d",&x,&y);
111                 update(1,1,n,st[x],ed[x],y);
112             }
113         }
114     }
115     return 0;
116 }

View Code

　　J题题意很简单，就是区间操作还有乘法。那么思路就是，用变量记录一段区间值是不是相等，相等的话只要记录下这次操作变化了多少就可以，不相等就递归下去，不过这题细节也挺多的，反正无限WA，留着以后再看。这题真是有毒！。。代码如下：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <set>
  4 #include <math.h>
  5 #include <vector>
  6 #include <stack>
  7 #include <map>
  8 #include <string.h>
  9 #define t_mid (l+r>>1)
 10 #define ls (o<<1)
 11 #define rs (o<<1 | 1)
 12 #define lson ls,l,t_mid
 13 #define rson rs,t_mid+1,r
 14 using namespace std;
 15 typedef long long ll;
 16 const int N = 100000 + 5;
 17 const int mod = 10007;
 18 
 19 ll add[N<<2],mul[N<<2],ch[N<<2],c[N<<2]; //ch表示这一段是否都是一个值,c表示这一段都是这一个数
 20 
 21 void build(int o,int l,int r)
 22 {
 23     mul[o]=1;
 24     add[o]=c[o]=ch[o]=0; //我觉得这里的ch[o]应该等于1，但是AC代码是0，而且答案都一样。
 25     if(l==r)
 26     {
 27         ch[o]=1;
 28         return;
 29     }
 30     build(lson);
 31     build(rson);
 32 }
 33 
 34 void pushdown(int o,int l,int r)
 35 {
 36     if(l==r) return;
 37     if(ch[o])
 38     {
 39         add[ls]=0,mul[ls]=1;
 40         add[rs]=0,mul[rs]=1;
 41         ch[ls]=ch[rs]=1;
 42         c[ls]=c[rs]=c[o];
 43         ch[o]=0;
 44     }
 45     else
 46     {
 47         if(add[o])
 48         {
 49             if(ch[ls]) c[ls] = (c[ls]+add[o]) % mod;
 50             else
 51             {
 52                 pushdown(lson);
 53                 add[ls]=(add[o]+add[ls]) % mod;
 54             }
 55 
 56             if(ch[rs]) c[rs] = (c[rs]+add[o]) % mod;
 57             else
 58             {
 59                 pushdown(rson);
 60                 add[rs]=(add[o]+add[rs]) % mod;
 61             }
 62             add[o]=0;
 63         }
 64 
 65         if(mul[o]>1)
 66         {
 67             if(ch[ls]) c[ls]=(c[ls]*mul[o]) % mod;
 68             else
 69             {
 70                 pushdown(lson);
 71                 mul[ls]=(mul[o]*mul[ls]) % mod;
 72             }
 73 
 74             if(ch[rs]) c[rs]=(c[rs]*mul[o]) % mod;
 75             else
 76             {
 77                 pushdown(rson);
 78                 mul[rs]=(mul[o]*mul[rs]) % mod;
 79             }
 80             mul[o]=1;
 81         }
 82     }
 83 }
 84 
 85 void update(int o,int l,int r,int ql,int qr,int f,int op)
 86 {
 87     if(ql <= l && qr >= r)
 88     {
 89         if(op == 3)
 90         {
 91             ch[o]=1,c[o]=f;
 92             mul[o]=1,add[o]=0;
 93         }
 94         else
 95         {
 96             if(ch[o])
 97             {
 98                 if(op == 1) c[o]=(c[o]+f)%mod;
 99                     else c[o]=c[o]*f%mod;
100             }
101             else
102             {
103                 pushdown(o,l,r);
104                 if(op == 1) add[o]=(c[o]+f)%mod;
105                     else mul[o]=mul[o]*f%mod;
106             }
107         }
108         return;
109     }
110 
111     pushdown(o,l,r);
112     if(ql <= t_mid) update(lson,ql,qr,f,op);
113     if(qr > t_mid) update(rson,ql,qr,f,op);
114 }
115 
116 ll query(int o,int l,int r,int ql,int qr,int p)
117 {
118     if(ql <= l && qr >= r)
119     {
120         if(ch[o])
121         {
122             ll ans = 1,t=c[o];
123             for(int i=1;i<=p;i++) ans = ans * t % mod;
124             return (r-l+1) * ans % mod;
125         }
126     }
127 
128     pushdown(o,l,r);
129     ll ans = 0;
130     if(ql <= t_mid) ans += query(lson,ql,qr,p);
131     if(qr > t_mid) ans += query(rson,ql,qr,p);
132     return ans % mod;
133 }
134 int main()
135 {
136     int n,m;
137     while(scanf("%d%d",&n,&m)==2)
138     {
139         if(n==0 && m==0) break;
140         build(1,1,n);
141         while(m--)
142         {
143             int op,x,y,f;
144             scanf("%d%d%d%d",&op,&x,&y,&f);
145             if(op<=3) update(1,1,n,x,y,f,op);
146                 else printf("%I64d
",query(1,1,n,x,y,f));
147         }
148     }
149     return 0;
150 }

View Code

　　哎，线段树真的好烦！。。