在大牛分站交能过，主站卡常。
时间复杂度为 n√n ≈ 3.5 * 108，我都不知道怎么过的。。
——代码
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int MAXN = 500001; 8 int n, m, S, C; 9 int a[MAXN], st[MAXN], ed[MAXN], belong[MAXN], sum[MAXN];10 11 inline void init()12 {13 int i, j;14 scanf("%d %d", &n, &m);15 for(i = 1; i <= n; i++) scanf("%d", &a[i]);16 S = sqrt(n) + 10;17 for(i = 1; i <= n; i += S)18 {19 st[++C] = i;20 ed[C] = min(i + S - 1, n);21 }22 for(i = 1; i <= C; i++)23 for(j = st[i]; j <= ed[i]; j++)24 sum[i] += a[j], belong[j] = i;25 }26 27 inline void update(int x, int k)28 {29 a[x] += k;30 sum[belong[x]] += k;31 }32 33 inline int query(int x, int y)34 {35 int i, ans = 0, l = belong[x], r = belong[y];36 if(l == r)37 {38 for(i = x; i <= y; i++) ans += a[i];39 return ans;40 }41 for(i = x; i <= ed[l]; i++) ans += a[i];42 for(i = l + 1; i <= r - 1; i++) ans += sum[i];43 for(i = st[r]; i <= y; i++) ans += a[i];44 return ans;45 }46 47 inline void work()48 {49 int i, x, y, z;50 for(i = 1; i <= m; i++)51 {52 scanf("%d %d %d", &z, &x, &y);53 if(z == 1) update(x, y);54 else printf("%d\n", query(x, y));55 }56 }57 58 int main()59 {60 init();61 work();62 return 0;63 }
在大牛分站交能过，主站卡常。
——代码
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int MAXN = 500001; 8 int n, m, S, C; 9 int a[MAXN], belong[MAXN], add[MAXN], st[MAXN], ed[MAXN];10 11 inline void init()12 {13 int i, j;14 scanf("%d %d", &n, &m);15 for(i = 1; i <= n; i++) scanf("%d", &a[i]);16 S = sqrt(n);17 for(i = 1; i <= n; i += S)18 {19 st[++C] = i;20 ed[C] = min(i + S - 1, n);21 }22 for(i = 1; i <= C; i++)23 for(j = st[i]; j <= ed[i]; j++)24 belong[j] = i;25 }26 27 inline void update(int x, int y, int k)28 {29 int i, l = belong[x], r = belong[y];30 if(l == r)31 {32 for(i = x; i <= y; i++) a[i] += k;33 return;34 }35 for(i = x; i <= ed[l]; i++) a[i] += k;36 for(i = l + 1; i <= r - 1; i++) add[i] += k;37 for(i = st[r]; i <= y; i++) a[i] += k;38 }39 40 inline void work()41 {42 int i, x, y, z, d;43 for(i = 1; i <= m; i++)44 {45 scanf("%d %d", &z, &x);46 if(z == 1)47 {48 scanf("%d %d", &y, &d);49 update(x, y, d);50 }51 else printf("%d\n", a[x] + add[belong[x]]);52 }53 }54 55 int main()56 {57 init();58 work();59 return 0;60 }
这个数据水，主站就能过。
——代码
1 #include2 #include 3 #include 4 #define LL long long 5 6 using namespace std; 7 8 const int MAXN = 100001; 9 int n, m, S, C;10 int st[MAXN], ed[MAXN], belong[MAXN];11 LL a[MAXN], sum[MAXN], add[MAXN];12 13 inline void init()14 {15 int i, j;16 scanf("%d %d", &n, &m);17 for(i = 1; i <= n; i++) scanf("%lld", &a[i]);18 S = sqrt(n);19 for(i = 1; i <= n; i += S)20 {21 st[++C] = i;22 ed[C] = min(i + S - 1, n);23 }24 for(i = 1; i <= C; i++)25 for(j = st[i]; j <= ed[i]; j++)26 sum[i] += a[j], belong[j] = i;27 }28 29 inline void update(int x, int y, LL k)30 {31 int i, l = belong[x], r = belong[y];32 if(l == r)33 {34 for(i = x; i <= y; i++) a[i] += k;35 sum[l] += (y - x + 1) * k;36 return;37 }38 for(i = x; i <= ed[l]; i++) a[i] += k;39 sum[l] += (ed[l] - x + 1) * k;40 for(i = l + 1; i <= r - 1; i++)41 {42 sum[i] += (ed[i] - st[i] + 1) * k;43 add[i] += k;44 }45 for(i = st[r]; i <= y; i++) a[i] += k;46 sum[r] += (y - st[r] + 1) * k;47 }48 49 inline LL query(int x, int y)50 {51 int i, l = belong[x], r = belong[y];52 LL ans = 0;53 if(l == r)54 {55 for(i = x; i <= y; i++) ans += a[i] + add[l];56 return ans;57 }58 for(i = x; i <= ed[l]; i++) ans += a[i] + add[l];59 for(i = l + 1; i <= r - 1; i++) ans += sum[i];60 for(i = st[r]; i <= y; i++) ans += a[i] + add[r];61 return ans;62 }63 64 inline void work()65 {66 int i, x, y, z;67 LL k;68 for(i = 1; i <= m; i++)69 {70 scanf("%d %d %d", &z, &x, &y);71 if(z == 1)72 {73 scanf("%lld", &k);74 update(x, y, k);75 }76 else printf("%lld\n", query(x, y));77 }78 }79 80 int main()81 {82 init();83 work();84 return 0;85 }
看了黄学长的讲解，猛然醒悟！%%%%%hzwer
整块可以直接打标记，而左右两边零散的块要先把它们所属于的整块的标记清除掉再打，否则会错。
——代码
1 #include2 #include 3 #include 4 #define LL long long 5 6 using namespace std; 7 8 const int MAXN = 100001; 9 int n, m, p, S, C; 10 int st[MAXN], ed[MAXN], belong[MAXN]; 11 LL a[MAXN], sum[MAXN], add[MAXN], mul[MAXN]; 12 13 inline void init() 14 { 15 int i, j; 16 scanf("%d %d %d", &n, &m, &p); 17 for(i = 1; i <= n; i++) scanf("%lld", &a[i]); 18 S = sqrt(n); 19 for(i = 1; i <= n; i += S) 20 { 21 st[++C] = i; 22 ed[C] = min(i + S - 1, n); 23 mul[C] = 1; 24 } 25 for(i = 1; i <= C; i++) 26 for(j = st[i]; j <= ed[i]; j++) 27 sum[i] += a[j], belong[j] = i; 28 } 29 30 inline void reset(int x) 31 { 32 int i; 33 for(i = st[x]; i <= ed[x]; i++) 34 a[i] = (a[i] * mul[x] + add[x]) % p; 35 sum[x] = (sum[x] * mul[x] + add[x] * (ed[x] - st[x] + 1)) % p; 36 add[x] = 0, mul[x] = 1; 37 } 38 39 inline void update(int f, int x, int y, LL k) 40 { 41 int i, l = belong[x], r = belong[y]; 42 LL tot; 43 if(l == r) 44 { 45 reset(l); 46 for(tot = 0, i = x; i <= y; i++) 47 { 48 if(f == 1) a[i] = (a[i] * k) % p, tot = (tot + a[i]) % p; 49 else a[i] = (a[i] + k) % p; 50 } 51 if(f == 1) sum[l] = (sum[l] + tot * (k - 1)) % p; 52 else sum[l] = (sum[l] + (y - x + 1) * k) % p; 53 return; 54 } 55 56 reset(l); 57 for(tot = 0, i = x; i <= ed[l]; i++) 58 { 59 if(f == 1) tot = (tot + a[i]) % p, a[i] = (a[i] * k) % p; 60 else a[i] = (a[i] + k) % p; 61 } 62 if(f == 1) sum[l] = (sum[l] + tot * (k - 1)) % p; 63 else sum[l] = (sum[l] + (ed[l] - x + 1) * k) % p; 64 65 reset(r); 66 for(tot = 0, i = st[r]; i <= y; i++) 67 { 68 if(f == 1) tot = (tot + a[i]) % p, a[i] = (a[i] * k) % p; 69 else a[i] = (a[i] + k) % p; 70 } 71 if(f == 1) sum[r] = (sum[r] + tot * (k - 1)) % p; 72 else sum[r] = (sum[r] + (y - st[r] + 1) * k) % p; 73 74 for(i = l + 1; i <= r - 1; i++) 75 if(f == 1) 76 { 77 add[i] = (add[i] * k) % p; 78 mul[i] = (mul[i] * k) % p; 79 } 80 else add[i] = (add[i] + k) % p; 81 } 82 83 inline LL query(int x, int y) 84 { 85 int i, l = belong[x], r = belong[y]; 86 LL ans = 0; 87 if(l == r) 88 { 89 for(i = x; i <= y; i++) 90 ans = (ans + a[i] * mul[l] + add[l]) % p; 91 return ans; 92 } 93 for(i = x; i <= ed[l]; i++) 94 ans = (ans + a[i] * mul[l] + add[l]) % p; 95 for(i = l + 1; i <= r - 1; i++) 96 ans = (ans + sum[i] * mul[i] + add[i] * (ed[i] - st[i] + 1)) % p; 97 for(i = st[r]; i <= y; i++) 98 ans = (ans + a[i] * mul[r] + add[r]) % p; 99 return ans;100 }101 102 inline void work()103 {104 int i, x, y, z;105 LL k;106 for(i = 1; i <= m; i++)107 {108 scanf("%d %d %d", &z, &x, &y);109 if(z == 3) printf("%lld\n", query(x, y));110 else scanf("%lld", &k), update(z, x, y, k);111 }112 }113 114 int main()115 {116 init();117 work();118 return 0;119 }
还有一个链接，黄学长的分块姿势。