好，这是一个线段树模板。
1 #include <cstdio>
2 using namespace std;
3 const long long int N=1000010;
4 long long int sum[N],tag1[N],tag2[N],mo;
5
6 void build(int l,int r,int o)
7 {
8 tag1[o]=1;
9 if(l==r)
10 {
11 scanf ("%d",&sum[o]);
12 return;
13 }
14 int mid=(l+r)>>1;
15 build(l,mid,o<<1);
16 build(mid+1,r,o<<1|1);
17 sum[o]=(sum[o<<1]+sum[o<<1|1])%mo;
18 return;
19 }
20 void down(int l,int r,int o)
21 {
22 tag1[o<<1]=tag1[o<<1]*tag1[o]%mo;
23 tag1[o<<1|1]=tag1[o<<1|1]*tag1[o]%mo;
24 tag2[o<<1]=(tag2[o<<1]*tag1[o]+tag2[o])%mo;
25 tag2[o<<1|1]=(tag2[o<<1|1]*tag1[o]+tag2[o])%mo;
26 int mid=(l+r)>>1;
27 sum[o<<1]=(sum[o<<1]*tag1[o]+tag2[o]*(mid-l+1))%mo;
28 sum[o<<1|1]=(sum[o<<1|1]*tag1[o]+tag2[o]*(r-mid))%mo;
29 tag1[o]=1;
30 tag2[o]=0;
31 return;
32 }
33
34 void add(int L,int R,int v,int l,int r,int o)
35 {
36 if(L<=l && r<=R)
37 {
38 tag2[o]=(tag2[o]+v)%mo;
39 sum[o]=(sum[o]+v*(r-l+1))%mo;
40 return;
41 }
42 if(r<L || R<l) return;
43 down(l,r,o);
44 int mid=(l+r)>>1;
45 if(L<=mid) add(L,R,v,l,mid,o<<1);
46 if(mid<R) add(L,R,v,mid+1,r,o<<1|1);
47 sum[o]=(sum[o<<1]+sum[o<<1|1])%mo;
48 return;
49 }
50 void mul(int L,int R,int v,int l,int r,int o)
51 {
52 if(L<=l && r<=R)
53 {
54 tag1[o]=tag1[o]*v%mo;
55 tag2[o]=tag2[o]*v%mo;
56 sum[o]=sum[o]*v%mo;
57 return;
58 }
59 if(r<L || R<l) return;
60 down(l,r,o);
61 int mid=(l+r)>>1;
62 if(L<=mid) mul(L,R,v,l,mid,o<<1);
63 if(mid<R) mul(L,R,v,mid+1,r,o<<1|1);
64 sum[o]=(sum[o<<1]+sum[o<<1|1])%mo;
65 return;
66 }
67 long long int ask_sum(int L,int R,int l,int r,int o)
68 {
69 if(L<=l && r<=R) return sum[o];
70 if(r<L || R<l) return 0;
71 int mid=(l+r)>>1;
72 down(l,r,o);
73 long long int ans=ask_sum(L,R,l,mid,o<<1);
74 ans=ans+ask_sum(L,R,mid+1,r,o<<1|1)%mo;
75 sum[o]=(sum[o<<1]+sum[o<<1|1])%mo;
76 return ans%mo;
77 }
78 int main()
79 {
80 int n,m;
81 scanf ("%d%d%d",&n,&m,&mo);
82 build(1,n,1);
83 while(m--)
84 {
85 int flag,x,y,c;
86 scanf ("%d",&flag);
87 if(flag==1)
88 {
89 scanf ("%d%d%d",&x,&y,&c);
90 mul(x,y,c,1,n,1);
91 }
92 else if(flag==2)
93 {
94 scanf ("%d%d%d",&x,&y,&c);
95 add(x,y,c,1,n,1);
96 }
97 else
98 {
99 scanf ("%d%d",&x,&y);
100 printf("%lld\n",ask_sum(x,y,1,n,1));
101 }
102 }
103 return 0;
104 }
就这样。
2018.06.16
今天心血来潮准备打个线段树模板玩，结果调了TM一个多小时...
一交先是RE(我明明开足了4倍空间)，然后又T(你在打我脸)，最后加个快读终于A了，气死我了。
1 #include <cstdio> 2 typedef long long LL; 3 const int N = 100010; 4 5 LL MO; 6 7 inline void Read(LL &x) { 8 x = 0; 9 char c = getchar(); 10 while(c < '0' || c > '9') { 11 c = getchar(); 12 } 13 while(c <= '9' && c >= '0') { 14 x = (x << 3) + (x << 1) + c - 48; 15 c = getchar(); 16 } 17 return; 18 } 19 20 struct SegmentTree { 21 LL sum[N << 2], tag1[N << 2], tag2[N << 2]; 22 int l[N << 2], r[N << 2]; 23 24 inline void update(int o) { 25 sum[o] = sum[o << 1] + sum[o << 1 | 1] % MO; 26 return; 27 } 28 inline void pushdown(int o) { 29 if(!tag2[o] && tag1[o] == 1) { 30 return; 31 } 32 33 int ls = o << 1; 34 int rs = ls | 1; 35 int mid = (l[o] + r[o]) >> 1; 36 37 tag1[ls] = tag1[ls] * tag1[o] % MO; 38 tag2[ls] = (tag2[ls] * tag1[o] % MO + tag2[o]) % MO; 39 sum[ls] = (sum[ls] * tag1[o] % MO + tag2[o] * (mid - l[o] + 1) % MO) % MO; 40 41 tag1[rs] = tag1[rs] * tag1[o] % MO; 42 tag2[rs] = (tag2[rs] * tag1[o] % MO + tag2[o]) % MO; 43 sum[rs] = (sum[rs] * tag1[o] % MO + tag2[o] * (r[o] - mid) % MO) % MO; 44 45 tag1[o] = 1; 46 tag2[o] = 0; 47 return; 48 } 49 void build(int o, int _l, int _r) { 50 l[o] = _l; 51 r[o] = _r; 52 tag1[o] = 1; 53 tag2[o] = 0; 54 if(_l == _r) { 55 Read(sum[o]); 56 sum[o] %= MO; 57 return; 58 } 59 int ls = o << 1; 60 int rs = ls | 1; 61 int mid = (_l + _r) >> 1; 62 build(ls, _l, mid); 63 build(rs, mid + 1, _r); 64 update(o); 65 return; 66 } 67 void add(int L, int R, int o, LL v) { 68 if(L <= l[o] && r[o] <= R) { 69 tag2[o] = (v + tag2[o]) % MO; 70 sum[o] = (sum[o] + v * (r[o] - l[o] + 1) % MO) % MO; 71 return; 72 } 73 if(r[o] < L || R < l[o]) { 74 return; 75 } 76 77 pushdown(o); 78 int ls = o << 1; 79 int rs = ls | 1; 80 int mid = (l[o] + r[o]) >> 1; 81 82 if(L <= mid) { 83 add(L, R, ls, v); 84 } 85 if(mid < R) { 86 add(L, R, rs, v); 87 } 88 update(o); 89 return; 90 } 91 void mul(int L, int R, int o, LL v) { 92 if(L <= l[o] && r[o] <= R) { 93 tag1[o] = v * tag1[o] % MO; 94 tag2[o] = v * tag2[o] % MO; 95 sum[o] = (sum[o] * v) % MO; 96 return; 97 } 98 if(r[o] < L || R < l[o]) { 99 return; 100 } 101 102 pushdown(o); 103 int ls = o << 1; 104 int rs = ls | 1; 105 int mid = (l[o] + r[o]) >> 1; 106 107 if(L <= mid) { 108 mul(L, R, ls, v); 109 } 110 if(mid < R) { 111 mul(L, R, rs, v); 112 } 113 update(o); 114 return; 115 } 116 LL ask(int L, int R, int o) { 117 if(L <= l[o] && r[o] <= R) { 118 return sum[o]; 119 } 120 if(r[o] < L || R < l[o]) { 121 return 0; 122 } 123 124 pushdown(o); 125 int ls = o << 1; 126 int rs = ls | 1; 127 int mid = (l[o] + r[o]) >> 1; 128 129 LL ans = (ask(L, R, ls) + ask(L, R, rs)) % MO; 130 return ans; 131 } 132 }SegT; 133 134 int main() { 135 int n, m; 136 scanf("%d%d%lld", &n, &m, &MO); 137 SegT.build(1, 1, n); 138 for(int i = 1, x, y, f; i <= m; i++) { 139 scanf("%d%d%d", &f, &x, &y); 140 if(f == 3) { 141 printf("%lld\n", SegT.ask(x, y, 1)); 142 } 143 else { 144 LL k; 145 scanf("%lld", &k); 146 if(f == 1) { 147 SegT.mul(x, y, 1, k); 148 } 149 else { 150 SegT.add(x, y, 1, k); 151 } 152 } 153 } 154 155 return 0; 156 }