　　　　　　　　NOIP基本模板进阶

一.Treap

支持：

插入

删除

查询

查询排名为

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define INF 0x7fffffff#define N 100010int n,tot,root;struct Treap{ int l,r,val,len,cnt,siz;}a[N];int New(int x){ a[++tot].val=x; a[tot].len=rand(); a[tot].cnt=a[tot].siz=1; return tot;}void Update(int p){ a[p].siz=a[a[p].l].siz+a[a[p].r].siz+a[p].cnt;}void Build(){ New(-INF); New(INF); root=1; a[1].r=2; Update(root);}int GetRankByVal(int p,int k){ if(p==0) return 0; if(k==a[p].val) return a[a[p].l].siz+1; else if(k
            
             =rank) return GetValByRank(a[p].l,rank); else if(a[a[p].l].siz+a[p].cnt>=rank) return a[p].val; else return GetValByRank(a[p].r,rank-a[a[p].l].siz-a[p].cnt);}void zig(int &p){ int q=a[p].l; a[p].l=a[q].r; a[q].r=p; p=q; Update(a[p].r); Update(p);}void zag(int &p){ int q=a[p].r; a[p].r=a[q].l; a[q].l=p; p=q; Update(a[p].l); Update(p);}void Insert(int &p,int k){ if(p==0) { p=New(k); return; } if(k==a[p].val) { a[p].cnt++; Update(p); return; } if(k
             
              1) { a[p].cnt--; Update(p); return; } if(a[p].l||a[p].r) { if(a[p].r==0||a[a[p].l].len>a[a[p].r].len) { zig(p); Remove(a[p].r,k); } else { zag(p); Remove(a[p].l,k); } Update(p); } else p=0; return; } if(k
              
               0) { p=a[p].l; while(a[p].r>0) p=a[p].r; ans=p; } break; } if(a[p].val
               
                a[ans].val) ans=p; if(k
                
                 0) { p=a[p].r; while(a[p].l>0) p=a[p].l; ans=p; } break; } if(a[p].val>k&&a[p].val

二.非旋转Treap

支持普通Treap操作，区间翻转

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 100010int n,tot,root,m;bool flag[N];struct Treap{ int val,len,siz,ch[2]; void clear() { ch[0]=ch[1]=siz=val=len=0; }}t[N];void update(int p){ t[p].siz=t[t[p].ch[0]].siz+t[t[p].ch[1]].siz+1;}void pushdown(int p){ if(!flag[p]) return; swap(t[p].ch[0],t[p].ch[1]); if(t[p].ch[0]!=0) flag[t[p].ch[0]]^=1; if(t[p].ch[1]!=0) flag[t[p].ch[1]]^=1; flag[p]=0;}int merge(int x,int y){ if(!x||!y) return x+y; pushdown(x); pushdown(y); if(t[x].len

三.权值线段树

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 200010int m,n,idx,a[N],b[N],cnt[N<<2],u[N],idxx=1;void pushup(int p){    cnt[p]=cnt[p<<1]+cnt[p<<1|1];}void update(int l,int r,int k,int v){    if(l==r)    {        cnt[k]++;        return;    }    int mid=(l+r)>>1;    if(v<=mid)        update(l,mid,k<<1,v);    if(v>mid)        update(mid+1,r,k<<1|1,v);    pushup(k);}int query(int l,int r,int k,int rank){    if(l==r)        return l;    int mid=(l+r)>>1;    if(rank<=cnt[k<<1])        return query(l,mid,k<<1,rank);    else        return query(mid+1,r,k<<1|1,rank-cnt[k<<1]);}int main(){    scanf("%d%d",&m,&n);    for(int i=1;i<=m;i++)    {        scanf("%d",&a[i]);        b[i]=a[i];    }    for(int i=1;i<=n;i++)        scanf("%d",&u[i]);    sort(b+1,b+m+1);    int tot=unique(b+1,b+m+1)-b-1;    for(int i=1;i<=m;i++)    {        int x=lower_bound(b+1,b+tot+1,a[i])-b;        update(1,tot,1,x);        while(i==u[idxx])        {            printf("%d\n",b[query(1,tot,1,++idx)]);            ++idxx;        }    }    return 0;}