[关闭]
@2368860385 2018-02-03T07:17:10.000000Z 字数 21555 阅读 157

省选数据结构模板

这边不包括属于NOIP难度级别的基础数据结果，包括并查集，树状数组，

快速读入

  1. inline ll read(){
  2.     ll f=1,x=0;char ch;
  3.     do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
  4.     do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
  5.     return f*x;
  6. }

线段树 洛谷 P3372

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上x
  2. 求出某区间每一个数的和
  1. #include <bits/stdc++.h>
  2. const int N = 100005;
  3. typedef long long ll;
  4. using namespace std;
  5. int a[N], n, m;
  7. //快读read()略
  9. ll sumv[N << 2], addv[N << 2];
  10. #define lson    (o << 1)
  11. #define rson    (o << 1 | 1)
  12. inline void pushup( int o ) {
  13.     sumv[o] = sumv[lson] + sumv[rson];
  14. }
  16. inline void pushdown( int o, int l, int r ) {
  17.     if ( !addv[o] )
  18.         return;
  19.     ll tag = addv[o]; addv[o] = 0; int mid = (l + r) >> 1;
  20.     addv[lson]  += tag; addv[rson] += tag;
  21.     sumv[lson]  += tag * 1LL * (mid - l + 1); sumv[rson] += tag * 1LL * (r - mid);
  22. }
  24. inline void build( int o, int l, int r ) {
  25.     if ( l == r ) {
  26.         sumv[o] = a[l]; return;
  27.     }
  28.     int mid = (l + r) >> 1;
  29.     build( lson, l, mid ); build( rson, mid + 1, r );
  30.     pushup( o );
  31. }
  33. inline void optadd( int o, int l, int r, int ql, int qr, ll v ) {
  34.     if ( ql <= l && r <= qr ) {
  35.         sumv[o] += v * 1LL * (r - l + 1); addv[o] += v; return;
  36.     }
  37.     int mid = (l + r) >> 1; pushdown( o, l, r );
  38.     if ( ql <= mid )
  39.         optadd( lson, l, mid, ql, qr, v );
  40.     if ( qr > mid )
  41.         optadd( rson, mid + 1, r, ql, qr, v );
  42.     pushup( o );
  43. }
  45. inline ll querysum( int o, int l, int r, int ql, int qr ) {
  46.     if ( ql <= l && r <= qr )
  47.         return(sumv[o]);
  48.     pushdown( o, l, r );
  49.     int mid = (l + r) >> 1; ll ans = 0;
  50.     if ( ql <= mid )
  51.         ans += querysum( lson, l, mid, ql, qr );
  52.     if ( qr > mid )
  53.         ans += querysum( rson, mid + 1, r, ql, qr );
  54.     return(ans);
  55. }
  57. int main() {
  58.     n = read(); m = read();
  59.     for ( int i = 1; i <= n; i++ )
  60.     a[i] = read();
  61.     build( 1, 1, n );
  62.     while ( m-- ) {
  63.         int opt = read(), l = read(), r = read();
  64.         if ( opt == 1 ) {
  65.             ll k = read(); optadd( 1, 1, n, l, r, k );
  66.         }else printf( "%lld\n", querysum( 1, 1, n, l, r ) );
  67.     }
  68. }

平衡树(splay 伸展树) 洛谷 P3369

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入x数
  2. 删除x数(若有多个相同的数，因只删除一个)
  3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x，且最大的数)
  6. 求x的后继(后继定义为大于x，且最小的数)
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cstdlib>
  6. #define maxn 100010
  7. using namespace std;
  8. struct Splay {
  9.     struct Node {
  10.         int v, s;
  11.         Node    *ch[2];
  12.         void maintain() {
  13.             s = ch[0]->s + ch[1]->s + 1;
  14.         }
  15.         int cmp( int k ) {
  16.             int d = k - ch[0]->s;
  17.             if ( d == 1 )
  18.                 return(-1);
  19.             return(d <= 0 ? 0 : 1);
  20.         }
  21.     };
  22.     Node    Pr[maxn], *root, *null; int cnt;
  23.     void    init() {
  24.         cnt = 0;
  25.         null = &Pr[0]; null->s = 0; null->v = 123456; root = null;
  26.     }
  27.     Node* New( int x ) {
  28.         Pr[++cnt].v = x; Pr[cnt].ch[0] = Pr[cnt].ch[1] = null; Pr[cnt].s = 1;
  29.         return(&Pr[cnt]);
  30.     }
  31.     void rotate( Node* &i, int d ) {
  32.         Node* k = i->ch[d ^ 1];
  33.         i->ch[d ^ 1]            = k->ch[d]; k->ch[d] = i;
  34.         i->maintain(); k->maintain(); i = k;
  35.     }
  36.     void splay( Node* &i, int k ) {
  37.         int d = i->cmp( k );
  38.         if ( d == 1 )
  39.             k -= i->ch[0]->s + 1;
  40.         if ( d != -1 ) {
  41.             Node    *p  = i->ch[d]; int d2 = p->cmp( k );
  42.             int k2  = d2 == 0 ? k : k - p->ch[0]->s - 1;
  43.             if ( d2 != -1 )
  44.             {
  45.                 splay( p->ch[d2], k2 );
  46.                 if ( d == d2 )
  47.                     rotate( i, d ^ 1 );
  48.                 else rotate( i->ch[d], d );
  49.             }
  50.             rotate( i, d ^ 1 );
  51.         }
  52.     }
  53.     void Insert( Node* &i, int x, int & d ) {
  54.         if ( i == null ) {
  55.             i = New( x ); return;
  56.         }
  57.         if ( x <= i->v )
  58.             Insert( i->ch[0], x, d );
  59.         else d += i->ch[0]->s + 1, Insert( i->ch[1], x, d );
  60.         if ( i != null )
  61.             i->maintain();
  62.     }
  63.     void insert( int x ) {
  64.         int d = 1;
  65.         Insert( root, x, d );
  66.         splay( root, d );
  67.     }
  68.     int find( int x ) {
  69.         int ans = 0; Node *p = root; bool flag = false;
  70.         while ( p != null ) {
  71.             if ( p->v == x )
  72.                 flag = true;
  73.             if ( x <= p->v )
  74.                 p = p->ch[0];
  75.             else ans += p->ch[0]->s + 1, p = p->ch[1];
  76.         }
  77.         if ( !flag )
  78.             return(0);
  79.         return(ans + 1);
  80.     }
  81.     int kth( Node* i, int k ) {
  82.         if ( k == i->ch[0]->s + 1 )
  83.             return(i->v);
  84.         if ( k <= i->ch[0]->s )
  85.             return(kth( i->ch[0], k ) );
  86.         else return(kth( i->ch[1], k - i->ch[0]->s - 1 ) );
  87.     }
  88.     int pre( int x ) {
  89.         Node* p = root; int ans;
  90.         while ( p != null ) {
  91.             if ( p->v < x )
  92.                 ans = p->v;
  93.             if ( x <= p->v )
  94.                 p = p->ch[0];
  95.             else p = p->ch[1];
  96.         }
  97.         return(ans);
  98.     }
  99.     int nex( int x ) {
  100.         Node* p = root; int ans;
  101.         while ( p != null ) {
  102.             if ( p->v > x )
  103.                 ans = p->v;
  104.             if ( x >= p->v )
  105.                 p = p->ch[1];
  106.             else p = p->ch[0];
  107.         }
  108.         return(ans);
  109.     }
  110.     Node* merge( Node* left, Node* right ) {
  111.         if ( left == null )
  112.             return(right);
  113.         if ( right == null )
  114.             return(left);
  115.         splay( left, left->s );
  116.         left->ch[1] = right;
  117.         left->maintain();
  118.         return(left);
  119.     }
  120.     void Delete( int x ) {
  121.         int d = find( x );
  122.         if ( !d )
  123.             return;
  124.         splay( root, d );
  125.         root = merge( root->ch[0], root->ch[1] );
  126.     }
  127. }   splay;
  130. int main() {
  131.     int n;
  132.     scanf( "%d", &n );
  133.     splay.init();
  134.     while ( n-- ) {
  135.         int opt, x;
  136.         scanf( "%d%d", &opt, &x );
  137.         if ( opt == 1 ) splay.insert( x );
  138.         if ( opt == 2 ) splay.Delete( x );
  139.         if ( opt == 3 ) printf( "%d\n", splay.find( x ) );
  140.         if ( opt == 4 )  int k = splay.kth( splay.root, x ); printf( "%d\n", k );
  141.         if ( opt == 5 ) printf( "%d\n", splay.pre( x ) );
  142.         if ( opt == 6 ) printf( "%d\n", splay.nex( x ) );
  143.     }
  144.     return(0);
  145. }

平衡树(旋转Treap) 洛谷 P3369

题面同上

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #define N   100005
  6. #define inf 1000000007
  7. using namespace std;
  8. int n;
  10. //快读read()略
  12. struct Treap {
  13.     int     l[N], r[N], val[N], rnd[N], size[N], w[N], sz, ans, rt;
  15.     inline void pushup( int x ) {
  16.         size[x] = size[l[x]] + size[r[x]] + w[x];
  17.     }
  18.     void rturn( int &k ) {
  19.         int t = l[k]; l[k] = r[t]; r[t] = k; size[t] = size[k]; pushup( k ); k = t;
  20.     }
  21.     void lturn( int &k ) {
  22.         int t = r[k]; r[k] = l[t]; l[t] = k; size[t] = size[k]; pushup( k ); k = t;
  23.     }
  24.     void ins( int &k, int x ) {
  25.         if ( k == 0 ) {
  26.             sz++; k = sz; size[k] = 1; w[k] = 1; val[k] = x; rnd[k] = rand(); return;
  27.         }
  28.         size[k]++;
  29.         if ( val[k] == x )
  30.             w[k]++;
  31.         else if ( val[k] < x ) {
  32.             ins( r[k], x ); 
  33.             if ( rnd[r[k]] < rnd[k] )
  34.                 lturn( k );
  35.         }else{
  36.             ins( l[k], x ); 
  37.             if ( rnd[l[k]] < rnd[k] )
  38.                 rturn( k );
  39.         }
  40.     }
  42.     void del( int &k, int x ) {
  43.         if ( !k )
  44.             return;
  45.         if ( val[k] == x ) {
  46.             if ( w[k] > 1 ) {
  47.                 w[k]--; size[k]--; return;
  48.             }
  49.             if ( l[k] * r[k] == 0 )
  50.                 k = l[k] + r[k];
  51.             else if ( rnd[l[k]] < rnd[r[k]] )
  52.                 rturn( k ), del( k, x );
  53.             else lturn( k ), del( k, x );
  54.         }else if ( val[k] < x ) {
  55.             size[k]--; del( r[k], x );
  56.         }else { 
  57.             size[k]--; del( l[k], x ); 
  58.         }
  59.     }
  61.     int queryrank( int k, int x ) {
  62.         if ( !k )
  63.             return(0);
  64.         if ( val[k] == x )
  65.             return(size[l[k]] + 1);
  66.         else if ( x > val[k] )
  67.             return(size[l[k]] + w[k] + queryrank( r[k], x ) );
  68.         else return(queryrank( l[k], x ) );
  69.     }
  71.     int querynum( int k, int x ) {
  72.         if ( k == 0 )
  73.             return(0);
  74.         if ( x <= size[l[k]] )
  75.             return(querynum( l[k], x ) );
  76.         else if ( x > size[l[k]] + w[k] )
  77.             return(querynum( r[k], x - size[l[k]] - w[k] ) );
  78.         else return(val[k]);
  79.     }
  81.     void querypre( int k, int x ) {
  82.         if ( k == 0 )
  83.             return;
  84.         if ( val[k] < x ) {
  85.             ans = k; querypre( r[k], x );
  86.         }else querypre( l[k], x );
  87.     }
  89.     void querysub( int k, int x ) {
  90.         if ( k == 0 )
  91.             return;
  92.         if ( val[k] > x ) {
  93.             ans = k; querysub( l[k], x );
  94.         }else querysub( r[k], x );
  95.     }
  96. } T;
  98. int main() {
  99.     n = read(); int opt, x; 
  100.     for ( int i = 1; i <= n; i++ ) {
  101.         opt = read(), x = read();
  102.         switch ( opt ) {
  103.         case 1: T.ins( T.rt, x ); break;
  104.         case 2: T.del( T.rt, x ); break;
  105.         case 3: printf( "%d\n", T.queryrank( T.rt, x ) ); break;
  106.         case 4: printf( "%d\n", T.querynum( T.rt, x ) ); break;
  107.         case 5: T.ans = 0; T.querypre( T.rt, x ); printf( "%d\n", T.val[T.ans] ); break;
  108.         case 6: T.ans = 0; T.querysub( T.rt, x ); printf( "%d\n", T.val[T.ans] ); break;
  109.         }
  110.     }
  111.     return(0);
  112. }

平衡树(非旋Treap) 洛谷 P3369

题面同上

  1. #include < bits/stdc ++.h>
  2. #define N 100010
  3. #define mp make_pair
  4. using namespace std; 
  5. typedef pair < int, int> par; 
  6. int n, x, rt; 
  7. struct Treap_Without_rotate{
  8.     int ls[N], rs[N], rnd[N], val[N], size[N], cnt; 
  9.     inline void pushup(int x){size[x] = size[ls[x]] + size[rs[x]] + 1; }
  10.     par split(int k, int x){
  11.         if(!x)return mp(0, k); 
  12.         int l = ls[k], r = rs[k]; 
  13.         if(x == size[l]){
  14.             ls[k] = 0; pushup(k); 
  15.             return mp(l, k); 
  16.         }
  17.         if(x == size[l] + 1){
  18.             rs[k] = 0; pushup(k); 
  19.             return mp(k, r); 
  20.         }
  21.         if(x < size[l]){
  22.             par tmp = split(l, x); 
  23.             ls[k] = tmp.second; pushup(k); 
  24.             return mp(tmp.first, k); 
  25.         }
  26.         par tmp = split(r, x - size[l] - 1); 
  27.         rs[k] = tmp.first; pushup(k); 
  28.         return mp(k, tmp.second); 
  29.     }
  30.     int merge(int x, int y){
  31.         if(x == 0 || y == 0)
  32.                 return x + y; 
  33.         if(rnd[x] < rnd[y]){
  34.             rs[x] = merge(rs[x], y); pushup(x); 
  35.             return x; 
  36.         }
  37.         else{
  38.             ls[y] = merge(x, ls[y]); pushup(y); 
  39.             return y; 
  40.         }
  41.     }
  42.     int queryrank(int x, int k){
  43.         int ans = 0, tmp = (int)1e9; 
  44.         while(k){
  45.             if(x == val[k])tmp = min(tmp, ans + size[ls[k]] + 1); 
  46.             if(x>val[k])ans +  = size[ls[k]] + 1, k = rs[k]; 
  47.             else k = ls[k]; 
  48.         }
  49.         return tmp == (int)1e9?ans:tmp; 
  50.     }
  51.     int find(int x, int k){
  52.         for(; ; ){
  53.             if(size[ls[k]] == x - 1)return val[k]; 
  54.             if(size[ls[k]]>x - 1)k = ls[k]; 
  55.             else x = x - size[ls[k]] - 1, k = rs[k]; 
  56.         }
  57.     }
  58.     int querypre(int x, int k){
  59.         int ans =  -(int)1e9; 
  60.         while(k){
  61.             if(val[k] < x)ans = max(ans, val[k]), k = rs[k]; 
  62.             else k = ls[k]; 
  63.         }
  64.         return ans; 
  65.     }
  66.     int querysub(int x, int k){
  67.         int ans = (int)1e9; 
  68.         while(k){
  69.             if(val[k]>x)ans = min(ans, val[k]), k = ls[k]; 
  70.             else k = rs[k]; 
  71.         }
  72.         return ans; 
  73.     }
  74.     void ins(int x){
  75.         int k = queryrank(x, rt); par tmp = split(rt, k); 
  76.         val[ ++cnt] = x; rnd[cnt] = rand(); size[cnt] = 1; 
  77.         rt = merge(tmp.first, cnt); rt = merge(rt, tmp.second); 
  78.     }
  79.     void del(int x){
  80.         int k = queryrank(x, rt); par t1 = split(rt, k), t2 = split(t1.first, k - 1); 
  81.         rt = merge(t2.first, t1.second); 
  82.     }
  83. } T; 
  85. int main(){
  86.     n = read(); srand(2333333); 
  87.     for(int i = 1; i <  = n; i ++){
  88.         int opt = read(), x = read(); 
  89.         if(opt == 1)T.ins(x); 
  90.         if(opt == 2)T.del(x); 
  91.         if(opt == 3)printf("%d\n", T.queryrank(x, rt)); 
  92.         if(opt == 4)printf("%d\n", T.find(x, rt)); 
  93.         if(opt == 5)printf("%d\n", T.querypre(x, rt)); 
  94.         if(opt == 6)printf("%d\n", T.querysub(x, rt)); 
  95.     }
  96.     return 0; 
  97. }

树链剖分 洛谷P3384

如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

  1. 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
  2. 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
  3. 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
  4. 格式： 4 x 表示求以x为根节点的子树内所有节点值之和
  1. #include<cstdio>
  2. #include<cmath>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std; 
  6. const int maxn = 300000; 
  7. struct tree{int l, r, v, lazy; }node[2*maxn]; 
  8. int first[maxn], last[maxn], nxt[maxn], a[maxn], w[maxn], tid[maxn], 
  9.     e[maxn], top[maxn], rank[maxn], size[maxn], r[maxn], tt[maxn], father[maxn], 
  10.     n, m, k, mod, x, y, g, i, s, tot, z; 
  12. void add(int x, int y){
  13.     a[++k] = y; tt[x]++; 
  14.     if(first[x] == 0)
  15.         first[x] = k; 
  16.     else 
  17.         nxt[last[x]] = k; 
  18.     last[x] = k; 
  19. }
  21. void build(int u, int l, int r){
  22.     int mid = (l + r) / 2; node[u].l = l; node[u].r = r; 
  23.     if(l == r)return; 
  24.     build(u*2, l, mid); 
  25.     build(u*2+1, mid+1, r); 
  26. }
  28. void down(int u){
  29.     if(node[u].lazy == 0)return; 
  30.     node[u].v += node[u].lazy*(node[u].r-node[u].l+1)%mod; 
  31.     node[u*2].lazy += node[u].lazy; node[u*2+1].lazy += node[u].lazy; 
  32.     node[u].lazy = 0; 
  33. }
  35. void change(int u, int l, int r, int cont){
  36.     if(node[u].l > r||node[u].r<l)return; 
  37.     if(node[u].l >= l&&node[u].r< = r){
  38.         node[u].lazy += cont; down(u); 
  39.         return; 
  40.     }
  41.     change(u*2, l, r, cont); 
  42.     change(u*2+1, l, r, cont); 
  43.     down(u*2); down(u*2+1); 
  44.     node[u].v = (node[u*2].v+node[u*2+1].v)%mod; 
  45. }
  47. int query(int u, int l, int r){
  48.     if(node[u].l > r||node[u].r<l)return 0; 
  49.     if(node[u].l >= l&&node[u].r< = r)return (node[u].v)%mod; 
  50.     down(u*2); down(u*2+1); 
  51.     return(query(u*2, l, r)+query(u*2+1, l, r))%mod; 
  52. }
  53. void dfs(int u, int fa){
  54.     int i = 0; size[u] = 1; r[u] = r[fa]+1; 
  55.     father[u] = fa; 
  56.     for(i = first[u]; i; i = nxt[i])
  57.     if(a[i]! = fa)
  58.     {
  59.         dfs(a[i], u); 
  60.         size[u] += size[a[i]]; 
  61.     }
  62. }
  63. void dfs2(int u, int head){
  64.     int i, mson = 0; 
  65.     top[u] = head; tid[u] = ++tot; rank[tid[u]] = tot; 
  66.     change(1, tot, tot, w[u]); 
  67.     if(tt[u] == 1&&u! = s){
  68.         e[u] = u; 
  69.         return; 
  70.     }
  71.     for(i = first[u]; i>0; i = nxt[i])
  72.     if(size[a[i]]<size[u]&&size[a[i]]>size[mson])
  73.         mson = a[i]; 
  74.     dfs2(mson, head); 
  75.     e[u] = e[mson]; 
  76.     for(i = first[u]; i>0; i = nxt[i])
  77.     if(size[a[i]]<size[u]&&a[i]! = mson){
  78.         dfs2(a[i], a[i]); e[u] = e[a[i]]; 
  79.     }
  80. }
  82. void schange(int x, int y, int cont){
  83.     while(top[x]! = top[y]) {
  84.         if(r[top[x]]<r[top[y]])swap(x, y); 
  85.         change(1, tid[top[x]], tid[x], cont); 
  86.         x = father[top[x]]; 
  87.     }
  88.     if(tid[x]>tid[y])swap(x, y); 
  89.     change(1, tid[x], tid[y], cont); 
  90. }
  91. int squery(int x, int y){
  92.     int ans = 0; 
  93.     while(top[x]! = top[y]){
  94.         if(r[top[x]]<r[top[y]])swap(x, y); 
  95.         ans += query(1, tid[top[x]], tid[x]); 
  96.         ans %= mod; 
  97.         x = father[top[x]]; 
  98.     }
  99.     if(tid[x]>tid[y])swap(x, y); 
  100.     ans += query(1, tid[x], tid[y]); 
  101.     ans %= mod; 
  102.     return ans; 
  103. }
  104. int main(){
  105.     scanf("%d%d%d%d", &n, &m, &s, &mod); 
  106.     for(i = 1; i< = n; i++)scanf("%d", &w[i]); 
  107.     for(i = 1; i< = n-1; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x); }
  108.     build(1, 1, n);  
  109.     dfs(s, 0); 
  110.     dfs2(s, s); 
  111.     for(i = 1; i< = m; i++){
  112.         scanf("%d", &g); 
  113.         if(g == 1){
  114.             scanf("%d%d%d", &x, &y, &z); 
  115.             schange(x, y, z); 
  116.         }
  117.         if(g == 2){
  118.             scanf("%d%d", &x, &y); 
  119.             printf("%d\n", squery(x, y)%mod); 
  120.         }
  121.         if(g == 3){
  122.             scanf("%d%d", &x, &y); 
  123.             change(1, tid[x], tid[e[x]], y); 
  124.         }
  125.         if(g == 4){
  126.             scanf("%d", &x); 
  127.             printf("%d\n", query(1, tid[x], tid[e[x]])%mod); 
  128.         }
  129.     }
  130.     return 0; 
  131. }

给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. #include<cmath>
  7. #define N 300005
  8. using namespace std;
  9. int n,m,top;
  10. int c[N][2],fa[N],v[N],s[N],q[N];
  11. bool rev[N];
  12. //略去快速读入read()
  13. void update(int x){
  14.     int l=c[x][0],r=c[x][1];
  15.     s[x]=s[l]^s[r]^v[x];
  16. }
  17. void pushdown(int x){
  18.     int l=c[x][0],r=c[x][1];
  19.     if(rev[x]){
  20.         rev[x]^=1;rev[l]^=1;rev[r]^=1;
  21.         swap(c[x][0],c[x][1]);
  22.     }
  23. }
  24. bool isroot(int x){
  25.     return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
  26. }
  27. void rotate(int x){
  28.     int y=fa[x],z=fa[y],l,r;
  29.     if(c[y][0]==x)l=0;else l=1;r=l^1;
  30.     if(!isroot(y)) {
  31.         if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;
  32.     }
  33.     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
  34.     c[y][l]=c[x][r];c[x][r]=y;
  35.     update(y);update(x);
  36. }
  37. void splay(int x){
  38.     top=0;q[++top]=x;
  39.     for(int i=x;!isroot(i);i=fa[i])
  40.         q[++top]=fa[i];
  41.     for(int i=top;i;i--)
  42.         pushdown(q[i]);
  43.     while(!isroot(x)){
  44.         int y=fa[x],z=fa[y];
  45.         if(!isroot(y))
  46.         {
  47.             if(c[y][0]==x^c[z][0]==y)rotate(x);
  48.             else rotate(y);
  49.         }
  50.         rotate(x);
  51.     }
  52. }
  53. void access(int x){
  54.     for(int t=0;x;t=x,x=fa[x])
  55.         splay(x),c[x][1]=t,update(x);
  56. }
  57. void makeroot(int x){
  58.     access(x);splay(x);rev[x]^=1;
  59. }
  60. int find(int x){
  61.     access(x);splay(x);
  62.     while(c[x][0])x=c[x][0];
  63.     return x;
  64. }
  65. void cut(int x,int y){
  66.     makeroot(x);access(y);splay(y);
  67.     if(c[y][0]==x)c[y][0]=fa[x]=0;
  68. }
  69. void link(int x,int y){
  70.     makeroot(x);fa[x]=y;
  71. }
  72. int main(){
  73.     n=read();m=read();
  74.     for(int i=1;i<=n;i++)v[i]=read(),s[i]=v[i];
  75.     int opt,x,y;
  76.     for(int i=1;i<=m;i++){
  77.         opt=read();x=read();y=read();
  78.         switch(opt){
  79.         case 0:makeroot(x);access(y);splay(y);printf("%d\n",s[y]);break;
  80.         case 1:if(find(x)!=find(y))link(x,y);break;
  81.         case 2:if(find(x)==find(y))cut(x,y);break;
  82.         case 3:access(x);splay(x);v[x]=y;update(x);break;
  83.         }
  84.     }
  85.     return 0;
  86. }

可持久化Trie 洛谷P2633

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

nzhtl1477认为这个数据结构应该叫fingertree

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #define ratio 4
  5. #define new_Node(s, v, a, b) (& (* st[ cnt++ ] = Node(s, v, a, b)))
  6. #define merge(a, b) new_Node(a->size + b->size, b->value, a, b)
  7. #define MAXN 100010
  9. using namespace std;
  11. struct Node {
  12.     int size, value;
  13.     Node * left, * right;
  14.     Node(int s, int v, Node * a, Node * b) : size(s), value(v), left(a), right(b) {}
  15.     Node() {}
  16. } * null, * root[ MAXN ], * st[4000000], t[4000000];
  18. int n, m, cnt, x, y, k, a[ MAXN ], fa[ MAXN ][20], dep[ MAXN ], ans;
  19. vector < int > linker[ MAXN ];
  21. void insert(int x, Node * cur) {
  22.     if(cur->size == 1) {
  23.         cur->left = new_Node(1, min(cur->value, x), null, null); 
  24.         cur->right = new_Node(1, max(cur->value, x), null, null);
  25.     }
  26.     else insert(x, x > cur->left->value ? cur->right : cur->left);
  27.     cur->size++, cur->value = cur->right->value;
  28. }
  30. int rank(int x, Node * cur) {
  31.     if(cur->size == 1) return 1;
  32.     return x > cur->left->value ? rank(x, cur->right) + cur->left->size : rank(x, cur->left);
  33. }
  35. int find(int x, Node * cur) {
  36.     if(cur->size == 1) return cur->value;
  37.     return x > cur->left->size ? find(x - cur->left->size, cur->right) : find(x, cur->left);
  38. }
  40. Node * modify(int x, Node * a) {
  41.     Node * cur = new_Node(a->size, a->value + 1, a->left, a->right);
  42.     if(cur->left)
  43.         if(x > cur->left->size) cur->right = modify(x - cur->left->size, cur->right);
  44.         else cur->left = modify(x, cur->left);
  45.     return cur;
  46. }
  48. int find(int x, Node * a, Node * b, Node * c, Node * d) {
  49.     int mid = a->left->value + b->left->value - c->left->value - d->left->value;
  50.     if(a->size == 1) return 1;
  51.     if(x > mid) return find(x - mid, a->right, b->right, c->right, d->right) + a->left->size;
  52.     return find(x, a->left, b->left, c->left, d->left);
  53. }
  55. Node * build(int l, int r) {
  56.     if(l == r) return new_Node(1, 0, null, null);
  57.     Node * left = build(l, (l + r) >> 1), * right = build(((l + r) >> 1) + 1, r);
  58.     return new_Node(r - l + 1, 0, left, right);
  59. }
  61. #define cur linker[x][i]
  62. void dfs(int x) {
  63.     root[x] = modify(rank(a[x], root[ n + 1 ]), root[ fa[x][0] ]);
  64.     dep[x] = dep[ fa[x][0] ] + 1;
  65.     for(int i = 0 ; i < linker[x].size() ; i++)
  66.         if(cur != fa[x][0])
  67.             fa[ cur ][0] = x, dfs(cur);
  68. }
  70. inline int lca(int x, int y) {
  71.     if(dep[x] < dep[y]) swap(x, y);
  72.     for(register int i = 0 ; i < 20 ; i++)
  73.         if((dep[x] - dep[y]) & (1 << i))
  74.             x = fa[x][i];
  75.     if(x == y) return x;
  76.     for(register int i = 19 ; i >= 0 ; i--)
  77.         if(fa[x][i] != fa[y][i])
  78.             x = fa[x][i], y = fa[y][i];
  79.     return fa[x][0];
  80. }
  82. //略去读入优化read()
  84. inline void addedge(int x, int y) {
  85.     linker[x].push_back(y), linker[y].push_back(x);
  86. }
  88. int main() {
  89.     n = read(), m = read();
  90.     for(register int i = 0 ; i < 4000000 ; i++) st[i] = & t[i];
  91.     null = new_Node(0, 0, 0, 0);
  92.     root[ n + 1 ] = new_Node(1, 2147483647, null, null);
  93.     root[0] = build(1, n);
  94.     for(register int i = 1 ; i <= n ; i++) insert(a[i] = read(), root[ n + 1 ]);
  95.     for(register int i = 1 ; i < n ; i++) addedge(read(), read());
  96.     dfs(1);
  97.     for(register int j = 1 ; j < 20 ; j++)
  98.         for(register int i = 1 ; i <= n ; i++)
  99.             fa[i][j] = fa[ fa[i][j - 1] ][j - 1];
  100.     while(m--)
  101.     {
  102.         x = read() ^ ans, y = read(), k = read();
  103.         int l = lca(x, y);
  104.         printf("%d", ans = find(find(k, root[x], root[y], root[l], root[ fa[l][0] ]), root[ n + 1 ]));
  105.         if(m) putchar('\n');
  106.     }
  107.     return 0;
  108. }

左偏树 可并堆 洛谷P3377

如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）

操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. const int N=101000;
  5. struct Leftist{
  6.     int lch,rch,key,fa,dist;
  7. }h[N];
  8. int n,m;
  9. // 省略读入优化read()
  10. int merge(int u,int v){
  11.     if (!u || !v)return u+v;
  12.     if (h[u].key>h[v].key || (h[u].key==h[v].key && u>v))swap(u,v);
  13.     int &ul=h[u].lch,&ur=h[u].rch;
  14.     ur=merge(ur,v);
  15.     h[ur].fa=u;
  16.     if (h[ul].dist<h[ur].dist)swap(ul,ur);
  17.     h[u].dist=h[ur].dist+1;
  18.     return u;
  19. }
  20. void erase(int u){
  21.     int ul=h[u].lch,ur=h[u].rch;
  22.     h[u].key=-1;h[ul].fa=0;h[ur].fa=0;
  23.     merge(ul,ur);
  24. }
  25. int find(int x){
  26.     return h[x].fa?find(h[x].fa):x;
  27. }
  28. int main(){
  29.     n=read(),m=read();
  30.     h[0].dist=-1;
  31.     for (int i=1;i<=n;i++)
  32.         h[i].key=read();
  33.     for (int i=1;i<=m;i++){
  34.         int opt,x,y;
  35.         opt=read(),x=read();
  36.         if (opt==1){
  37.             y=read();
  38.             if (h[x].key!=-1 && h[y].key!=-1){
  39.                 int p=find(x),q=find(y);
  40.                 if (p!=q)merge(p,q);
  41.             }
  42.         }else if (opt==2){
  43.             if (h[x].key==-1)printf("-1\n");
  44.             else{
  45.                 int p=find(x);
  46.                 printf("%d\n",h[p].key);
  47.                 erase(p);
  48.             }
  49.         }
  50.     }
  51.     return 0;
  52. }

树套树 线段树套treap 洛谷P3380

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

  1. 查询k在区间内的排名
  2. 查询区间内排名为k的值
  3. 修改某一位值上的数值
  4. 查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)
    5.查询k在区间内的后继(后继定义为严格大于x，且最小的数，若不存在输出2147483647)

这题有多种复杂度不同写法，下面给出的是一个线段树套Treap平衡树的做法。其中的Treap是另外一种写法。

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #pragma GCC optimize("O3")
  6. #define N 50020
  7. #define M 100000000
  8. #define INFINITE 2147483647
  9. using namespace std;
  11. class Node {
  12. public:
  13.     Node *s[2];
  14.     int v, e, w, z;
  16.     Node(int _v, int _e, int _w, int _z) : v(_v), e(_e), w(_w), z(_z){
  17.         s[0] = s[1] = NULL;
  18.         return;
  19.     }
  21.     int Size(int k) {
  22.         return s[k] ? s[k] -> z : 0;
  23.     }
  25.     void Update(void) {
  26.         z = Size(0) + Size(1) + w;
  27.         return;
  28.     }
  29. };
  31. class Treap {
  32. public:
  33.     Node *r;
  35.     void RotateTreap(Node *&x, int k) {
  36.         Node *t;
  38.         t = x -> s[!k];
  39.         x -> s[!k] = t -> s[k];
  40.         t -> s[k] = x;
  42.         x -> Update();
  43.         t -> Update();
  44.         x = t;
  46.         return;
  47.     }
  49.     void InsertTreap(Node *&x, int v, int w = 1) {
  50.         if(!x)
  51.             x = new Node(v, rand(), w, w);
  52.         else if(x -> v == v)
  53.             x -> w += w;
  54.         else if(x -> v < v) {
  55.             InsertTreap(x -> s[1], v, w);
  56.             if(x -> s[1] -> e < x -> e)
  57.                 RotateTreap(x, 0);
  58.         }
  59.         else {
  60.             InsertTreap(x -> s[0], v, w);
  61.             if(x -> s[0] -> e < x -> e)
  62.                 RotateTreap(x, 1);
  63.         }
  64.         x -> Update();
  66.         return;
  67.     }
  69.     void RemoveTreap(Node *&x, int v) {
  70.         Node *t;
  71.         int k;
  73.         if(x -> v == v) {
  74.             if(x -> w > 1)
  75.                 x -> w --;
  76.             else {
  77.                 if(!x -> s[0]) {
  78.                     t = x;
  79.                     x = x -> s[1];
  81.                     delete t;
  82.                     return;
  83.                 }
  84.                 if(!x -> s[1]) {
  85.                     t = x;
  86.                     x = x -> s[0];
  88.                     delete t;
  89.                     return;
  90.                 }
  91.                 k = x -> s[0] -> e < x -> s[1] -> e;
  92.                 RotateTreap(x, k);
  93.                 RemoveTreap(x -> s[k], v);
  94.             }
  95.         }
  96.         else {
  97.             k = x -> v < v;
  98.             RemoveTreap(x -> s[k], v);
  99.             if(x -> s[k] && x -> s[k] -> e < x -> e)
  100.                 RotateTreap(x, x -> s[k] -> e < x -> e);
  101.         }
  102.         x -> Update();
  104.         return;
  105.     }
  107.     int RankTreap(Node *x, int v) {
  108.         int o;
  109.         for(o = 0;x;)
  110.             if(x -> v == v) {
  111.                 //printf("G %d\n", x -> Size(0));
  112.                 return o + x -> Size(0);
  113.             }
  114.             else if(x -> v < v) {
  115.                 o += x -> Size(0) + x -> w;
  116.                 x = x -> s[1];
  117.             }
  118.             else
  119.                 x = x -> s[0];
  120.         return o;
  121.     }
  123.     int CountTreap(Node *x, int v) {
  124.         while(x) {
  125.             if(x -> v == v)
  126.                 return x -> w;
  127.             x = x -> s[x -> v < v];
  128.         }
  129.         return 0;
  130.     }
  132.     int PrevTreap(Node *x, int v) {
  133.         int o;
  135.         for(o = -INFINITE;x;)
  136.             if(x -> v >= v)
  137.                 x = x -> s[0];
  138.             else {
  139.                 o = max(o, x -> v);
  140.                 x = x -> s[1];
  141.             }
  143.         return o;
  144.     }
  146.     int SuffTreap(Node *x, int v) {
  147.         int o;
  149.         for(o =  INFINITE;x;)
  150.             if(x -> v <= v)
  151.                 x = x -> s[1];
  152.             else {
  153.                 o = min(o, x -> v);
  154.                 x = x -> s[0];
  155.             }
  157.         return o;
  158.     }
  160.     void MergeTreap(Node *x) {
  161.         if(!x)
  162.             return;
  163.         MergeTreap(x -> s[0]);
  164.         MergeTreap(x -> s[1]);
  165.         InsertTreap(r, x -> v, x -> w);
  167.         return;
  168.     }
  170. };
  172. class Segment {
  173. public:
  174.     Treap f[N * 4];
  176.     void BuildSegment(int *x, int i, int l, int r) {
  177.         if(l >= r) {
  178.             f[i].r = NULL;
  179.             f[i].InsertTreap(f[i].r, x[l]);
  181.             return;
  182.         }
  184.         BuildSegment(x, i * 2, l, (l + r) / 2);
  185.         BuildSegment(x, i * 2 + 1, (l + r) / 2 + 1, r);
  186.         f[i].r = NULL;
  187.         f[i].MergeTreap(f[i * 2].r);
  188.         f[i].MergeTreap(f[i * 2 + 1].r);
  189.         /*for(int t = l;t <= r;t ++)
  190.             f[i].InsertTreap(f[i].r, x[t]);*/
  191.         /*if(f[i * 2].r -> z > f[i * 2 + 1].r -> z) {
  192.             f[i] = f[i * 2];
  193.             f[i].MergeTreap(f[i * 2 + 1].r);
  194.         }
  195.         else {
  196.             f[i] = f[i * 2 + 1];
  197.             f[i].MergeTreap(f[i * 2].r);
  198.         }*/
  200.         return;
  201.     }
  203.     int RankSegment(int i, int l, int r, int s, int t, int v) {
  204.         if(r < s || l > t)
  205.             return 0;
  206.         if(l >= s && r <= t)
  207.             return f[i].RankTreap(f[i].r, v);
  209.         return RankSegment(i * 2, l, (l + r) / 2, s, t, v) + RankSegment(i * 2 + 1, (l + r) / 2 + 1, r, s, t, v);
  210.     }
  212.     int CountSegment(int i, int l, int r, int s, int t, int v) {
  213.         if(r < s || l > t)
  214.             return 0;
  215.         if(l >= s && r <= t) {
  216.             return f[i].RankTreap(f[i].r, v) + f[i].CountTreap(f[i].r, v);
  217.         }
  219.         return CountSegment(i * 2, l, (l + r) / 2, s, t, v) + CountSegment(i * 2 + 1, (l + r) / 2 + 1, r, s, t, v);
  220.     }
  222.     int PrevSegment(int i, int l, int r, int s, int t, int v) {
  223.         if(r < s || l > t)
  224.             return -INFINITE;
  225.         if(l >= s && r <= t)
  226.             return f[i].PrevTreap(f[i].r, v);
  228.         return max(PrevSegment(i * 2, l, (l + r) / 2, s, t, v), PrevSegment(i * 2 + 1, (l + r) / 2 + 1, r, s, t, v));
  229.     }
  231.     int SuffSegment(int i, int l, int r, int s, int t, int v) {
  232.         if(r < s || l > t)
  233.             return  INFINITE;
  234.         if(l >= s && r <= t)
  235.             return f[i].SuffTreap(f[i].r, v);
  237.         return min(SuffSegment(i * 2, l, (l + r) / 2, s, t, v), SuffSegment(i * 2 + 1, (l + r) / 2 + 1, r, s, t, v));
  238.     }
  240.     void SetSegment(int *x, int i, int l, int r, int p, int v) {
  241.         if(l > p || r < p)
  242.             return;
  243.         if(l == p && r == p) {
  244.             f[i].RemoveTreap(f[i].r, x[p]);
  245.             f[i].InsertTreap(f[i].r, v   );
  247.             return;
  248.         }
  250.         f[i].RemoveTreap(f[i].r, x[p]);
  251.         f[i].InsertTreap(f[i].r, v   );
  252.         SetSegment(x, i * 2, l, (l + r) / 2, p, v);
  253.         SetSegment(x, i * 2 + 1, (l + r) / 2 + 1, r, p, v);
  255.         return;
  256.     }
  258.     int KthSegment(int s, int t, int k, int n, pair<int, int> v) {
  259.         int l, m, r;
  261.         for(l = v.first - 1, r = v.second;l + 1 < r;) {
  262.             //printf("%d : %d\n", (l + r) / 2, CountSegment(1, 0, n - 1, s, t, m = (l + r) / 2));
  263.             if(CountSegment(1, 0, n - 1, s, t, m = (l + r) / 2) >= k)
  264.                 r = m;
  265.             else
  266.                 l = m;
  267.         }
  269.         return r;
  270.     }
  271. };
  273. class Segwin {
  274. private:
  275.     int n;
  276.     int f[N * 4];
  277.     int g[N * 4];
  279. public:
  280.     void BuildSegwin(int n, int *x) {
  281.         int i;
  283.         this -> n = n;
  284.         for(i = 0;i < n;i ++)
  285.             f[i + n] = g[i + n] = x[i];
  286.         for(i = n - 1;i > -1;i --) {
  287.             f[i] = min(f[i << 1], f[i << 1 | 1]);
  288.             g[i] = max(g[i << 1], g[i << 1 | 1]);
  289.         }
  291.         return;
  292.     }
  294.     pair<int, int> MixSegwin(int s, int t) {
  295.         pair<int, int> o;
  297.         for(o = make_pair(INFINITE, -INFINITE), s += n, t += n + 1;s < t;s >>= 1, t >>= 1) {
  298.             if(s & 1) {
  299.                 o.first  = min(o.first , f[s]);
  300.                 o.second = max(o.second, g[s]);
  301.                 s ++;
  302.             }
  303.             if(t & 1) {
  304.                 t --;
  305.                 o.first  = min(o.first , f[t]);
  306.                 o.second = max(o.second, g[t]);
  307.             }
  308.         }
  310.         return o;
  311.     }
  313.     void SetSegwin(int p, int v) {
  314.         for(p += n, f[p] = g[p] = v;p >>= 1;) {
  315.             f[p] = min(f[p << 1], f[p << 1 | 1]);
  316.             g[p] = max(g[p << 1], g[p << 1 | 1]);
  317.         }
  319.         return;
  320.     }
  321. };
  323. int a[N];
  324. Segment f;
  325. Segwin g;
  327. int main() {
  328.     int n, m, p, l, r, k;
  329.     int i;
  331.     scanf("%d %d", &n, &m);
  332.     for(i = 0;i < n;i ++)
  333.         scanf("%d", &a[i]);
  335.     f.BuildSegment(a, 1, 0, n - 1);
  336.     g.BuildSegwin(n, a);
  337.     while(m --) {
  338.         scanf("%d %d %d", &p, &l, &r);
  339.         if(p != 3) {
  340.             l --;
  341.             r --;
  342.             scanf("%d", &k);
  343.         }
  345.         if(p == 1)
  346.             printf("%d\n", f.RankSegment(1, 0, n - 1, l, r, k) + 1);
  347.         if(p == 2)
  348.             printf("%d\n", f.KthSegment(l, r, k, n, /*make_pair(0, M)*/g.MixSegwin(l, r)));
  349.             //printf("%d\n", f.CountSegment(1, 0, n - 1, l, r, k));
  350.         if(p == 3) {
  351.             f.SetSegment(a, 1, 0, n - 1, -- l, r);
  352.             g.SetSegwin(l, r);
  353.             a[l] = r;
  354.         }
  355.         if(p == 4)
  356.             printf("%d\n", f.PrevSegment(1, 0, n - 1, l, r, k));
  357.         if(p == 5)
  358.             printf("%d\n", f.SuffSegment(1, 0, n - 1, l, r, k));
  359.     }
  361.     return 0;
  362. }

莫队算法 洛谷P3604

n个人，每个人给了一个小写字母'a'到'z'作为编号

一个区间的人如果满足他们的编号重排之后可以成为一个回文串，则他们可以一起回归天空，即这个区间可以回归天空。

给了m个区间，每次求每个区间中有多少个子区间可以回归天空。

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <math.h>
  5. #include <algorithm>
  6. #define MAXN 60010
  8. using namespace std;
  10. int n , m , t , block , belong[ MAXN ];
  11. unsigned short cnt[1 << 26];
  12. char s[ MAXN ];
  13. unsigned int a[ MAXN ] , ans[ MAXN ] , res;
  15. struct ask
  16. {
  17.     int l , r , pos;
  18. } q[ MAXN ];
  20. inline bool cmp( const ask & a , const ask & b )
  21. {
  22.     return belong[ a.l ] ^ belong[ b.l ] ? belong[ a.l ] < belong[ b.l ] : belong[ a.l ] & 1 ? a.r < b.r : a.r > b.r;
  23. }
  25. inline void insert( int x )
  26. {
  27.     for( register int i = 0 ; i < t ; i++ )
  28.         res += cnt[ x ^ ( 1 << i ) ];
  29.     res += cnt[x]++;
  30. }
  32. inline void erase( int x )
  33. {
  34.     for( register int i = 0 ; i < t ; i++ )
  35.         res -= cnt[ x ^ ( 1 << i ) ];
  36.     res -= --cnt[x];
  37. }
  39. inline int read()
  40. {
  41.     register int x = 0 , ch = getchar();
  42.     while( !isdigit( ch ) ) ch = getchar();
  43.     while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar();
  44.     return x;
  45. }
  47. int main()
  48. {
  49.     scanf( "%d %d %s" , &n , &m , s + 1 );
  50.     for( register int i = 1 ; i <= n ; i++ ) t = max( t , s[i] - 'a' + 1 );
  51.     block = n / sqrt( m * 2 / 3 );
  52.     for( register int i = 1 ; i <= n ; i++ ) belong[i] = ( i - 1 ) / block , a[i] = a[i - 1] ^ ( 1ll << s[i] - 'a' );
  53.     for( register int i = 1 ; i <= m ; i++ )
  54.         q[i].l = read() , q[i].r = read() , q[i].pos = i;
  55.     sort( q + 1 , q + m + 1 , cmp );
  56.     for( int i = 1 , l = 1 , r = 0 ; i <= m ; i++ )
  57.     {
  58.         while( l > q[i].l ) insert( a[ --l ] );
  59.         while( r < q[i].r ) insert( a[ ++r ] );
  60.         while( l < q[i].l ) erase( a[ l++ ] );
  61.         while( r > q[i].r ) erase( a[ r-- ] );
  62.         insert( a[l - 1] );
  63.         ans[ q[i].pos ] = res;
  64.         erase( a[l - 1] );
  65.     }
  66.     for( register int i = 1 ; i <= m ; i++ )
  67.         printf( "%u\n" , ans[i] );
  68.     return 0;
  69. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注