区间的操作最主要的地方就是把 split 操作从按权值分裂 改成了 按大小分裂

 

我们把 大小 == k 放在一棵树，然后其余的放在另一棵树

 

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string.h>
  4 #include <random>
  5 
  6 const int maxn = 1e5 + 10;
  7 
  8 struct Node {
  9     int l,r;
 10     int val,key;
 11     int size;
 12     bool reverse;
 13 }fhq[maxn];
 14 
 15 int cnt,root;
 16 
 17 std::mt19937 rnd(233);
 18 
 19 int newnode(int val) {
 20     fhq[++cnt].val = val;
 21     fhq[cnt].key = rnd();
 22     fhq[cnt].size = 1;
 23     return cnt;
 24 }
 25 
 26 void update(int now) {
 27     fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
 28 }
 29 
 30 void pushdown(int now) {
 31     std::swap(fhq[now].l,fhq[now].r);
 32     fhq[fhq[now].l].reverse^=1;
 33     fhq[fhq[now].r].reverse^=1;
 34     fhq[now].reverse = false;
 35 }
 36 
 37 void split(int now,int siz,int &x,int &y) {
 38     if (!now)
 39         x = y = 0;
 40     else {
 41         if (fhq[now].reverse) {
 42             pushdown(now);
 43         }
 44         if (fhq[fhq[now].l].size < siz) {
 45             x = now;
 46             split(fhq[now].r,siz-fhq[fhq[now].l].size-1,fhq[now].r,y);
 47         }
 48         else {
 49             y = now;
 50             split(fhq[now].l,siz,x,fhq[now].l);
 51         }
 52         update(now);
 53     }
 54 }
 55 
 56 int merge(int x,int y) {
 57     if (!x || !y)
 58         return x + y;
 59     if (fhq[x].key > fhq[y].key) {
 60         if (fhq[x].reverse)
 61             pushdown(x);
 62         fhq[x].r = merge(fhq[x].r,y);
 63         update(x);
 64         return x;
 65     }
 66     else {
 67         if (fhq[y].reverse)
 68             pushdown(y);
 69         fhq[y].l = merge(x,fhq[y].l);
 70         update(y);
 71         return y;
 72     }
 73 }
 74 
 75 void reverse(int l,int r) {
 76     int x,y,z;
 77     split(root,l-1,x,y);
 78     split(y,r-l+1,y,z);
 79     fhq[y].reverse^=1;
 80     root = merge(merge(x,y),z);
 81 }
 82 
 83 void ldr(int now) {
 84     if (!now)
 85         return ;
 86     if (fhq[now].reverse)
 87         pushdown(now);
 88     ldr(fhq[now].l);
 89     printf("%d ",fhq[now].val);
 90     ldr(fhq[now].r);
 91 }
 92 
 93 int main() {
 94     int n,m;
 95     scanf("%d%d",&n,&m);
 96     for (int i=1;i<=n;i++) {
 97         root = merge(root,newnode(i));
 98     }
 99     while (m--) {
100         int l,r;
101         scanf("%d%d",&l,&r);
102         reverse(l,r);
103     }
104     ldr(root);
105     return 0;
106 }