分块，是一种可以说是，相当，暴力的数据结构。
分块算法的思想是通过适当的划分，预处理一部分信息保存下来，用空间换取时间，达到时空平衡。
基本操作是，将一段序列，分成一定数量的块，每一块有一个长度，表示一段区间。对于区间操作，通过对完整块的整体操作和对不完整块的暴力操作而使复杂度尽可能的低
一般来讲，块的大小常设为sqrt(n)，但实际上块的大小可以任意自定，不过肯定是要让复杂度尽可能的优秀
分块的效率要低于树状数组和线段树，且代码实现比较随意，相对来说更好理解。
但是俗话说的好：越简单的东西，就意味着它越牢固，可拓展性越强。
分块与其说是数据结构，它更像是一种思想，就像分治这样，虽然分块的整体框架也基本固定。
分块与树状数组，线段树相比，我个人认为，它最大的优点在于，它本身极为强大的可拓展性。
也就是说分块可以容纳相当多的区间操作，这也是由分块本身的性质决定的。
分块更多的像是一个思想。
分块实现的基本框架：
划分块，预处理，操作或查询。
操作或查询通常为4步：
1.判断要操作或是查询的区间是否在一个块内
2.若在一个块内，暴力操作或查询
3.若不在一个块内，将除了最左边和最右边这两个块外其余的块进行整体的操作，即直接对块打上修改标记之类的
4.单独暴力处理最左边的块和最右边的块
同时分块的块内还可以使用别的数据结构或是操作以实现要求或进一步优化复杂度
分块例题1—9（loj）当然更建议直接看黄学长的博客
分块入门1：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。
1 #include<bits/stdc++.h>
2 using namespace std; 3 const int maxn = 50086; 4 int a[maxn], n; 5 int add[maxn]; 6 int pos[maxn];//, sum[maxn];
7 int L[maxn], R[maxn]; 8
9 inline int read() { 10 int x = 0, y = 1; 11 char ch = getchar(); 12 while(!isdigit(ch)) { 13 if(ch == '-') y = -1; 14 ch = getchar(); 15 } 16 while(isdigit(ch)) { 17 x = (x << 1) + (x << 3) + ch - '0'; 18 ch = getchar(); 19 } 20 return x * y; 21 } 22
23 inline void change(int l, int r, int d) { 24 int p = pos[l], q = pos[r]; 25 if(p == q) 26 for(int i = l; i <= r; ++i) a[i] += d; 27 else { 28 for(int i = p + 1; i <= q - 1; ++i) add[i] += d; 29 for(int i = l; i <= R[p]; ++i) a[i] += d; 30 for(int i = L[q]; i <= r; ++i) a[i] += d; 31 } 32 } 33
34 int main() { 35 n = read(); 36 for(int i = 1; i <= n; ++i) 37 a[i] = read(); 38 int t = sqrt(n); 39 for(int i = 1; i <= t; ++i) { 40 L[i] = (i - 1) * t + 1; 41 R[i] = i * t; 42 } 43 if(R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n; 44 for(int i = 1; i <= t; ++i) 45 for(int j = L[i]; j <= R[i]; ++j) 46 pos[j] = i; 47 for(int i = 1; i <= n; ++i) { 48 int opt, l, r, c; 49 opt = read(), l = read(), r = read(), c = read(); 50 if(!opt) change(l, r, c); 51 else { 52 int q = pos[r]; 53 cout << a[r] + add[q] << '\n'; 54 } 55 } 56 return 0; 57 }
分块入门2：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std; 4 const int maxn = 50005; 5 int n,blo; 6 int v[maxn], bl[maxn], atag[maxn]; 7 vector<int>ve[505]; 8
9 inline ll read() { 10 ll x = 0, y = 1; 11 char ch = getchar(); 12 while(!isdigit(ch)) { 13 if(ch == '-') y = -1; 14 ch = getchar(); 15 } 16 while(isdigit(ch)) { 17 x = (x << 1) + (x << 3) + ch - '0'; 18 ch = getchar(); 19 } 20 return x * y; 21 } 22
23 inline void reset(int x) { 24 ve[x].clear(); 25 for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++) 26 ve[x].push_back(v[i]); 27 sort(ve[x].begin(),ve[x].end()); 28 } 29
30 inline void add(int a, int b, int c) { 31 for(int i = a; i <= min(bl[a] * blo, b); i++) 32 v[i] += c; 33 reset(bl[a]); 34 if(bl[a] != bl[b]) { 35 for(int i = (bl[b] - 1) * blo + 1; i <= b; i++) 36 v[i] += c; 37 reset(bl[b]); 38 } 39 for(int i =bl[a] + 1; i <= bl[b] - 1; i++) 40 atag[i] +=c; 41 } 42
43 inline int query(int a, int b, int c) { 44 int ans = 0; 45 for(int i = a; i <= min(bl[a] * blo, b); i++) 46 if(v[i] + atag[bl[a]] < c)ans++; 47 if(bl[a] != bl[b]) 48 for(int i = (bl[b] - 1) * blo + 1; i <= b; i++) 49 if(v[i] + atag[bl[b]] < c)ans++; 50 for(int i=bl[a]+1;i<=bl[b]-1;i++) { 51 int x = c - atag[i]; 52 ans += lower_bound(ve[i].begin(), ve[i].end(), x) - ve[i].begin(); 53 } 54 return ans; 55 } 56
57 int main() { 58 n = read(); blo = sqrt(n);//t = sqrt(n);
59 for(int i = 1; i <= n; ++i) v[i] = read();//a[i] = read()
60 for(int i = 1; i <= n; i++) { 61 bl[i] = (i - 1) / blo + 1;//pos[i]
62 ve[bl[i]].push_back(v[i]); 63 } 64 for(int i = 1; i <= bl[n]; i++) 65 sort(ve[i].begin(), ve[i].end()); 66 for(int i = 1; i <= n; i++) { 67 int opt = read(), l = read(), r = read(), d = read(); 68 if(opt == 0) add(l, r, d); 69 if(opt == 1) printf("%d\n", query(l, r, d * d)); 70 } 71 return 0; 72 }
分块入门3：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。
因为要使用set(听说二分有点难卡过去)，所以没写
分块入门4：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，区间求和
传说中的经典操作
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std; 4 const int maxn = 50086; 5 int n, t; 6 ll add[maxn], sum[maxn], a[maxn]; 7 int L[maxn], R[maxn]; 8 int pos[maxn]; 9 int opt, l, r, d; 10
11 inline int read() { 12 int x = 0, y = 1; 13 char ch = getchar(); 14 while(!isdigit(ch)) { 15 if(ch == '-') y = -1; 16 ch = getchar(); 17 } 18 while(isdigit(ch)) { 19 x = (x << 1) + (x << 3) + ch - '0'; 20 ch = getchar(); 21 } 22 return x * y; 23 } 24
25 inline void change(int l, int r, int d) { 26 int p = pos[l], q = pos[r]; 27 if(p == q) { 28 for(int i = l; i <= r; ++i) a[i] += d; 29 sum[p] += (r - l + 1) * d; 30 } 31 else { 32 for(int i = p + 1; i <= q - 1; ++i) add[i] += d; 33 for(int i = l; i <= R[p]; ++i) a[i] += d; 34 sum[p] += (R[p] - l + 1) * d; 35 for(int i = L[q]; i <= r; ++i) a[i] += d; 36 sum[q] += (r - L[q] + 1) * d; 37 } 38 } 39
40 inline ll ask(int l, int r, int mod) { 41 int p = pos[l], q = pos[r]; 42 ll ans = 0; 43 if(p == q) { 44 for(int i = l; i <= r; ++i) ans = (ans + a[i]) % mod; 45 ans = (ans + add[p] * (r - l + 1)) % mod; 46 } 47 else { 48 for(int i = p + 1; i <= q - 1; ++i) 49 ans = (ans + sum[i] + add[i] * (R[i] - L[i] + 1)) % mod; 50 for(int i = l; i <= R[p]; ++i) ans = (ans + a[i]) % mod; 51 ans = (ans + add[p] * (R[p] - l + 1)) % mod; 52 for(int i = L[q]; i <= r; ++i) ans = (ans + a[i]) % mod; 53 ans = (ans + add[q] * (r - L[q] + 1)) % mod; 54 } 55 return ans % mod; 56 } 57
58 int main() { 59 // freopen("asd.in", "r", stdin); 60 // freopen("a.out", "w", stdout);
61 n = read(); t = sqrt(n); 62 for(int i = 1; i <= n; ++i) a[i] = read(); 63 for(int i = 1; i <= t; ++i) { 64 L[i] = (i - 1) * t + 1; 65 R[i] = i * t; 66 } 67 if(R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n; 68 for(int i = 1; i <= t; ++i) 69 for(int j = L[i]; j <= R[i]; ++j) { 70 pos[j] = i; 71 sum[i] += a[j]; 72 } 73 for(int i = 1; i <= n; ++i) { 74 opt = read(), l = read(), r = read(), d = read(); 75 if(!opt) change(l, r, d); 76 else cout << ask(l, r, d + 1) << '\n'; 77 } 78 return 0; 79 }
分块入门5：
给出一个长为 n 的数列 a1…an，以及 n 个操作，操作涉及区间开方，区间求和。
对于区间开方，我们可以想到，对于一个区间的数，经过数次开方后，他们会变为0或1，所以采取一种分块优化的暴力做法，只要每个整块暴力开方后，记录一下元素是否都变成了 0 / 1，区间修改时跳过那些全为 0 / 1 的块即可。
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std; 4 const int maxn = 50086; 5 int n, a[maxn]; 6 int sum[maxn], pos[maxn]; 7 int L[maxn], R[maxn]; 8 int t; 9 bool vis[maxn]; 10 int opt, l, r, c; 11
12 inline int read() { 13 int x = 0, y = 1; 14 char ch = getchar(); 15 while(!isdigit(ch)) { 16 if(ch == '-') y = -1; 17 ch = getchar(); 18 } 19 while(isdigit(ch)) { 20 x = (x << 1) + (x << 3) + ch - '0'; 21 ch = getchar(); 22 } 23 return x * y; 24 } 25
26 inline void check_sqrt(int x) { 27 if(vis[x]) return; 28 vis[x] = 1; 29 sum[x] = 0; 30 for(int i = L[x]; i <= R[x]; ++i) { 31 a[i] = sqrt(a[i]); 32 sum[x] += a[i]; 33 if(a[i] > 1) vis[x] = 0; 34 } 35 } 36
37 inline void change(int l, int r) { 38 int p = pos[l], q = pos[r]; 39 if(p == q) { 40 for(int i = l; i <= r; ++i) { 41 sum[p] -= a[i]; 42 a[i] = sqrt(a[i]); 43 sum[p] += a[i]; 44 } 45 } 46 else { 47 for(int i = p + 1; i <= q - 1; ++i) 48 check_sqrt(i); 49 for(int i = l; i <= R[p]; ++i) { 50 sum[p] -= a[i]; 51 a[i] = sqrt(a[i]); 52 sum[p] += a[i]; 53 } 54 for(int i = L[q]; i <= r; ++i) { 55 sum[q] -= a[i]; 56 a[i] = sqrt(a[i]); 57 sum[q] += a[i]; 58 } 59 } 60 } 61
62 inline int ask(int l, int r) { 63 int ans = 0; 64 int p = pos[l], q = pos[r]; 65 if(p == q) for(int i = l; i <= r; ++i) ans += a[i]; 66 else { 67 for(int i = p + 1; i <= q - 1; ++i) ans += sum[i]; 68 for(int i = l; i <= R[p]; ++i) ans += a[i]; 69 for(int i = L[q]; i <= r; ++i) ans += a[i]; 70 } 71 return ans; 72 } 73
74 int main() { 75 memset(vis, false, sizeof(vis)); 76 n = read(); t = sqrt(n); 77 for(int i = 1; i <= n; ++i) a[i] = read(); 78 for(int i = 1; i <= t; ++i) { 79 L[i] = (i - 1) * t + 1; 80 R[i] = i * t; 81 } 82 if(R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n; 83 for(int i = 1; i <= t; ++i) 84 for(int j = L[i]; j <= R[i]; ++j) { 85 sum[i] += a[j]; 86 pos[j] = i; 87 } 88 for(int i = 1; i <= n; ++i) { 89 opt = read(), l = read(), r = read(), c = read(); 90 if(!opt) change(l, r); 91 else cout << ask(l, r) << '\n'; 92 } 93 return 0; 94 }
分块入门6：
给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问，数据随机生成。
1 #include<bits/stdc++.h>
2 using namespace std; 3 const int maxn = 1e5 + 10; 4 const int maxq = 1e3 + 10; 5 struct enkidu { 6 int s, t; 7 }; 8 int n, a[maxn]; 9 int s[maxn << 1]; 10 int k, m;
11 int opt, l, r, c; 12 vector<int> e[maxq]; 13
14 inline int read() { 15 int x = 0, y = 1; 16 char ch = getchar(); 17 while(!isdigit(ch)) { 18 if(ch == '-') y = -1; 19 ch = getchar(); 20 } 21 while(isdigit(ch)) { 22 x = (x << 1) + (x << 3) + ch - '0'; 23 ch = getchar(); 24 } 25 return x * y; 26 } 27
28 inline enkidu query(int x) { 29 int i = 1; 30 while(x > (int)e[i].size()) 31 x -= (int)e[i].size(), i++; 32 return (enkidu){i, x - 1}; 33 } 34
35 inline void rebuild() {
36 int top = 0; 37 for(int i = 1; i <= m; ++i) { 38 int z = e[i].size(); 39 for(int j = 0; j < z; ++j) 40 s[++top] = e[i][j]; 41 e[i].clear(); 42 } 43 k = sqrt(top), m = (top - 1) / k + 1; 44 for(int i = 1; i <= top; ++i) 45 e[(i - 1) / k + 1].push_back(s[i]); 46 } 47
48 inline void change(int l, int r) { 49 enkidu x = query(l); 50 int s = x.s, t = x.t; 51 e[s].insert(e[s].begin() + t, r); 52 if((int)e[s].size() > 20 * k) 53 rebuild(); 54 } 55
56 int main() { 57 n = read(); 58 for(int i = 1; i <= n; ++i) a[i] = read(); 59 k = sqrt(n), m = (n - 1) / k + 1;
60 for(int i = 1; i <= n; ++i) 61 e[(i - 1) / k + 1].push_back(a[i]); 62 for(int i = 1; i <= n; ++i) { 63 opt = read(), l = read(), r = read(), c = read(); 64 if(!opt) change(l, r); 65 else { 66 enkidu x = query(r); 67 int s = x.s, t = x.t; 68 cout << e[s][t] << '\n'; 69 } 70 } 71 return 0; 72 }
分块入门7：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间乘法，区间加法，单点询问。
比较难处理的是乘法与加法的优先级问题，对于加法，我们直接累加，对于乘法，我们在加法标记和乘法标记上都乘上要乘的数就可以保证优先级的正确性（这是很显然的）
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std; 4 const int maxn = 100086; 5 const int mod = 10007; 6 int n, t; 7 int a[maxn]; 8 int add[maxn], mul[maxn]; 9 int pos[maxn]; 10 int opt, l, r, c; 11
12 inline ll read() { 13 ll x = 0, y = 1; 14 char ch = getchar(); 15 while(!isdigit(ch)) { 16 if(ch == '-') y = -1; 17 ch = getchar(); 18 } 19 while(isdigit(ch)) { 20 x = (x << 1) + (x << 3) + ch - '0'; 21 ch = getchar(); 22 } 23 return x * y; 24 } 25
26 inline void reset(int x) { 27 for(int i = (x - 1) * t + 1; i <= min(n, x * t); ++i) 28 a[i] = (a[i] * mul[x] + add[x]) % mod; 29 add[x] = 0, mul[x] = 1; 30 } 31
32 inline void change(int flag, int l, int r, int c) { 33 reset(pos[l]); 34 for(int i = l; i <= min(pos[l] * t, r); ++i) { 35 if(!flag) a[i] += c; 36 else a[i] *= c; 37 a[i] %= mod; 38 } 39 if(pos[l] != pos[r]) { 40 reset(pos[r]); 41 for(int i = (pos[r] - 1) * t + 1; i <= r; ++i) { 42 if(!flag) a[i] += c; 43 else a[i] *= c; 44 a[i] %= mod; 45 } 46 } 47 for(int i = pos[l] + 1; i <= pos[r] - 1; ++i) { 48 if(!flag) add[i] = (add[i] + c) % mod; 49 else if(flag) { 50 add[i] = add[i] * c % mod; 51 mul[i] = mul[i] * c % mod; 52 } 53 } 54 } 55
56 int main() { 57 n = read(); t = sqrt(n); 58 for(int i = 1; i <= n; ++i) a[i] = read(); 59 for(int i = 1; i <= n; ++i) 60 pos[i] = (i - 1) / t + 1; 61 for(int i = 1; i <= pos[n]; ++i) mul[i] = 1; 62 for(int i = 1; i <= n; ++i) { 63 opt = read(), l = read(), r = read(), c = read(); 64 if(opt == 2) cout << (a[r] * mul[pos[r]] + add[pos[r]]) % mod << '\n'; 65 else change(opt, l, r, c); 66 } 67 return 0; 68 }
分块入门8：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。
区间修改和询问操作，遇到以后建议线段树（逃）
1 #include<bits/stdc++.h>
2 using namespace std; 3 const int maxn = 100086; 4 int n, t; 5 int a[maxn]; 6 int pos[maxn], tag[maxn]; 7 int l, r, c; 8
9 inline int read() { 10 int x = 0, y = 1; 11 char ch = getchar(); 12 while(!isdigit(ch)) { 13 if(ch == '-') y = -1; 14 ch = getchar(); 15 } 16 while(isdigit(ch)) { 17 x = (x << 1) + (x << 3) + ch - '0'; 18 ch = getchar(); 19 } 20 return x * y; 21 } 22
23 inline void reset(int x) { 24 if(tag[x] == -1) return; 25 for(int i = (x - 1) * t + 1; i <= x * t; ++i) 26 a[i] = tag[x]; 27 tag[x] = -1; 28 } 29
30 inline int sovle(int l, int r, int c) { 31 int ans = 0; 32 reset(pos[l]); 33 for(int i = l; i <= min(pos[l] * t, r); ++i) { 34 if(a[i] != c) a[i] = c; 35 else ans++; 36 } 37 if(pos[l] != pos[r]) { 38 reset(pos[r]); 39 for(int i = (pos[r] - 1) * t + 1; i <= r; ++i) { 40 if(a[i] != c) a[i] = c; 41 else ans++; 42 } 43 } 44 for(int i = pos[l] + 1; i <= pos[r] - 1; ++i) { 45 if(tag[i] != -1) { 46 if(tag[i] != c) tag[i] = c; 47 else ans += t; 48 } 49 else { 50 for(int j = (i - 1) * t + 1; j <= i * t; ++j) { 51 if(a[j] != c) a[j] = c; 52 else ans++; 53 } 54 tag[i] = c; 55 } 56 } 57 return ans; 58 } 59
60 int main() { 61 memset(tag, -1, sizeof(tag)); 62 n = read(); t = sqrt(n); 63 for(int i = 1; i <= n; ++i) a[i] = read(); 64 for(int i = 1; i <= n; ++i) 65 pos[i] = (i - 1) / t + 1; 66 for(int i = 1; i <= n; ++i) { 67 l = read(), r = read(), c = read(); 68 cout << sovle(l, r, c) << '\n'; 69 } 70 return 0; 71 }
分块入门9：
给出一个长为 n 的数列，以及 n 个操作，操作涉及询问区间的最小众数。
分块最经典的区间众数操作，因为不具有区间相加性，无法使用线段树或是树状数组完成。
当然学了莫队就很简单，不会莫队（比如我），就老老实实分块吧….
首先先离散化处理一下
接着枚举预处理出任意一个区间[l, r]的众数，也就是任意一个块的左端点到其他块的右端点的众数（看了代码就懂了系列），非常显然的使用数组记录每个数出现过的次数，然后再枚举一遍，求出众数
对于每一次询问的区间[l, r]，我们可以和明显的发现，大区间的众数存在于大区间内完整的块里或是左右两端不完整的块里
对于完整的块里，显然我们已经与处理过了，直接询问即可，所以我们需要快速求出不完整的块中的区间众数
然后可以发现我们上面进行了离散化，所以我们在离散时动动手脚就很好办了，对于每数，使用vector存每一次出现的位置，
然后把这个数存在的左端点和右端点二分再相减就可以求出这个数在区间里出现的次数，也就是求区间内第一个大于这个数的位置(upper_bound)和第一个大于等于这个数的位置(lower_bound)
再相减即可
剩下的直接看代码即可
1 #include<bits/stdc++.h>
2 using namespace std; 3 const int maxn = 50005; 4 int f[505][505]; 5 int a[maxn], pos[maxn]; 6 int val[maxn], cnt[maxn]; 7 int n, l, r, t, id; 8 map<int, int> mp; 9 vector<int> v[maxn]; 10
11 inline int read() { 12 int x = 0, y = 1; 13 char ch = getchar(); 14 while(!isdigit(ch)) { 15 if(ch == '-') y = -1; 16 ch = getchar(); 17 } 18 while(isdigit(ch)) { 19 x = (x << 1) + (x << 3) + ch - '0'; 20 ch = getchar(); 21 } 22 return x * y; 23 } 24
25 inline void pre(int x) { 26 memset(cnt, 0, sizeof(cnt)); 27 int maxx = 0 , ans = 0; 28 for(int i = (x - 1) * t + 1; i <= n; ++i) { 29 cnt[a[i]]++; 30 int p = pos[i]; 31 if(cnt[a[i]] > maxx || ((cnt[a[i]] == maxx) && val[a[i]] < val[ans])) 32 ans = a[i], maxx = cnt[a[i]]; 33 f[x][p] = ans; 34 } 35 } 36
37 inline int query_cnt(int l, int r, int x) { 38 int k = upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l); 39 return k; 40 } 41
42 inline int query(int l, int r) { 43 int ans, maxx = -1000000; 44 ans = f[pos[l] + 1][pos[r] - 1]; 45 maxx = query_cnt(l, r, ans); 46 for(int i = l; i <= min(pos[l] * t, r); ++i) { 47 int k = query_cnt(l, r, a[i]); 48 if(k > maxx || (k == maxx && val[ans] > val[a[i]])) 49 ans = a[i], maxx = k; 50 } 51 if(pos[l] != pos[r]) { 52 for(int i = (pos[r] - 1) * t + 1; i <= r; ++i) { 53 int k = query_cnt(l, r, a[i]); 54 if(k > maxx || (k == maxx && val[ans] > val[a[i]])) 55 ans = a[i], maxx = k; 56 } 57 } 58 return ans; 59 } 60
61 int main() { 62 n = read(); t = 200; 63 for(int i = 1; i <= n; ++i) { 64 a[i] = read(); 65 if(!mp[a[i]]) { 66 mp[a[i]] = ++id; 67 val[id] = a[i]; 68 } 69 a[i] = mp[a[i]]; 70 v[a[i]].push_back(i); 71 } 72 for(int i = 1; i <= n; ++i) pos[i] = (i - 1) / t + 1; 73 for(int i = 1; i <= pos[n]; ++i) pre(i); 74 for(int i = 1; i <= n; ++i) { 75 l = read(), r = read(); 76 if(l > r) swap(l, r); 77 cout << val[query(l, r)] << '\n'; 78 } 79 return 0; 80 }
已下是毒瘤题！代码毒瘤！
题面：给定一个长度为n的序列，求有多少个区间[l, r]满足：区间内每个数都出现奇数次
解决的主要思想是：
给每个数x赋上一个随机权值Hx，这样就能把问题转化成：
求有多少个区间，使得区间内的所有数权值异或和等于区间内出现过的数权值异或和
思考为什么会有这样的转化：
首先我们可以知道，对于有着相同权值的数，若出现了多次肯定会不断抵消。
当一个数x出现了奇数次时，将区间内所有的x异或起来，得到的仍是x，这样也就是说，若区间内的所有数异或起来等于区间内出现过的
数的权值异或和
就说明这个区间内每个数都出现了奇数次
接下来思考基于这个思想的具体算法：
记prei表示i这个数上一次出现的位置。
那么问题转化为：枚举区间右端点𝑟，每次两个操作：
1. 给区间 [1, prear]异或一个数；
2. 询问[1, r]中为0的数的个数
为什么可以这样呢，注意我们的prei的含义：它表示的是这个数上次出现的位置
我们考虑我们将要插入一个数x，若[1, prear]之间异或上这个x的权值Hx，然后里面部分数变成了0，说明了什么：
说明了在区间[1, prear]中，x这个数出现了奇数次，这样我们枚举右端点r，然后每次这样操作，再查询0的个数，用一个变量ans累加答案
最后得到的就是有多少个区间满足每个数出现了奇数次了
然后考虑代码实现：
因为数据范围可能较大，所以我们素质离散一下
同时为了避免重复，我们rand出的权值可能会很大，所以我们要注意使用unsigned long long
对于区间异或我们可以打标记，区间询问即为统计值为标记的数的个数。
同时关于哪个数赋了什么权值，我们也需要存储，比如说我们可以用STL的map来实现
但是众所周知map有O(logn)的复杂度，而且即便我们如此取权值也可能会有重复
因此我们可以选择毒瘤hash
遇到不完整的块的时候，直接暴力处理过后把块的信息重新统计即可
这样复杂度就是O(n√n)
但是口胡算法并没什么用处，代码实现还是相当的毒瘤的，某个写std的人如是说道：“哎我当初在干什么”“哎我都写了什么”
所以具体细节还是代码见吧
1 #include<bits/stdc++.h>
2 #define ll long long
3 #define uint unsigned int
4 #define ull unsigned long long
5 using namespace std; 6 const int maxn = 2e5 + 10; 7 const int kuai = 510; 8 const int MOD = 2339;//uss it to hash
9 struct shiki { 10 int lin[MOD + 5], net[MOD + 5], len; 11 int hid[MOD + 5], cnt[MOD + 5], id; 12 ull to[MOD + 5]; 13 inline void clear_() { 14 len = id = 0; 15 memset(lin, 0, sizeof(lin)); 16 memset(hid, 0, sizeof(hid)); 17 } 18 inline void insert(int xx, ull yy, int v) { 19 to[++len] = yy; 20 net[len] = lin[xx]; 21 cnt[len] = v; 22 lin[xx] = len; 23 } 24 //最初没有插入任何数，对每个单独的数组成的只有一个区间的数来说，出现次数都是奇数次，因此赋上(r-l+1)的初值 25 //cnt[i]表示对于某个数出现了多少次，下标i对应在链中的位置(大概)，参考邻接表
26 inline void init(int L, int R) {//最初
27 insert(0, 0, R - L + 1); 28 } 29 inline void reset() {//reset：重置, 在将块重构时，因为直接memset的复杂度可能是错误的，所以每次把tot归零
30 id++, len = 0;//同时用一个id表示最新版本是哪个版本以方便把后续节点安排上
31 } 32 inline int place(int x) {//hid数组表示对于一个取模后的数hx,它是哪一个版本的，方便把它更新掉
33 if(hid[x] == id) return lin[x];//若当前值在新的表中出现过，return head[x]
34 else { 35 hid[x] = id;//else 把当前值插入新的hash表中
36 return lin[x] = 0; 37 } 38 } 39 inline void add(ull x) { 40 int hx = x % MOD; 41 for(int i = place(hx); i; i = net[i]) 42 if(to[i] == x) {//表示在这个新的hash块里是否存在和取模后的x值相等的，若相等，则说明插入后to[i]的数量++
43 cnt[i]++;//则这个数的数量++
44 return; 45 } 46 insert(hx, x, 1);//若未找到，将x插入
47 } 48 inline int query_cnt(ull x) {//询问针对完整的块tag表示这些块异或了数次后的值
49 int hx = x % MOD; 50 for(int i = place(hx); i; i = net[i])//搜索hash值为hx的数，若此前有和这个值相等的数，则说明异或上x后，可以得到0，也就是说在x前，这个数出现了奇数次
51 if(to[i] == x) return cnt[i];//则符合要求，输出这个数的个数
52 return 0; 53 } 54 }hash[kuai]; 55 int a[maxn]; 56 ull H[maxn];//H数组表示赋上的随机权值
57 int pos[maxn], L[maxn], R[maxn]; 58 int b[maxn], c[maxn], tot = 0; 59 ull tag[kuai];//对于整个的块表示异或了数次后的值
60 ull cag[maxn];//对于非整块的表示异或了数次后的值
61 int n, m, t; 62 int last[maxn];//数a[i]上一次出现的位置
63
64 inline int read() { 65 int x = 0, y = 1; 66 char ch = getchar(); 67 while(!isdigit(ch)) { 68 if(ch == '-') y = -1; 69 ch = getchar(); 70 } 71 while(isdigit(ch)) { 72 x = (x << 1) + (x << 3) + ch - '0'; 73 ch = getchar(); 74 } 75 return x * y; 76 } 77
78 inline int query_lisan(int x) { 79 return lower_bound(b + 1, b + tot + 1, x) - b; 80 } 81
82 inline ull irand() { 83 ull res = 0; 84 for(int i = 1; i <= 5; ++i) res = (((res + rand()) * rand()) << 15) + rand(); 85 return res; 86 } 87
88 inline void deal_xor(int x, ull hx) { 89 if(!x) return; 90 int p = pos[x]; 91 for(int i = 1; i < p; ++i) tag[i] ^= hx; 92 hash[p].reset(); 93 for(int i = L[p]; i <= x; ++i) { 94 cag[i] ^= hx; 95 hash[p].add(cag[i]); 96 } 97 for(int i = x + 1; i <= R[p]; ++i) hash[p].add(cag[i]); 98 } 99
100 inline int query(int x) { 101 int p = pos[x], res = 0; 102 for(int i = 1; i < p; ++i) res += hash[i].query_cnt(tag[i]); 103 for(int i = L[p]; i <= x; ++i) 104 if(cag[i] == tag[p]) res++; 105 return res; 106 } 107
108 int main() { 109 n = read(); t = sqrt(n); 110 for(int i = 1; i <= n; ++i) { 111 a[i] = read(); 112 c[i] = a[i]; 113 } 114 //离散化
115 sort(c + 1, c + n + 1); 116 for(int i = 1; i <= n; ++i) 117 if(i == 1 || c[i - 1] != c[i]) 118 b[++tot] = c[i]; 119 for(int i = 1; i <= n; ++i) { 120 int pal = query_lisan(a[i]); 121 c[i] = pal;//c数组为离散后的a数组
122 } 123
124 //check 125 // for(int i = 1; i <= n; ++i) cout << c[i] << ' '; 126 // cout << '\n'; 127
128
129 //分块
130 for(int i = 1; i <= t; ++i) { 131 L[i] = (i - 1) * t + 1; 132 R[i] = i * t; 133 } 134 if(R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n; 135 for(int i = 1; i <= t; ++i) 136 for(int j = L[i]; j <= R[i]; ++j) 137 pos[j] = i; 138 ll ans = 0; 139 //start to answer questions
140 for(int i = 1; i <= tot; ++i) H[i] = irand();//赋一个随机权值
141 for(int i = 1; i <= t; ++i) hash[i].clear_(), hash[i].init(L[i], R[i]); 142 for(int i = 1; i <= n; ++i) { 143 int pre = last[c[i]]; last[c[i]] = i; 144 deal_xor(pre, H[c[i]]); 145 ans += query(i); 146 } 147 printf("%lld\n", ans); 148 return 0; 149 }
今天的文章分块入门1~9_5分成2份有几种分法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：http://bianchenghao.cn/49312.html
