树状数组

241. 楼兰图腾

在完成了分配任务之后，西部 314 来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)，其中 y1∼yn 是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤iyj,yj如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤iyk，则称这三个点构成 ∧ 图腾;
西部314 想知道，这 n 个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
输入格式
第一行一个数 n。
第二行是 n 个数，分别代表 y1，y2,…,yn。
输出格式
两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。
数据范围
对于所有数据，n≤200000，且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。
输入样例：
5
1 5 3 2 4
输出样例：
3 4
image.png
image.png

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  5. using namespace std;
  7. const int N = 2000010;
  9. typedef long long LL;
  11. int n;
  12. //t[i]表示树状数组i结点覆盖的范围和
  13. int a[N], t[N];
  14. //Lower[i]表示左边比第i个位置小的数的个数
  15. //Greater[i]表示左边比第i个位置大的数的个数
  16. int Lower[N], Greater[N];
  18. //返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
  19. int lowbit(int x)
  20. {
  21.     return x & -x;
  22. }
  24. //将序列中第x个数加上k。
  25. void add(int x, int k)
  26. {
  27.     for(int i = x; i <= n; i += lowbit(i)) t[i] += k;
  28. }
  29. //查询序列前x个数的和
  30. int ask(int x)
  31. {
  32.     int sum = 0;
  33.     for(int i = x; i; i -= lowbit(i)) sum += t[i];
  34.     return sum;
  35. }
  37. int main()
  38. {
  40.     scanf("%d", &n);
  41.     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
  43.     //从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数
  44.     for(int i = 1; i <= n; i++)
  45.     {
  46.         int y = a[i]; //第i个数
  48.         //在前面已加入树状数组的所有数中统计在区间[1, y - 1]的数字的出现次数
  49.         Lower[i] = ask(y - 1); 
  51.         //在前面已加入树状数组的所有数中统计在区间[y + 1, n]的数字的出现次数
  52.         Greater[i] = ask(n) - ask(y);
  54.         //将y加入树状数组，即数字y出现1次
  55.         add(y, 1);
  56.     }
  58.     //清空树状数组，从右往左统计每个位置右边比第i个数y小的数的个数、以及大的数的个数
  59.     memset(t, 0, sizeof t);
  61.     LL resA = 0, resV = 0;
  62.     //从右往左统计
  63.     for(int i = n; i >= 1; i--)
  64.     {
  65.         int y = a[i];
  66.         resA += (LL)Lower[i] * ask(y - 1);
  67.         resV += (LL)Greater[i] * (ask(n) - ask(y));
  69.         //将y加入树状数组，即数字y出现1次
  70.         add(y, 1);
  71.     }
  73.     printf("%lld %lld\n", resV, resA);
  75.     return 0;
  76. }
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. typedef long long LL;
  7. using namespace std;
  8. const int N = 2e5 + 10;
  9. int a[N], tr[N];
  10. int n;
  11. LL Greate[N], Lower[N];
  13. int lowbit(int x) {
  14.     return x & -x;
  15. }
  17. void update(int x, int c)  // 位置x加c
  18. {
  19.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
  20. }
  22. int query(int x)  // 返回前x个数的和
  23. {
  24.     int res = 0;
  25.     for (int i = x; i; i -= lowbit(i)) res += tr[i];
  26.     return res;
  27. }
  30. int main() {
  31.     cin >> n;
  32.     for (int i = 1; i <= n; i++) {
  33.         cin >> a[i];
  34.     }
  35.     for (int i = 1; i <= n; i++) {
  36.         int y = a[i];
  37.         Greate[i] = query(n) - query(y);
  38.         Lower[i] = query(y - 1);
  39.         update(y, 1);
  40.     }
  41.     memset(tr, 0, sizeof tr);
  42.     LL resA = 0, resV = 0;
  43.     for (int i = n; i >= 1; i--) {
  44.         int y = a[i];
  45.         resA += Lower[i] * query(y - 1);
  46.         resV += Greate[i] * (query(n) - query(y));
  47.         update(y, 1);
  48.     }
  49.     cout << resV << " " << resA << endl;
  51. }

242. 一个简单的整数问题

给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。
第二类指令形如 Q x，表示询问数列中第 x 个数的值。
对于每个询问，输出一个整数表示答案。
输入格式
第一行包含两个整数 N 和 M。
第二行含 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤10^5,
|d|≤10000,
|A[i]|≤10^9
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例：
4
1
2
5

image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. typedef long long LL;
  7. using namespace std;
  8. const int N = 1e5 + 10;
  9. int a[N], n, m;
  10. int tr[N];
  12. int lowbit(int x) {
  13.     return x & -x;
  14. }
  16. void update(int x, int c)  // 位置x加c
  17. {
  18.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
  19. }
  21. LL query(int x)  // 返回前x个数的和
  22. {
  23.     LL res = 0;
  24.     for (int i = x; i; i -= lowbit(i)) res += tr[i];
  25.     return res;
  26. }
  29. int main() {
  30.     cin >> n >> m;
  31.     for (int i = 1; i <= n; i++) {
  32.         cin >> a[i];
  33.     }
  34.     for (int i = 1; i <= n; i++) {
  35.         update(i, a[i] - a[i - 1]);   // 存入差分序列
  36.     }
  38.     while (m--) {
  39.         char op[2];
  40.         int l, r, d, x;
  41.         scanf("%s", &op);
  42.         if (op[0] == 'C') {
  43.             scanf("%d%d%d", &l, &r, &d);
  44.             update(l, d);         // 差分修改
  45.             update(r + 1, -d);
  46.         } else {
  47.             scanf("%d", &x);
  48.             cout << query(x) << endl;
  49.         }
  51.     }
  52. }

244. 谜一样的牛

有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。
现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。
输入格式
第 1 行：输入整数 n。
第 2..n 行：每行输入一个整数 Ai，第 i 行表示第 i 头牛前面有 Ai 头牛比它低。
（注意：因为第 1 头牛前面没有牛，所以并没有将它列出）
输出格式
输出包含 n 行，每行输出一个整数表示牛的身高。
第 i 行输出第 i 头牛的身高。
数据范围
1≤n≤10^5
输入样例：
5
1
2
1
0
输出样例：
2
4
5
3
1
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 1e5 + 10;
  7. int h[N], n;
  8. int tr[N];
  9. int ans[N];
  11. int lowbit(int x) {
  12.     return x & -x;
  13. }
  15. void update(int x, int c)  // 位置x加c
  16. {
  17.     for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
  18. }
  20. int query(int x)  // 返回前x个数的和
  21. {
  22.     int res = 0;
  23.     for (int i = x; i; i -= lowbit(i)) res += tr[i];
  24.     return res;
  25. }
  27. int main() {
  28.     cin >> n;
  29.     for (int i = 2; i <= n; i++) {
  30.         cin >> h[i];
  31.     }
  32.     for (int i = 1; i <= n; i++) {
  33.         update(i, 1);   //每个位置插入1
  34.     }
  35.     for (int i = n; i; i--) {
  36.         int k = h[i] + 1;
  37.         int l = 1, r = n;
  38.         while (l < r) {   // 在没有用过的数当中 二分找第k个数
  39.             int mid = l + r >> 1;
  40.             if (query(mid) >= k) {
  41.                 r = mid;
  42.             } else {
  43.                 l = mid + 1;
  44.             }
  45.         }
  46.         ans[i] = l;
  47.         update(l, -1);  // l这个位置的数已经用过，update(l,-1)相当于将这个位置为标记为用过
  48.     }
  49.     for (int i = 1; i <= n; i++) {
  50.         cout << ans[i] << endl;
  51.     }
  52. }

4316. 合适数对

给定一个长度为 n 的整数数列 a1,a2,…,an 和一个整数 t。
请你判断共有多少个数对 (l,r) 同时满足：
1≤l≤r≤n
al+al+1+…+ar−1+ar输入格式
第一行包含两个整数 n 和 t。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示满足条件的数对的数量。
数据范围
前三个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤2×10^5，|t|≤2×1014，|ai|≤109。
输入样例1：
5 4
5 -1 3 4 -1
输出样例1：
5
输入样例2：
3 0
-1 2 -3
输出样例2：
4
输入样例3：
4 -1
-2 1 -2 3
输出样例3：
3

  1. // 暴力解法，直接前缀和
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. typedef long long LL;
  9. int n,m;
  10. const int N = 2e5+10;
  11. LL a[N],s[N];
  12. int res;
  13. int main()
  14. {
  15.     cin >> n >> m;
  16.     for (int i = 1; i <= n; i ++ ){
  17.         cin >> a[i];
  18.         s[i] = s[i-1]+a[i];
  19.     }
  20.     for (int i = 1; i <= n; i ++ ){
  21.         for (int j = i; j <= n; j ++ ){
  22.             if(s[j]-s[i-1]<m){
  23.                 res++;
  24.             }
  25.         }
  26.     }
  27.     cout << res;
  28. }
  1. // 树状数组
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7. typedef long long LL;
  8. const int N = 2e6 + 10, M = N * 2;
  9. LL n, m;
  10. LL s[N],cnt;
  11. LL tr[M];
  12. vector<LL> nums;
  14. int lowbit(int x) {
  15.     return x & -x;
  16. }
  19. void add(int x, int k) {
  20.     for (int i = x; i <= cnt; i += lowbit(i)) tr[i] += k;
  21. }
  23. int sum(int x) {
  24.     int res = 0;
  25.     for (int i = x; i; i -= lowbit(i)) res += tr[i];
  26.     return res;
  27. }
  29. int get(LL x) {
  30.     return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
  31. }
  33. int main() {
  34.     cin >> n >> m;
  35.     for (int i = 1; i <= n; i++) {
  36.         cin >> s[i];
  37.         s[i] += s[i - 1];
  38.     }
  39.     for (int i = 0; i <= n; i++) { //将所有前缀和以及后续询问用到的数值全部离散化
  40.         nums.push_back(s[i]);
  41.         nums.push_back(s[i] - m);
  42.     }
  43.     sort(nums.begin(), nums.end());
  44.     nums.erase(unique(nums.begin(), nums.end()), nums.end());
  45.     // 把每一个数 添加到树状数组中
  46.     LL res = 0;
  47.     cnt = nums.size();
  48.     add(get(s[0]), 1);
  49.     for (int i = 1; i <= n; i++) {
  50.         res += sum(cnt) - sum(get(s[i] - m));
  51.         add(get(s[i]), 1);
  52.     }
  53.     cout << res;
  55. }

线段树

1275. 最大数

给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1 之间。
可以对这列数进行两种操作：
添加操作：向序列后添加一个数，序列长度变成 n+1；
询问操作：询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始，整数序列为空。
一共要对整数序列进行 m 次操作。
写一个程序，读入操作的序列，并输出询问操作的答案。
输入格式
第一行有两个正整数 m,p，意义如题目描述；
接下来 m 行，每一行表示一个操作。
如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；
如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。
第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。
输出格式
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 L 个数的最大数。
输入样例：
10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99
输出样例：
97
97
97
60
60
97
样例解释
最后的序列是 97,14,60,96。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. typedef long long LL;
  10. const int N = 200010;
  12. int m, p;
  13. struct Node
  14. {
  15.     int l, r;
  16.     int v;  // 区间[l, r]中的最大值
  17. }tr[N * 4];
  19. void pushup(int u)  // 由子节点的信息，来计算父节点的信息
  20. {
  21.     tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
  22. }
  24. void build(int u, int l, int r)
  25. {
  26.     tr[u] = {l, r};
  27.     if (l == r) return;
  28.     int mid = l + r >> 1;
  29.     build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  30. }
  32. int query(int u, int l, int r)
  33. {
  34.     if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了
  36.     int mid = tr[u].l + tr[u].r >> 1;
  37.     int v = 0;
  38.     if (l <= mid) v = query(u << 1, l, r);
  39.     if (r > mid) v = max(v, query(u << 1 | 1, l, r));
  41.     return v;
  42. }
  44. void modify(int u, int x, int v)
  45. {
  46.     if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
  47.     else
  48.     {
  49.         int mid = tr[u].l + tr[u].r >> 1;
  50.         if (x <= mid) modify(u << 1, x, v);
  51.         else modify(u << 1 | 1, x, v);
  52.         pushup(u);
  53.     }
  54. }
  57. int main()
  58. {
  59.     int n = 0, last = 0;
  60.     scanf("%d%d", &m, &p);
  61.     build(1, 1, m);
  63.     int x;
  64.     char op[2];
  65.     while (m -- )
  66.     {
  67.         scanf("%s%d", op, &x);
  68.         if (*op == 'Q')
  69.         {
  70.             last = query(1, n - x + 1, n);
  71.             printf("%d\n", last);
  72.         }
  73.         else
  74.         {
  75.             modify(1, n + 1, ((LL)last + x) % p);
  76.             n ++ ;
  77.         }
  78.     }
  80.     return 0;
  81. }

245. 你能回答这些问题吗

给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
1 x y，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤y{∑i=lrA[i]}。
2 x y，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行每行 3 个整数 k,x,y，k=1 表示查询（此时如果 x>y，请交换 x,y），k=2 表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 5e5+10;
  7. int w[N];
  8. struct Node
  9. {
  10.     int l, r;
  11.     int sum; // a[l]...a[r]的和
  12.     int lmax,rmax,tmax; // 以l为起点的最大连续子段和的长度
  13. }tr[N * 4];
  14. /*
  15. 分治法求最大连续子段和
  16. */
  18. void pushup(Node &u,Node &l,Node &r){
  19.     u.sum = l.sum + r.sum;
  20.     u.lmax = max(l.lmax,l.sum+r.lmax);
  21.     u.rmax = max(r.rmax,r.sum + l.rmax);
  22.     u.tmax = max(max(l.tmax,r.tmax),l.rmax + r.lmax);
  23. }
  25. void pushup(int u)
  26. {
  27.     pushup(tr[u],tr[u<<1],tr[u<<1|1]);  // 这里要写|不要写成+
  28. }
  31. void build(int u, int l, int r)
  32. {
  33.     if (l == r) tr[u] = {l, r,w[l],w[l],w[l],w[l]};
  34.     else
  35.     {
  36.         tr[u] = {l, r};
  37.         int mid = l + r >> 1;
  38.         build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  39.         pushup(u);
  40.     }
  41. }
  42. void modify(int u, int x, int v){ // 将x节点修改为v
  43.     if(tr[u].l==x&&tr[u].r==x){
  44.         tr[u] = {x,x,v,v,v,v};
  45.         return;
  46.     }
  47.     int mid = tr[u].l+tr[u].r >> 1;
  48.     if(x<=mid){
  49.         modify(u<<1,x,v);
  50.     }else{
  51.         modify(u<<1|1,x,v);
  52.     }
  53.     pushup(u);
  54. }
  56. Node query(int u, int l, int r)
  57. {
  58.     if (tr[u].l >= l && tr[u].r <= r)
  59.     {
  60.         return tr[u];
  61.     }
  62.     else
  63.     {
  64.         int mid = tr[u].l + tr[u].r >> 1;
  65.         if(r<=mid){
  66.             return query(u<<1,l,r);
  67.         }else if(l>mid){
  68.             return query(u<<1|1,l,r);
  69.         }else{
  70.             Node res;
  71.             auto t1 = query(u<<1,l,r);
  72.             auto t2 = query(u<<1|1,l,r);
  73.             pushup(res,t1,t2);
  74.             return res;
  75.         }
  76.     }
  77. }
  80. int main(){
  81.     int n,m;
  82.     cin >> n >> m;
  83.     for (int i = 1; i <= n; i ++ ){
  84.         cin >> w[i];
  85.     }
  86.     build(1,1,n);
  87.     while (m -- ){
  88.         int t,x,y;
  89.         cin >> t >> x >> y;
  90.         if(t==1){
  91.             if(x>y){
  92.                 swap(x,y);
  93.             }
  94.             auto t = query(1,x,y);
  95.             cout << t.tmax <<endl;
  96.         }else{
  97.             modify(1,x,y);
  98.         }
  99.     }
  100. }

246. 区间最大公约数

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. typedef long long LL;
  5. const int N = 5e5+10;
  6. using namespace std;
  7. LL w[N];
  8. int n,m;
  10. LL gcd(LL a, LL b)  // 欧几里得算法
  11. {
  12.     return b ? gcd(b, a % b) : a;
  13. }
  16. struct Node
  17. {
  18.     int l, r;
  19.     LL sum;  // l,r区间的和
  20.     LL d;    // l,r区间的最大公约数
  21. }tr[N * 4];
  23. void pushup(Node &u, Node &l, Node &r){
  24.     u.sum = l.sum+r.sum;
  25.     u.d = gcd(l.d,r.d);
  26. }
  28. void pushup(int u)
  29. {
  30.     pushup(tr[u],tr[u<<1],tr[u<<1|1]);
  31. }
  34. void build(int u, int l, int r)
  35. {
  36.     if (l == r) {
  37.         LL b = w[l]-w[l-1]; // 这里关键
  38.         tr[u] = {l, r, b, b};
  39.     }
  40.     else
  41.     {
  42.         tr[u] = {l, r};
  43.         int mid = l + r >> 1;
  44.         build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  45.         pushup(u);
  46.     }
  47. }
  50. Node query(int u, int l, int r)
  51. {
  52.     if (tr[u].l >= l && tr[u].r <= r)
  53.     {
  54.         return tr[u];
  55.     }
  56.     else
  57.     {
  58.         int mid = tr[u].l + tr[u].r >> 1;
  59.         if(r<=mid){
  60.             return query(u<<1,l,r);
  61.         }else if(l>mid){
  62.             return query(u<<1|1,l,r);
  63.         }else{
  64.             Node res,t1,t2;
  65.             t1 = query(u<<1, l, r);
  66.             t2 = query(u<<1|1, l, r);
  67.             pushup(res, t1, t2);
  68.             return res;
  69.         }
  71.     }
  72. }
  74. void modify(int u,int x,LL v){
  75.     if(tr[u].l==x&&tr[u].r==x){
  76.         LL b = tr[u].sum + v;
  77.         tr[u] = {x,x,b,b};   
  78.     }else{
  79.         int mid = tr[u].l + tr[u].r >>1;
  80.         if(x<=mid){
  81.             modify(u<<1,x,v);
  82.         }else{
  83.             modify(u<<1|1,x,v);
  84.         }
  85.         pushup(u);
  86.     }
  87. }
  89. int main()
  90. {
  91.     cin >> n >> m;
  92.     for (int i = 1; i <= n; i ++ ){
  93.         cin >> w[i];
  94.     }
  95.     build(1,1,n);
  96.     char op[5];
  97.     int l,r;
  98.     LL d;
  99.     while (m -- ){
  100.         scanf("%s", &op);
  101.         if(op[0]=='C'){
  102.             cin >> l >> r >>d;
  103.             modify(1,l,d);
  104.             if(r+1<=n){
  105.                 modify(1,r+1,-d);
  106.             }
  107.         }else{
  108.             cin >> l >> r;
  109.             Node t1={0,0,0,0};
  110.             auto t2 = query(1,1,l);
  111.             if(l+1<=r){
  112.                 t1 = query(1,l+1,r);
  113.             }
  114.             /* 这里为什么要求一个区间[1,l]的区间和呢，看下面解释
  115.             */
  116.             cout << abs(gcd(t2.sum,t1.d))<<endl;
  117.         }
  118.     }
  119. }
  120. /*
  121. 差分序列
  123. 原数列  w[1]        w[2]        w[3]        w[4]        w[5]
  124. 差分数列w[1]-w[0]  w[2]-w[1]   w[3]-w[2]   w[4]-w[3]   w[5]-w[4]
  125. 差分数列b[1]       b[2]           b[3]           b[4]           b[5]
  126. 假如现在目标是求[2,4]区间的最大公约数
  127. 那么不能直接查询query(1,2,4)的公约数，因为 差分序列b[2]不仅包含了w[2]，还包含了w[1]
  128. 所以就求从1到l的前缀和，得出w[2]的值
  129. */

243. 一个简单的整数问题2

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例：
4
55
9
15

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. typedef long long LL;
  10. const int N = 100010;
  12. int n, m;
  13. int w[N];
  14. struct Node
  15. {
  16.     int l, r;
  17.     LL sum, add;
  18. }tr[N * 4];
  20. void pushup(int u)
  21. {
  22.     tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
  23. }
  25. void pushdown(int u)
  26. {
  27.     auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
  28.     if (root.add)
  29.     {
  30.         left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
  31.         right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
  32.         root.add = 0;
  33.     }
  34. }
  36. void build(int u, int l, int r)
  37. {
  38.     if (l == r) tr[u] = {l, r, w[r], 0};
  39.     else
  40.     {
  41.         tr[u] = {l, r};
  42.         int mid = l + r >> 1;
  43.         build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  44.         pushup(u);
  45.     }
  46. }
  48. void modify(int u, int l, int r, int d)
  49. {
  50.     if (tr[u].l >= l && tr[u].r <= r)
  51.     {
  52.         tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
  53.         tr[u].add += d;  // 这里懒标记了，等下次用到这个点的时候再更新就行
  54.         // 那么什么时候用到呢
  55.         /*
  56.         1. 再次修改，可能会涉及到这个区间，所以下面的else那块有一样pushdown
  57.         2. 查询时涉及这个区间，那么一定得先pushdown
  58.         */
  59.     }
  60.     else    // 一定要分裂
  61.     {
  62.         pushdown(u);
  63.         int mid = tr[u].l + tr[u].r >> 1;
  64.         if (l <= mid) modify(u << 1, l, r, d);
  65.         if (r > mid) modify(u << 1 | 1, l, r, d);
  66.         pushup(u);
  67.     }
  68. }
  70. LL query(int u, int l, int r)
  71. {
  72.     if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
  74.     pushdown(u);
  75.     int mid = tr[u].l + tr[u].r >> 1;
  76.     LL sum = 0;
  77.     if (l <= mid) sum = query(u << 1, l, r);
  78.     if (r > mid) sum += query(u << 1 | 1, l, r);
  79.     return sum;
  80. }
  83. int main()
  84. {
  85.     scanf("%d%d", &n, &m);
  87.     for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  89.     build(1, 1, n);
  91.     char op[2];
  92.     int l, r, d;
  94.     while (m -- )
  95.     {
  96.         scanf("%s%d%d", op, &l, &r);
  97.         if (*op == 'C')
  98.         {
  99.             scanf("%d", &d);
  100.             modify(1, l, r, d);
  101.         }
  102.         else printf("%lld\n", query(1, l, r));
  103.     }
  105.     return 0;
  106. }

1277. 维护序列

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为 N 的数列，不妨设为 a1,a2,…,aN。
有如下三种操作形式：
把数列中的一段数全部乘一个值；
把数列中的一段数全部加一个值；
询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。
输入格式
第一行两个整数 N 和 P；
第二行含有 N 个非负整数，从左到右依次为 a1,a2,…,aN；
第三行有一个整数 M，表示操作总数；
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
操作 1：1 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai×c；
操作 2：2 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai+c；
操作 3：3 t g，询问所有满足 t≤i≤g 的 ai 的和模 P 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
输入样例：
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
输出样例：
2
35
8
样例解释
初始时数列为 {1,2,3,4,5,6,7}；
经过第 1 次操作后，数列为 {1,10,15,20,25,6,7}；
对第 2 次操作，和为 10+15+20=45，模 43 的结果是 2；
经过第 3 次操作后，数列为 {1,10,24,29,34,15,16}；
对第 4 次操作，和为 1+10+24=35，模 43 的结果是 35；
对第 5 次操作，和为 29+34+15+16=94，模 43 的结果是 8。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. typedef long long LL;
  10. const int N = 100010;
  12. int n, m,p;
  13. int w[N];
  14. struct Node
  15. {
  16.     int l, r;
  17.     LL sum, add, mul;
  18. }tr[N * 4];
  20. void pushup(int u)
  21. {
  22.     tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum)%p; // 这里取模
  23. }
  25. void eval(Node& t,LL add,LL mul){
  26.     t.sum = (t.sum*mul)%p + (((LL)t.r - t.l + 1)*add) % p;  // 取模
  27.     t.mul = (t.mul*mul)%p;
  28.     t.add = (t.add * mul + add)%p;
  29. }
  31. void pushdown(int u)
  32. {
  33.     auto &t = tr[u];
  34.     eval(tr[u<<1],t.add,t.mul);
  35.     eval(tr[u<<1|1],t.add,t.mul);
  36.     t.add = 0;
  37.     t.mul = 1;
  38. }
  40. void build(int u, int l, int r)
  41. {
  42.     if (l == r) tr[u] = {l, r, w[r], 0, 1 }; // 这里要改
  43.     else
  44.     {
  45.         tr[u] = {l, r,0,0,1}; // 这里要改
  46.         int mid = l + r >> 1;
  47.         build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  48.         pushup(u);
  49.     }
  50. }
  52. void modify(int u, int l, int r, LL add, LL mul)
  53. {
  54.     if (tr[u].l >= l && tr[u].r <= r)
  55.     {
  56.         eval(tr[u], add, mul);
  57.     }
  58.     else    // 一定要分裂
  59.     {
  60.         pushdown(u);
  61.         int mid = tr[u].l + tr[u].r >> 1;
  62.         if (l <= mid) modify(u << 1, l, r, add,mul);
  63.         if (r > mid) modify(u << 1 | 1, l, r, add,mul);
  64.         pushup(u);
  65.     }
  66. }
  68. LL query(int u, int l, int r)
  69. {
  70.     if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
  72.     pushdown(u);
  73.     int mid = tr[u].l + tr[u].r >> 1;
  74.     LL sum = 0;
  75.     if (l <= mid) sum = query(u << 1, l, r)%p;
  76.     if (r > mid) {
  77.         sum = (sum + query(u << 1 | 1, l, r))%p;
  78.     }
  79.     return sum;
  80. }
  83. int main()
  84. {
  85.     scanf("%d%d", &n,&p);
  87.     for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  89.     cin >> m;
  90.     build(1, 1, n);
  92.     int op;
  93.     int l, r; 
  94.     LL d;
  96.     while (m -- )
  97.     {
  98.         scanf("%d%d%d", &op, &l, &r);
  99.         if (op == 1)
  100.         {
  101.             scanf("%d", &d);
  102.             modify(1, l, r, 0,d);
  103.         }else if(op==2){
  104.             scanf("%d", &d);
  105.             modify(1, l, r, d,1);
  106.         }
  107.         else printf("%lld\n", query(1, l, r)%p);
  108.     }
  110.     return 0;
  111. }

247. 亚特兰蒂斯

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友 Bill 必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例，第一行包含整数 n，表示总的地图数量。
接下来 n 行，描绘了每张地图，每行包含四个数字 x1,y1,x2,y2（不一定是整数），(x1,y1) 和 (x2,y2) 分别是地图的左上角位置和右下角位置。
注意，坐标轴 x 轴从上向下延伸，y 轴从左向右延伸。
当输入用例 n=0 时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出 Test case #k，其中 k 是测试用例的编号，从 1 开始。
第二行输出 Total explored area: a，其中 a 是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。
在每个测试用例后输出一个空行。
输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00
样例解释
样例所示地图覆盖区域如下图所示，两个矩形区域所覆盖的总面积，即为样例的解。
image.png
image.png
image.png
image.png
建立了线段树, 我们再考虑实际线段要怎么存进去, 假设我们存储的是点. 那么当前最小节点是类似[1, 1], [2, 2]这样,
显然他们单独的长度都是0(因为是点)
假设离散化后的ys为 [5.1, 6.2, 8.5, 10.8, …]
考虑线段树内[1, 1], [2, 2]的父节点[1, 2], 我们若需要[1, 2]这个节点的len能够
映射离散化区间里面6.2到8.5的距离的话, 即需要tr[x].r找到8.5, tr[x].l找到6.2 这样看着是可行的
但是这样的话, 当线段树被切分成单位点的时候, 比如若线段树根节点是[0, 2]
要查询[1,2]的长度, 按照线段树国际惯例, 我们下一步会切成[0, 1]和[2, 2], 那么可以发现, 这里我们弄断了两点之间的线段, 且很难继续记录他们之间的关联, 导致难以进行下去

所以, 我们换一种映射方法, 我们考虑令线段树的最小单位是映射相邻两点之间的线段:
同样假设离散化后的ys为 [5.1, 6.2, 8.5, 10.8, …]
考虑线段树区间[0, 0], 我们需要它映射到5.1~6.2这个区间, 同理[1, 1]映射[6.2, 8.5] …
那么, 我们每个线段树最小单位映射的长度, 就应该是ys[tr[t].r + 1] - ys[tr[t].l] 即可
很容易看出, 该做法可以推到更上层的节点也不会出错

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  6. using namespace std;
  8. const int N = 10010;
  10. int n;
  12. // 用于存每一组数据里面的每一条竖线(线段)
  13. struct Segment
  14. {
  15.     double x, y1, y2;
  16.     int k; //标记左右竖线
  17.     bool operator<(const Segment &t)const
  18.     {
  19.         return x < t.x;
  20.     }
  21. }seg[N * 2]; // 每个测试用例包括n组数据(n<=10000), 每组数组是1个矩形, 存2条竖线
  23. struct Node
  24. {
  25.     int l, r; // 左右端点
  26.     int cnt;  // 当前区段(整段)被有效覆盖次数
  27.     double len;  // 当前区间内的有效长度
  28. }tr [N * 8]; // 每个测试用例最多存在, 2n个y坐标再 * 4(线段树)
  30. vector<double> ys;
  32. int find(double y)
  33. {
  34.     return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
  35. }
  37. void pushup(int u)
  38. {
  39.     // 如果该"整段"需要算入len
  40.     if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
  41.     // 如果tr[u].cnt等于0其实有两种情况:
  42.     // 1. 完全覆盖. 这种情况由modify的第一个if进入. 
  43.     //    这时下面其实等价于把"由完整的l, r段贡献给len的部分清除掉", 
  44.     //    而留下其他可能存在的子区间段对len的贡献
  45.     // 2. 不完全覆盖, 这种情况由modify的else最后一行进入. 
  46.     //    表示区间并不是完全被覆盖，可能有部分被覆盖,所以要通过儿子的信息来更新
  47.     else if (tr[u].cnt == 0 && tr[u].l != tr[u].r)  //加个==0清晰点
  48.     {
  49.         tr[u].len = tr[u<<1].len + tr[u<<1|1].len;
  50.     }
  51.     else tr[u].len = 0; // 不可再分且cnt等于0, 那就直接安全置0
  52. }
  54. void build(int u, int l, int r)
  55. {
  56.     if (l == r) tr[u] = {l, r, 0, 0};
  57.     if (l != r)
  58.     {
  59.         tr[u] = {l, r};
  60.         int mid = l + r >> 1;
  61.         build(u<<1, l, mid), build(u<<1|1, mid+1, r);
  62.         pushup(u);
  63.     }
  64. }
  66. void modify(int u, int l, int r, int k)
  67. {
  68.     // 线段被包住, 说明整体都是要改的
  69.     if (tr[u].l >= l && tr[u].r <= r)
  70.     {
  71.         tr[u].cnt += k;  // cnt是当前还在计算面积的矩形个数
  72.         pushup(u);
  73.     }
  74.     else
  75.     {
  76.         int mid = tr[u].l + tr[u].r >> 1;
  77.         if (l <= mid) modify(u<<1, l, r, k);
  78.         if (r > mid) modify(u<<1|1, l, r, k);
  79.         pushup(u);
  80.     }
  81. }
  83. // debug用
  84. void print_tree()
  85. {
  86.     puts("tree:");
  87.     for (int i = 0; i <= ys.size()-2; i++)
  88.     {
  89.         printf("i: %d,  l: %d  r:  %d  cnt:  %d,  len:  %lf\n",
  90.                 i, tr[i].l, tr[i].r, tr[i].cnt, tr[i].len);
  91.     }
  92. }
  94. int main()
  95. {
  96.     int T = 1;
  97.     // 测试用例组数不定, 直到n为0才停止
  98.     while (scanf("%d", &n), n)
  99.     {
  100.         ys.clear();
  101.         // 每组测试用例有n个矩形输入
  102.         for (int i = 0, j = 0; i < n; i++)
  103.         {
  104.             double x1, y1, x2, y2;
  105.             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
  106.             seg[j++] = {x1, y1, y2, 1}; //左竖线
  107.             seg[j++] = {x2, y1, y2, -1}; //右竖线
  108.             ys.push_back(y1), ys.push_back(y2); // 离散化压缩空间
  109.         }
  111.         // 离散化
  112.         sort(ys.begin(), ys.end());
  113.         ys.erase(unique(ys.begin(), ys.end()), ys.end());
  115.         // 对该组所有测试用例的y坐标离散后所在区间构造线段树
  116.         // y轴有ys.size()个点, 而我们线段树需要存线段, 这里一共有ys.size()-1个线段
  117.         // 而线段树build是每个单位点为最小单位, 所以最少得build ys.size()-1个点
  118.         // 所以r最小是build(1, 0, ys.size()-2) 实际上r只需要不比这个ys.size()-2小就行
  119.         build(1, 0, ys.size() - 2);
  120.         // 建立了线段树, 我们再考虑实际线段要怎么存进去, 当前最小节点是类似[1, 1], [2, 2]这样,
  121.         // 显然他们单独的长度都是0(因为是点)
  122.         // 假设离散化后的ys为 [5.1, 6.2, 8.5, 10.8, ...] 
  123.         // 考虑线段树内[1, 1], [2, 2]的父节点[1, 2], 我们若需要[1, 2]这个节点的len能够
  124.         // 映射离散化区间里面6.2到8.5的距离的话, 即需要tr[x].r找到8.5, tr[x].l找到6.2 
  125.         // 这样看着是可行的
  126.         // 但是这样的话, 当线段树被切分成单位点的时候, 比如若线段树根节点是[0, 2]
  127.         // 要查询[1,2]的长度, 按照线段树国际惯例, 我们下一步会切成[0, 1]和[2, 2], 那么可以发现, 
  128.         // 这里我们弄断了两点之间的线段, 且很难继续记录他们之间的关联, 导致难以进行下去
  130.         // 所以, 我们换一种映射方法, 我们考虑令线段树的最小单位是映射相邻两点之间的线段:
  131.         // 同样假设离散化后的ys为 [5.1, 6.2, 8.5, 10.8, ...]
  132.         // 考虑线段树区间[0, 0], 我们需要它映射到5.1~6.2这个区间, 同理[1, 1]映射[6.2, 8.5] ...
  133.         // 那么, 我们每个线段树最小单位映射的长度, 就应该是ys[tr[t].r + 1] - ys[tr[t].l] 即可
  134.         // 很容易看出, 该做法可以推到更上层的节点也不会出错
  137.         // 根据x的大小排序, 确定后面遍历是正确的从左到右
  138.         sort(seg, seg + n * 2);
  140.         double res = 0;
  141.         for (int i = 0; i < n * 2; i++)
  142.         {
  143.             // tr[1].len是当前y轴实际使用长度, 乘上x就是面积
  144.             if (i > 0)res += tr[1].len * (seg[i].x - seg[i-1].x);
  145.             // 线段树插入当前y轴上的用到的线段, .k是标记左右竖线
  146.             // 参考上面调用build之前的注释, 从tr去取出真实ys坐标(y轴离散化后)要+1
  147.             // 那么从真实ys坐标找回对应tr内的右点就减回去1
  148.             modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
  150.         }
  153.         printf("Test case #%d\n", T++);
  154.         printf("Total explored area: %.2lf\n\n", res);
  155.     }
  156.     return 0;
  157. }

image.png
image.png

可持久化数据结构

最大异或和

给定一个非负整数序列 a，初始长度为 N。
有 M 个操作，有以下两种操作类型：
A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 增大 1。
Q l r x：询问操作，你需要找到一个位置 p，满足 l≤p≤r，使得：a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出这个最大值。
输入格式
第一行包含两个整数 N，M，含义如问题描述所示。
第二行包含 N 个非负整数，表示初始的序列 A。
接下来 M 行，每行描述一个操作，格式如题面所述。
输出格式
每个询问操作输出一个整数，表示询问的答案。
每个答案占一行。
输入样例：
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
输出样例：
4
5
6
image.png

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. const int N = 600010, M = N * 25;
  10. int n, m;
  11. int s[N];
  12. int tr[M][2], max_id[M];
  13. int root[N], idx;
  14. /*
  15. i是s[i]中的i，即s的下标
  16. k是当前处理到第几位
  17. p是上一个版本
  18. q是最新版本
  19. */
  20. void insert(int i, int k, int p, int q)
  21. {
  22.     if (k < 0)
  23.     {
  24.         max_id[q] = i;
  25.         return;
  26.     }
  27.     int v = s[i] >> k & 1;
  28.     // 当前这位是v可以将原先的覆盖掉
  29.     // 所以只需要将v^1 这一位从p这个版本复制过来
  30.     if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
  31.     // 当前的点必须开一个新的点
  32.     tr[q][v] = ++ idx;
  33.     // 递归插入另一个
  34.     insert(i, k - 1, tr[p][v], tr[q][v]);
  35.     // 更新一下当前版本的最大id
  36.     max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
  37. }
  38. /*
  39. 本题目是在区间[l,r]中寻找一个p使得
  40. a[p]^a[p+1].....^a[N] ^ x值最大
  41. 那考虑到b^a^a = b
  42. 所以我们预处理一个前缀和
  43. s[1] = a[1]
  44. s[2] = a[1]^a[2]
  45. s[3] = a[1]^a[2]^a[3]
  46. ....
  47. s[n] = a[1]^a[2]^a[3]....^a[n]
  48. 要 求a[p]^a[p+1].....^a[N]的值，只需要s[n]^s[p-1]即可
  49. */ 
  51. /*
  52. root 根节点
  53. C 从root为根的子树中找与C异或最大的数
  54. 因此题目中的p是从[l,r]中找
  55. 那么p-1就是从[l-1,r-1]中找
  56. */
  57. int query(int root, int C, int L)
  58. {
  59.     int p = root;
  60.     for (int i = 23; i >= 0; i -- )
  61.     {
  62.         int v = C >> i & 1;
  63.         if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
  64.         else p = tr[p][v];
  65.     }
  66.     return C ^ s[max_id[p]];
  67. }
  69. int main()
  70. {
  71.     scanf("%d%d", &n, &m);
  72. /*
  73. 这里为什么必须将max_id[0]设置成一个非法值？
  74. 注意到在查询函数中
  75. if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
  76. 如果tr[p][v^1]这个点不存在，那么他的值肯定是0，
  77. 那就相当于
  78. if (max_id[0] >= L) p = tr[p][v ^ 1];
  79. 当L = 0时，本来是不存在这个点（tr[p][v ^ 1]）的却要走向这个点，那么走向这个点
  80. 就一定会将结果变小
  81. 假设前面已经匹配一段了abcde,待匹配是xxxx
  82. abcdexxxx
  83. 但是如果走向这个不存在的点的话query函数最后返回那块
  84. C ^ s[max_id[p]]; 
  85. s[max_id[p]] = s[0]=0，
  86. 而正确结果至少是匹配abcde这一段大于等于0
  87. */
  88.     max_id[0] = -1;
  89. /*
  90. 为什么又要初始化root[0]并且插入0节点呢
  91. 因为p-1的范围是[l-1,r-1],当l-1==0时，意味着有可能和0匹配，所以必须加
  92. */
  93.     root[0] = ++ idx;
  94.     insert(0, 23, 0, root[0]);
  96.     for (int i = 1; i <= n; i ++ )
  97.     {
  98.         int x;
  99.         scanf("%d", &x);
  100.         s[i] = s[i - 1] ^ x;
  101.         root[i] = ++ idx;
  102.         insert(i, 23, root[i - 1], root[i]);
  103.     }
  105.     char op[2];
  106.     int l, r, x;
  107.     while (m -- )
  108.     {
  109.         scanf("%s", op);
  110.         if (*op == 'A')
  111.         {
  112.             scanf("%d", &x);
  113.             n ++ ;
  114.             s[n] = s[n - 1] ^ x;
  115.             root[n] = ++ idx;
  116.             insert(n, 23, root[n - 1], root[n]);
  117.         }
  118.         else
  119.         {
  120.             scanf("%d%d%d", &l, &r, &x);
  121.             printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
  122.         }
  123.     }
  125.     return 0;
  126. }
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. // 30w初始数据和30w新增,  而10的7次方小于2的24次方, 再加上根节点, 就是说每个数最多需要25位;
  7. const int N = 600010, M = N * 25;
  9. int n, m;
  10. int s[N]; // 前缀和序列
  11. int tr[M][2];
  12. int max_id[M];  // 用于记录当前根节点版本的最大id范围
  13. int root[N], idx;
  15. // i是第i个插入的数的i, p是上一个插入的数的节点号, q是当前节点号, k是现在取到第k位
  16. void insert(int i, int k, int p, int q)
  17. {
  18.     // 如果记录结束了
  19.     if (k < 0)
  20.     {
  21.         max_id[q] = i;  // 记录当前节点(可能会被后面公用)所能到达的最大范围i
  22.         return;
  23.     }
  25.     // 取出前缀和的二进制表示从右往左数第k位v
  26.     // 需要注意的是, 这个s[i]就是我们要存的东西!!!!!
  27.     int v = s[i] >> k & 1;
  29.     // 如果前一个节点存在当前节点没有的分支, 那就把当前节点的这个空的路径指过去, 这就相当于复制!
  30.     if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
  32.     tr[q][v] = ++idx; // 现在才是正常trie树插入
  34.     // 递归插入下一位二进制, tr[q][v]就是我们本轮插入的新节点
  35.     // 而前面我们只复制了前一轮的不同v方向的路径, v方向的还没动过, 于是放到p里面等下一轮
  36.     // 至于为什么可以放到下一轮, 因为当前q新插入的数字(二进制当前位)是v, 而p的这条路径也是v
  37.     // 所以暂时不需要复制
  38.     insert(i, k - 1, tr[p][v], tr[q][v]);
  40.     // 下面是递归到所有点都插入完成才开始进行的, 所以能把最大max_id递归传递回去
  41.     // 每个点的最大范围用子节点最大的值, 然后还能递归传递回去, 因为当前递归层
  42.     // 的q, 就是上一层的tr[q][v], 观察易知每个节点都会有对应max_id
  43.     max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
  44. }
  46. int query(int r, int C, int l)
  47. {
  48.     // 选用合适的root, 就是第r-1个节点作为root(-1已在传参前完成)
  49.     // 然后根据异或的前缀和性质才能保证在r左边
  50.     int p = root[r];
  52.     for (int i = 23; i >= 0; i--)
  53.     {
  54.         // C是s[n] ^ x, 从高位到低位逐位检索二进制每一位上能跟C异或结果最大的数
  55.         int v = C >> i & 1; 
  56.         // 自带判空功能如果没有点, max_id会为0, 那就肯定不能满足>=l
  57.         // 而max_id又同时可以限制当前的点是在l r区间内
  58.         // 另外, 如果tr[p][v^1]为空, 那么tr[p][v]就肯定不为空,并在l r区间, 因为根据
  59.         // 插入的代码, 每个节点至少有一条当前s[i]的完整路径
  60.         // 而如果tr[p][v^1]不为空但maxid小于l, 同理也能选取到tr[p][v]
  61.         if (max_id[tr[p][v ^ 1]] >= l) p = tr[p][v ^ 1]; 
  62.         else p = tr[p][v];
  63.     }
  65.     return C ^ s[max_id[p]];
  66. }
  68. int main()
  69. {
  70.     scanf("%d%d", &n, &m);
  71.     // 前缀和, 初始化root[0]
  72.     max_id[0] = -1;
  73.     root[0] = ++idx;
  74.     insert(0, 23, 0, root[0]);
  75.     for (int i = 1; i <= n; i++)
  76.     {
  77.         int x;
  78.         scanf("%d", &x);
  79.         s[i] = s[i - 1] ^ x; // 前缀和序列
  80.         root[i] = ++idx;
  81.         insert(i, 23, root[i - 1], root[i]);
  82.     }
  84.     char op[2];
  85.     int l, r, x;
  86.     while (m--)
  87.     {
  88.         scanf("%s", op);
  89.         if (op[0] == 'A')
  90.         {
  91.             scanf("%d", &x);
  92.             n++;
  93.             s[n] = s[n - 1] ^ x;
  94.             root[n] = ++idx;
  95.             insert(n, 23, root[n - 1], root[n]);
  96.         }
  97.         else
  98.         {
  99.             scanf("%d%d%d", &l, &r, &x);
  100.             // 至少要包住第r个点, 所以用r-1, 否则会因为异或把root[r]抵消掉
  101.             // l也同理
  102.             printf("%d\n", query(r - 1, s[n] ^ x, l - 1));
  103.         }
  104.     }
  105.     return 0;
  106. }
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 6e5+10,M = N*24;
  7. int tr[M][2],idx,maxid[M],root[N];
  8. int s[N];
  9. int n,m;
  10. /*
  11. 下面insert函数中注意
  12.         if(lp){
  13.             tr[p][u^1] = tr[lp][u^1];
  14.             lp = tr[lp][u];
  15.         }
  16. 这段是非常巧妙的，试问自己一个问题，这棵trie树是如何保存到历史版本的
  17.     关键就在于 if函数里面那两句
  18.     理解一下: 这里的tr其实是一个指针，直接将现在的节点指向了，上一个版本的trie树中的节点
  19.         而且还能保证不重不漏
  20. */
  21. void insert(int k,int lp,int p,int x){
  22.     maxid[p] = k;
  23.     for (int i = 23; i >=0; i -- ){
  24.         int u = x>>i&1;
  25.         if(lp){
  26.             tr[p][u^1] = tr[lp][u^1];
  27.             lp = tr[lp][u];
  28.         }
  29.         tr[p][u] = ++idx;
  30.         p = tr[p][u];
  31.         maxid[p]=k;
  32.     }
  33. }
  35. int query(int p,int x,int l){
  36.     for (int i = 23; i >=0; i -- ){
  37.         int u = x>>i&1;
  38.         if(maxid[tr[p][u^1]]>=l){
  39.             p = tr[p][u^1];
  40.         }else{
  41.             p = tr[p][u];
  42.         }
  43.     }
  44.     return x^s[maxid[p]];
  45. }
  47. int main()
  48. {
  49.     cin >> n >> m;
  50.     maxid[0]=-1;
  51.     root[0]=++idx;
  52.     insert(0,root[0],root[0],0);
  53.     for (int i = 1; i <= n; i ++ ){
  54.         int x ;
  55.         cin >> x ;
  56.         s[i] = s[i-1]^x;
  57.         root[i] = ++idx;
  58.         insert(i,root[i-1],root[i],s[i]);
  59.     }
  60.     char op[2];
  61.     int l,r,x;
  62.     while (m -- ){
  63.         scanf("%s", &op);
  64.         if(op[0]=='A'){
  65.             cin >> x;
  66.             n++;
  67.             root[n] = ++idx;
  68.             s[n] = s[n-1]^x;
  69.             insert(n,root[n-1],root[n],s[n]);
  70.         }else{
  71.             cin >> l >> r >> x;
  72.             cout << query(root[r-1],s[n]^x,l-1) <<endl;
  73.         }
  75.     }
  76. }

255. 第K小数

给定长度为 N 的整数序列 A，下标为 1∼N。
现在要执行 M 次操作，其中第 i 次操作为给出三个整数 li,ri,ki，求 A[li],A[li+1],…,A[ri] (即 A 的下标区间 [li,ri])中第 ki 小的数是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数，表示整数序列 A。
接下来 M 行，每行包含三个整数 li,ri,ki，用以描述第 i 次操作。
输出格式
对于每次操作输出一个结果，表示在该次操作中，第 k 小的数的数值。
每个结果占一行。
输入样例：
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
输出样例：
5
6
3

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  6. using namespace std;
  7. const int N = 1e5 + 10;
  8. int n, m;
  9. int a[N];
  10. vector<int> nums; // 用于离散化
  11. struct Node {
  12.     int l, r, cnt; // l和r分别是左儿子和右儿子的编号,cnt是在某个区间内元素个数
  13.     // 而这个区间是默认的
  14. } tr[N * 4 + 17 * N];
  15. int root[N], idx;
  17. int find(int x) {
  18.     return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
  19. }
  21. int insert(int p, int l, int r, int x) {
  22.     int q = ++idx;
  23.     tr[q] = tr[p];
  24.     if (l == r) {
  25.         tr[q].cnt++;
  26.         return q;
  27.     }
  28.     int mid = l + r >> 1;
  29.     if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
  30.     else tr[q].r = insert(tr[p].r, mid + 1, r, x);
  31.     tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
  32.     return q;
  33. }
  35. int query(int q, int p, int l, int r, int k) {
  36.     if (l == r) return r;
  37.     int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
  38.     int mid = l + r >> 1;
  39.     if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
  40.     else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
  41. }
  43. int main() {
  44.     cin >> n >> m;
  45.     for (int i = 1; i <= n; i++) {
  46.         cin >> a[i];
  47.         nums.push_back(a[i]);
  48.     }
  49.     // 排序,去重
  50.     sort(nums.begin(), nums.end());
  51.     nums.erase(unique(nums.begin(), nums.end()), nums.end());
  52.     // 插入各个元素
  54.     for (int i = 1; i <= n; i++)
  55.         root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
  57.     while (m--) {
  58.         int l, r, k;
  59.         scanf("%d%d%d", &l, &r, &k);
  60.         cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)];
  62.     }
  63. }

AC自动机

1282. 搜索关键词

给定 n 个长度不超过 50 的由小写英文字母组成的单词，以及一篇长为 m 的文章。
请问，其中有多少个单词在文章中出现了。
注意：每个单词不论在文章中出现多少次，仅累计 1 次。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
对于每组数据，第一行一个整数 n，接下去 n 行表示 n 个单词，最后一行输入一个字符串，表示文章。
出格式
对于每组数据，输出一个占一行的整数，表示有多少个单词在文章中出现。
数据范围
1≤n≤10^4,
1≤m≤10^6
输入样例：
1
5
she
he
say
shr
her
yasherhs
输出样例：
3

这道题跟平常的ac自动机有点不一样之处 就是 cnt[p]统计以p为后缀的所有单词的时候，在build else { ne[p] = tr[ne[t]][i]; q[++tt] = p; } 这块时不能直接写上 cnt[p]+=cnt[ne[p]]，可能你会想到一种办法，那就是在主函数遍历那块写成 int j = str[i]-‘a’; p = tr[p][j]; // 走到了ac自动机的这个节点上 res += cnt[p]; int u = p; while(u){ cnt[u]=0; u = ne[u]; } 这样就因为cnt[p]包含了cnt[ne[p]], 所以要把它所有的ne[p]的cnt清零

但是，但是，但是，这也是不对的！！！

  1. 因为有可能有一个更长的字符串也包含了ne[p]，那么这个字符串也应该减去ne[p]，但是很显然减不掉

所以只能用下面这种解法

  1. 不能将cnt的计算放到build里面 ```cpp

    include

    include

    include

using namespace std;

const int N = 1e4 + 10, M = N * 55; int tr[M][26], idx; int cnt[M], ne[M]; int q[M];

void insert(string str) // 将str插入Trie中 { int p = 0; for (int i = 0; i < str.size(); i++) { int u = str[i] - ‘a’; if (!tr[p][u]) tr[p][u] = ++idx; p = tr[p][u]; } cnt[p]++; // 记录单词出现次数 }

void build() // 创建AC自动机 { int hh = 0, tt = -1; for (int i = 0; i < 26; i++) if (tr[0][i]) q[++tt] = tr[0][i]; while (hh <= tt) { int t = q[hh++]; for (int i = 0; i < 26; i++) { int p = tr[t][i]; if (!p) tr[t][i] = tr[ne[t]][i]; else { ne[p] = tr[ne[t]][i]; q[++tt] = p; } } } }

int main() { int T; cin >> T; while (T—) { memset(cnt, 0, sizeof cnt); memset(ne, 0, sizeof ne); memset(tr, 0, sizeof tr); idx = 0; int n; cin >> n; for (int i = 0; i < n; i++) { string s; cin >> s; insert(s); } build(); string str; cin >> str; // 看看文章中出现多少单词 int p = 0, res = 0; for (int i = 0; i < str.size(); i++) { // 枚举每个字母 int j = str[i] - ‘a’; p = tr[p][j]; // 走到了ac自动机的这个节点上 int q = p; while (q) { res += cnt[q]; cnt[q] = 0; q = ne[q]; } } cout << res << endl; }

}

  1. <a name="RgTog"></a>
  2. ### 1285. 单词
  3. 某人读论文，一篇论文是由许多单词组成的。<br />但他发现一个单词会在论文中出现很多次，现在他想知道每个单词分别在论文中出现多少次。<br />**输入格式**<br />第一行一个整数 N，表示有多少个单词。<br />接下来 N 行每行一个单词，单词中只包含小写字母。<br />**输出格式**<br />输出 N 个整数，每个整数占一行，第 i 行的数字表示第 i 个单词在文章中出现了多少次。<br />**数据范围**<br />1≤N≤200,<br />所有单词长度的总和不超过 106。<br />**输入样例：**<br />3<br />a<br />aa<br />aaa<br />**输出样例：**<br />6<br />3<br />1<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/1788465/1646893207351-1703df44-0032-476a-8fdf-0ac7ad1f4b86.png#clientId=uecc76e2e-0968-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=996&id=u73ce314d&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1556&originWidth=1096&originalType=binary&ratio=1&rotation=0&showTitle=false&size=1848423&status=done&style=none&taskId=u12bd6fa8-c571-41b5-b4e8-252506a56b9&title=&width=701.44)
  4. ```cpp
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iostream>
  8. #include <algorithm>
  10. using namespace std;
  12. const int N = 1000010;
  14. int n;
  15. int tr[N][26], f[N], idx;
  16. int q[N], ne[N];
  17. char str[N];
  18. int id[210];
  20. void insert(int x)
  21. {
  22.     int p = 0;
  23.     for (int i = 0; str[i]; i ++ )
  24.     {
  25.         int t = str[i] - 'a';
  26.         if (!tr[p][t]) tr[p][t] = ++ idx;
  27.         p = tr[p][t];
  28.         f[p] ++ ;
  29.     }
  30.     id[x] = p;
  31. }
  33. void build()
  34. {
  35.     int hh = 0, tt = -1;
  36.     for (int i = 0; i < 26; i ++ )
  37.         if (tr[0][i])
  38.             q[ ++ tt] = tr[0][i];
  40.     while (hh <= tt)
  41.     {
  42.         int t = q[hh ++ ];
  43.         for (int i = 0; i < 26; i ++ )
  44.         {
  45.             int &p = tr[t][i];
  46.             if (!p) p = tr[ne[t]][i];
  47.             else
  48.             {
  49.                 ne[p] = tr[ne[t]][i];
  50.                 q[ ++ tt] = p;
  51.             }
  52.         }
  53.     }
  54. }
  56. int main()
  57. {
  58.     scanf("%d", &n);
  60.     for (int i = 0; i < n; i ++ )
  61.     {
  62.         scanf("%s", str);
  63.         insert(i);
  64.     }
  66.     build();
  68.     for (int i = idx - 1; i >= 0; i -- ) f[ne[q[i]]] += f[q[i]];
  70.     for (int i = 0; i < n; i ++ ) printf("%d\n", f[id[i]]);
  72.     return 0;
  73. }