ZOJ 2112 Dynamic Rankings（线段树树套平衡树） - c++编程基础

题意就是求区间第k大，不过有修改。

其实这题解法挺多，主席树套BIT的我之后再写，这次写了线段树套平衡树的2种解法，第一种是按权值建线段树套treap，treap里放的是数的位置，这种方法必须要离线，因为需要把修改的值也一起建树，第二种则是在线的，按区间建线段树套treap，treap里放的是数的大小。第一种建树复杂度是o(log^2n)，询问复杂度是o(log^2n)。修改复杂度o(log^2n)，第二种则差一些，建树复杂度是o(log^2n)，询问复杂度是o(log^3n)，修改复杂度o(log^2n)。

先说第一种，每一个线段树的节点是那个节点所含treap的根节点，然后查询的时候，左子树的含有[L,R]的点如果大于等于k，那么就到左子树去查，反之就把K-左子树[L,R]的点，到右子树查。一直走到根节点就查到了。修改的时候先删掉线段树中原来那个点的值，再插入。

第二种，第二种按照区间建树，建树的时候做法基本跟第一种是一样的。但是要注意有相同数字的问题，导致了treap里面那个cmp函数有些地方不能用。查询的时候就有个问题了，肯定是二分最大值也就是10^9，但是有重复值的问题，这样就导致小于答案的不一定是k-1个，这个问题我是用查询小于m，以及小于等于m的值来解决的。假设小于m的数有x个，小于等于m的数有y个，x <= k-1 && y>=k

才说明这个值是这个区间里数且满足题意。如果不满足x <= k-1，所以就往小的找，如果不满足y>=k就往大的找。

按权值建树：(660ms)

#pragma comment(linker, "/STACK:102400000,102400000")
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #includewww.2cto.com
                  
                    using namespace std; #define ll long long #define ull unsigned long long #define eps 1e-8 #define NMAX 201000 #define MOD 1000000 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define PI acos(-1) template
                   
                     inline void scan_d(T &ret) { char c; int flag = 0; ret=0; while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c == '-') { flag = 1; c = getchar(); } while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar(); if(flag) ret = -ret; } const int maxn = 60000+10; const int maxm = 10000+10; struct Node { Node* ch[2]; int r,v,s; int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } void maintain() { s = 1; s += ch[0]->s + ch[1]->s; } }treap[maxn*15]; int nodecnt; Node *null = &treap[0]; void node_init(Node* &o, int v) { o->ch[0] = o->ch[1] = null; o->r = rand(); o->v = v; o->s = 1; } Node* newnode() { Node *p = &treap[nodecnt++]; return p; } void rotate(Node* &o, int d) { Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k; } void insert(Node* &o, int k) { if(o == null) { o = newnode(); node_init(o,k); } else { int d = o->cmp(k);//无相同节点可以用 insert(o->ch[d],k); if(o->r < o->ch[d]->r) rotate(o,d^1); } o->maintain(); } void remove(Node* &o, int k) { int d = o->cmp(k); if(d == -1) { if(o->ch[0] != null && o->ch[1] != null) { int d2 = o->ch[0]->r > o->ch[1]->r ? 1 : 0; rotate(o,d2); remove(o->ch[d2],k); } else { if(o->ch[0] != null) o = o->ch[0]; else o = o->ch[1]; } } else remove(o->ch[d],k); if(o != null) o->maintain();//别忘了if null } int querytree(Node* &o, int l)//>=l有几个 { if(o == null) return 0; if(o->v >= l) return o->ch[1]->s+1+querytree(o->ch[0],l); return querytree(o->ch[1],l); } int a[maxn],b[maxn]; Node* T[maxn<<2]; struct Query { char flag; int l,r,k; }que[maxm]; void build(int l, int r, int rt) { T[rt] = null; if(l == r) return; int mid = (l+r)>>1; build(lson); build(rson); } void insertit(int L, int k, int l, int r, int rt) { insert(T[rt],k); if(l == r) return; int mid = (l+r)>>1; if(L <= mid) insertit(L, k, lson); else insertit(L, k, rson); } int query(int L, int R, int k, int l, int r, int rt) { if(l == r) return l; int mid = (l+r)>>1; if(T[rt<<1] != null) { int num = querytree(T[rt<<1],L)-querytree(T[rt<<1],R+1); if(num >= k) return query(L, R, k, lson); else return query(L, R, k-num, rson); } else return query(L, R, k, rson); } void removeit(int L, int k, int l, int r, int rt) { remove(T[rt], k); if(l == r) return; int mid = (l+r)>>1; if(L <= mid) removeit(L, k, lson); else removeit(L, k, rson); } void dfs(Node* &o) { if(o == null) return; dfs(o->ch[0]); printf("%d ",o->v); dfs(o->ch[1]); } int main() { #ifdef GLQ freopen("input.txt","r",stdin); // freopen("o.txt","w",stdout); #endif srand(time(NULL)); null->s = 0; int n,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); nodecnt = 1; int cnt = 0; for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); b[cnt++] = a[i]; } for(int i = 0; i < m; i++) { char tmp[5]; int l,r,k; scanf("%s",tmp); if(tmp[0] == 'Q') { que[i].flag = tmp[0]; scanf("%d%d%d",&que[i].l,&que[i].r,&que[i].k); } else { que[i].flag = tmp[0]; scanf("%d%d",&que[i].l,&que[i].k); b[cnt++] = que[i].k; } } sort(b,b+cnt); int nct = unique(b,b+cnt)-b; build(1,nct,1); for(int i = 1; i <= n; i++) { int tmp = lower_bound(b,b+nct,a[i])-b+1; insertit(tmp,i,1,nct,1); } for(int i = 0; i < m; i++) { if(que[i].flag == 'Q') printf("%d\n",b[query(que[i].l,que[i].r,que[i].k,1,nct,1)-1]); else { int pos1 = lower_bound(b,b+nct,a[que[i].l])-b+1,pos2 = lower_bound(b,b+nct,que[i].k)-b+1; removeit(pos1,que[i].l,1,nct,1); insertit(pos2,que[i].l,1,nct,1); a[que[i].l] = que[i].k; } } } return 0; }

按区间建树(1.9s)

#pragma comment(linker, "/STACK:102400000,102400000")
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    using namespace std; #define ll long long #define ull unsigned long long #define eps 1e-8 #define NMAX 201000 #define MOD 1000000 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define PI acos(-1) template
                   
                     inline void scan_d(T &ret) { char c; int flag = 0; ret=0; while(((c=getchar())

ZOJ 2112 Dynamic Rankings（线段树树套平衡树）(一)