square root algorithm根号n算法

image.png

image.png
image.png
image.png

mo`s algorithm莫队

https://zhuanlan.zhihu.com/p/115243708
https://www.cnblogs.com/WAMonster/p/10118934.html
https://www.luogu.com.cn/blog/DPair2005/talk-talk-bruh-forces-in-oi

例题：奇数

image.png
image.png
image.png

询问离线后，排序的不同优化

  1. // 询问离线后，排序的不同优化
  3. // 用时5038ms
  4. // 左端点在同一个块里的询问 ，我们按它们的 右端点升序排序
  5. // 否则我们按它们的 左端点升序排序
  6. struct node{
  7.     int l, r, idx;
  8.     bool operator< (const node &W) const{
  9.         if (l / B == W.l / B) return r < W.r;
  10.         return l < W.l;
  11.     }
  12. }q[N];
  15. // 用时4879ms
  16. // 不难发现，排序的时候，我们每一个块都是按右端点升序排序的，
  17. // 这里显然只需要保证右端点单调就行了，所以降序排序也是对的。
  18. struct node{
  19.     int l, r, idx;
  20.     bool operator< (const node &W) const{
  21.         if (l / B == W.l / B) return r > W.r;
  22.         return l < W.l;
  23.     }
  24. }q[N];
  27. // 用时3322ms
  28. // 然后我们又不难发现，每一次我们处理完左端点在某一个块中的所有询问后，
  29. // 右端点此时应该在序列的靠右端，处理下一个块时又回到最左端了，然后又不断往右，有一些浪费。
  30. // 所以我们考虑引入“奇偶块排序”，即对于左端点编号为奇数的块升序，左端点编号为偶数的块降序排序。
  32. // 关于小技巧的说明:对于两个区间交替的过程中,
  33. // r如果先回来,那么部分点就会被扫两次,
  34. // 那么对于r一正一逆的排序,就可以避免重复的情况
  35. struct node{
  36.     int l, r, idx;
  37.     bool operator< (const node &W) const{
  38.         if (l / B != W.l / B) return l < W.l;
  39.         if (l / B & 1) return r < W.r;
  40.         return r > W.r;
  41.     }
  42. }q[N];

没有离散化的AC代码，数据有点锅

  1. // 没有离散化的
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. const int N = 1e5 + 10;
  9. int a[N], cnt[N], n, m;
  10. int B;
  11. int l = 1, r = 0;
  12. int ans[N], cur;
  14. struct node{
  15.     int l, r, idx;
  16.     bool operator< (const node &W) const{
  17.         //if (l / B == W.l / B) return r > W.r;
  18.         //return l < W.l;
  20.         if (l / B != W.l / B) return l < W.l;
  21.         if (l / B & 1) return r < W.r;
  22.         return r > W.r;
  23.     }
  24. }q[N];
  26. void add(int p){
  27.     cnt[a[p]]++;
  28.     if (cnt[a[p]] % 2 == 0) cur--;
  29.     else cur++;
  30. }
  32. void del(int p){
  33.     cnt[a[p]]--;
  34.     if (cnt[a[p]] % 2 == 0) cur--;
  35.     else cur++;
  36. }
  38. int main(){
  39.     cin >> n;
  40.     B = sqrt(n);
  41.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  43.     cin >> m;
  44.     for (int i = 0; i < m; i++){
  45.         scanf("%d%d", &q[i].l, &q[i].r);
  46.         q[i].idx = i;
  47.     }
  49.     sort(q, q + m);
  51.     for (int i = 0; i < m; i++){
  52.         while (l > q[i].l) add(--l);
  53.         while (r < q[i].r) add(++r);
  54.         while (l < q[i].l) del(l++);
  55.         while (r > q[i].r) del(r--);
  56.         ans[q[i].idx] = cur;
  57.     }
  59.     for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  61.     return 0;
  62. }

加入离散化后的AC代码

  1. // 加入离散化
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. const int N = 1e5 + 10;
  9. int a[N], cnt[N], n, m;
  10. int B;
  11. int l = 1, r = 0;
  12. int ans[N], cur;
  13. int lsh[N];
  15. struct node{
  16.     int l, r, idx;
  17.     bool operator< (const node &W) const{
  18.         if (l / B != W.l / B) return l < W.l;
  19.         if (l / B & 1) return r < W.r;
  20.         return r > W.r;
  21.     }
  22. }q[N];
  24. void add(int p){
  25.     cnt[a[p]]++;
  26.     if (cnt[a[p]] % 2 == 0) cur--;
  27.     else cur++;
  28. }
  30. void del(int p){
  31.     cnt[a[p]]--;
  32.     if (cnt[a[p]] % 2 == 0) cur--;
  33.     else cur++;
  34. }
  36. int main(){
  37.     cin >> n;
  38.     B = sqrt(n);
  39.     for (int i = 1; i <= n; i++){
  40.         scanf("%d", &a[i]);
  41.         lsh[i] = a[i];
  42.     }
  44.     sort(lsh + 1, lsh + 1 + n);
  45.     int num = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
  46.     for (int i = 1; i <= n; i++)
  47.         a[i] = lower_bound(lsh+1, lsh+num+1, a[i]) - lsh;  //解决掉a[i]<0的问题
  49.     cin >> m;
  50.     for (int i = 0; i < m; i++){
  51.         scanf("%d%d", &q[i].l, &q[i].r);
  52.         q[i].idx = i;
  53.     }
  55.     sort(q, q + m);
  57.     for (int i = 0; i < m; i++){
  58.         while (l > q[i].l) add(--l);
  59.         while (r < q[i].r) add(++r);
  60.         while (l < q[i].l) del(l++);
  61.         while (r > q[i].r) del(r--);
  62.         ans[q[i].idx] = cur;
  63.     }
  65.     for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  67.     return 0;
  68. }

加入快读，用时3306ms

  1. // 使用快读
  2. // 用时3306ms
  4. #include <bits/stdc++.h>
  6. using namespace std;
  8. const int N = 1e5 + 10;
  10. int a[N], cnt[N], n, m;
  11. int B;
  12. int l = 1, r = 0;
  13. int ans[N], cur;
  14. int lsh[N];
  16. inline int read(){
  17.     int f = 1, x = 0;
  18.     char c = getchar();
  19.     while (c < '0' || c > '9'){
  20.         if (c == '-') f = -1;
  21.         c = getchar();
  22.     }
  24.     while (c >= '0' && c <= '9'){
  25.         x = x * 10 + c - '0';
  26.         c = getchar();
  27.     }
  29.     return f * x;
  30. }
  32. struct node{
  33.     int l, r, idx;
  34.     bool operator< (const node &W) const{
  35.         //if (l / B == W.l / B) return r < W.r;
  36.         //return l < W.l;
  38.         if (l / B != W.l / B) return l < W.l;
  39.         if (l / B & 1) return r < W.r;
  40.         return r > W.r;
  41.     }
  42. }q[N];
  44. void add(int p){
  45.     cnt[a[p]]++;
  46.     if (cnt[a[p]] % 2 == 0) cur--;
  47.     else cur++;
  48. }
  50. void del(int p){
  51.     cnt[a[p]]--;
  52.     if (cnt[a[p]] % 2 == 0) cur--;
  53.     else cur++;
  54. }
  56. int main(){
  57.     n = read();
  58.     B = sqrt(n);
  59.     for (int i = 1; i <= n; i++){
  60.         a[i] = read();
  61.         lsh[i] = a[i];
  62.     }
  64.     sort(lsh + 1, lsh + 1 + n);
  65.     int num = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
  66.     for (int i = 1; i <= n; i++)
  67.         a[i] = lower_bound(lsh+1, lsh+num+1, a[i]) - lsh;  //解决掉a[i]<0的问题
  69.     m = read();
  70.     for (int i = 0; i < m; i++){
  71.         q[i].l = read(); q[i].r = read();
  72.         q[i].idx = i;
  73.     }
  75.     sort(q, q + m);
  77.     for (int i = 0; i < m; i++){
  78.         while (l > q[i].l) add(--l);
  79.         while (r < q[i].r) add(++r);
  80.         while (l < q[i].l) del(l++);
  81.         while (r > q[i].r) del(r--);
  82.         ans[q[i].idx] = cur;
  83.     }
  85.     for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  87.     return 0;
  88. }

加入inline，用时2606ms

在 c/c++ 中，为了解决一些频繁调用的小函数大量消耗栈空间（栈内存）的问题，特别的引入了 inline 修饰符，表示为内联函数。栈空间就是指放置程序的局部数据（也就是函数内数据）的内存空间。

  1. // 使用inline
  2. // 用时2606ms
  4. #include <bits/stdc++.h>
  6. using namespace std;
  8. const int N = 1e5 + 10;
  10. int a[N], cnt[N], n, m;
  11. int B;
  12. int l = 1, r = 0;
  13. int ans[N], cur;
  14. int lsh[N];
  16. inline int read(){
  17.     int f = 1, x = 0;
  18.     char c = getchar();
  19.     while (c < '0' || c > '9'){
  20.         if (c == '-') f = -1;
  21.         c = getchar();
  22.     }
  24.     while (c >= '0' && c <= '9'){
  25.         x = x * 10 + c - '0';
  26.         c = getchar();
  27.     }
  29.     return f * x;
  30. }
  32. struct node{
  33.     int l, r, idx;
  34.     bool operator< (const node &W) const{
  35.         //if (l / B == W.l / B) return r < W.r;
  36.         //return l < W.l;
  38.         if (l / B != W.l / B) return l < W.l;
  39.         if (l / B & 1) return r < W.r;
  40.         return r > W.r;
  41.     }
  42. }q[N];
  44. inline void add(int p){
  45.     cnt[a[p]]++;
  46.     if (cnt[a[p]] % 2 == 0) cur--;
  47.     else cur++;
  48. }
  50. inline void del(int p){
  51.     cnt[a[p]]--;
  52.     if (cnt[a[p]] % 2 == 0) cur--;
  53.     else cur++;
  54. }
  56. int main(){
  57.     n = read();
  58.     B = sqrt(n);
  59.     for (int i = 1; i <= n; i++){
  60.         a[i] = read();
  61.         lsh[i] = a[i];
  62.     }
  64.     sort(lsh + 1, lsh + 1 + n);
  65.     int num = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
  66.     for (int i = 1; i <= n; i++)
  67.         a[i] = lower_bound(lsh+1, lsh+num+1, a[i]) - lsh;  //解决掉a[i]<0的问题
  69.     m = read();
  70.     for (int i = 0; i < m; i++){
  71.         q[i].l = read(); q[i].r = read();
  72.         q[i].idx = i;
  73.     }
  75.     sort(q, q + m);
  77.     for (int i = 0; i < m; i++){
  78.         while (l > q[i].l) add(--l);
  79.         while (r < q[i].r) add(++r);
  80.         while (l < q[i].l) del(l++);
  81.         while (r > q[i].r) del(r--);
  82.         ans[q[i].idx] = cur;
  83.     }
  85.     for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  87.     return 0;
  88. }

加入分块，用时2529ms

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  7. int a[N], cnt[N], n, m;
  8. int B;
  9. int l = 1, r = 0;
  10. int ans[N], cur;
  11. int lsh[N];
  12. int bel[N];
  14. inline int read(){
  15.     int f = 1, x = 0;
  16.     char c = getchar();
  17.     while (c < '0' || c > '9'){
  18.         if (c == '-') f = -1;
  19.         c = getchar();
  20.     }
  22.     while (c >= '0' && c <= '9'){
  23.         x = x * 10 + c - '0';
  24.         c = getchar();
  25.     }
  27.     return f * x;
  28. }
  30. // [l, r]这个区间，进行查找
  31. // bel[l] bel[W.l]根据所在的块进行区分
  32. struct node{
  33.     int l, r, idx;
  34.     bool operator< (const node &W) const{
  35.         if (bel[l] != bel[W.l]) return bel[l] < bel[W.l];
  36.         if (bel[l] & 1) return r < W.r;
  37.         return r > W.r;
  38.     }
  39. }q[N];
  41. inline void add(int p){
  42.     cnt[a[p]]++;
  43.     if (cnt[a[p]] % 2 == 0) cur--;
  44.     else cur++;
  45. }
  47. inline void del(int p){
  48.     cnt[a[p]]--;
  49.     if (cnt[a[p]] % 2 == 0) cur--;
  50.     else cur++;
  51. }
  53. int main(){
  54.     n = read();
  55.     B = sqrt(n);
  57.     // 分块
  58.     for (int i = 1; i <= n; i++) bel[i] = (i - 1) / B + 1;
  60.     for (int i = 1; i <= n; i++){
  61.         a[i] = read();
  62.         lsh[i] = a[i];
  63.     }
  65.     sort(lsh + 1, lsh + 1 + n);
  66.     int num = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
  67.     for (int i = 1; i <= n; i++)
  68.         a[i] = lower_bound(lsh+1, lsh+num+1, a[i]) - lsh;  //解决掉a[i]<0的问题
  70.     m = read();
  71.     for (int i = 0; i < m; i++){
  72.         q[i].l = read(); q[i].r = read(); q[i].idx = i;
  73.     }
  75.     sort(q, q + m);
  77.     for (int i = 0; i < m; i++){
  78.         while (l > q[i].l) add(--l);
  79.         while (r < q[i].r) add(++r);
  80.         while (l < q[i].l) del(l++);
  81.         while (r > q[i].r) del(r--);
  82.         ans[q[i].idx] = cur;
  83.     }
  85.     for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  87.     return 0;
  88. }


例题：索引

image.png
image.png
image.png

这道题目，本意是二分，我们在处理多次区间修改的过程中，可以用分块处理

  1. // 分块
  2. #include <bits/stdc++.h>
  4. using namespace std;
  6. const int N = 1e7 + 10;
  8. int k, n, a[N];
  9. int bel[N], tag[N];
  10. int B;
  12. inline int read(){
  13.     int f = 1, x = 0;
  14.     char c = getchar();
  15.     while (c < '0' || c > '9'){
  16.         if (c == '-') f = -1;
  17.         c = getchar();
  18.     }
  20.     while (c >= '0' && c <= '9'){
  21.         x = x * 10 + c - '0';
  22.         c = getchar();
  23.     }
  25.     return f * x;
  26. }
  28. // 核心是这个环节，特别有趣
  29. // 体现了O(n * sqrt(n))的思想
  30. void update(int l, int r, int c){
  31.     for (int i = l; i <= min(bel[l] * B, r); i++) a[i] += c;
  32.     if (bel[l] != bel[r]) for (int i = (bel[r]-1) * B + 1; i <= r; i++) a[i] += c;
  34.     for (int i = bel[l] + 1; i <= bel[r] - 1; i++) tag[i] += c;
  35. }
  37. void ask(){
  38.     int l = 1, r = n, best = 1;
  39.     while (l < r){
  40.         int mid = (l + r + 1) >> 1;
  41.         if (a[mid] + tag[bel[mid]] <= 0) l = mid, best = mid;
  42.         else r = mid - 1;
  43.     }
  45.     if (a[best] + tag[bel[best]] == 0) puts("YES");
  46.     else puts("NO");
  48.     //for (int i = 1; i <= n; i++) printf("%d ", a[i]);
  49.     //puts("");
  50. }
  52. int main(){
  53.     k = read(), n = read();
  54.     B = sqrt(n);
  55.     for (int i = 1; i <= n; i++){
  56.         a[i] = read() - i;
  57.         bel[i] = (i - 1) / B + 1;
  58.     }
  60.     ask();
  62.     for (int i = 2; i <= k; i++){
  63.         int l = read(), r = read(), c = read();
  64.         update(l, r, c);
  65.         ask();
  66.     }
  68.     return 0;
  69. }