分块来水题

luogu P3374 【模板】树状数组 1

在大牛分站交能过，主站卡常。

时间复杂度为 n√n ≈ 3.5 * 10⁸，我都不知道怎么过的。。

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 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 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 32 33 inline int query(int x, int y) 34 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 56 } 57 58 int main() 59
View Code

luoguP3368 【模板】树状数组 2

在大牛分站交能过，主站卡常。

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 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 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 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 51 else printf("%d\n", a[x] + add[belong[x]]); 52 } 53 } 54 55 int main() 56
View Code

luoguP3372 【模板】线段树 1

这个数据水，主站就能过。

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 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 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 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 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 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 } 64 inline void work() 65 76 else printf("%lld\n", query(x, y)); 77 } 78 } 79 80 int main() 81
View Code

luogu P3373 【模板】线段树 2

看了黄学长的讲解，猛然醒悟！%%%%%hzwer

整块可以直接打标记，而左右两边零散的块要先把它们所属于的整块的标记清除掉再打，否则会错。

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 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 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 38 39 inline void update(int f, int x, int y, LL k) 40 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 62 if(f == 1) sum[l] = (sum[l] + tot * (k 1)) % p; 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 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 80 else add[i] = (add[i] + k) % p; 81 } 82 83 inline LL query(int x, int y) 84 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 112 } 113 114 int main() 115
View Code

还有一个链接，黄学长的分块姿势。

【分块】数列分块入门19 by hzwer

上一篇：[BZOJ1029] [JSOI2007]建筑抢修（贪心 + 优先队列）

下一篇：[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）

---

线段树 树状数组 分块 模板