BZOJ 4923: [Lydsy1706月赛]K小值查询 Splay + 思维

#include <bits/stdc++.h>
using namespace std; 
typedef long long ll; 
const int maxn=100003; 
namespace IO {  
    void setIO(string s) {
        string in=s+".in"; 
        string out=s+".out"; 
        freopen(in.c_str(),"r",stdin);
        freopen(out.c_str(),"w",stdout); 
    } 
    char *p1,*p2,buf[100000];
    #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
    int rd() {
        int x=0; 
        char c=nc(); 
        while(c<48) c=nc(); 
        while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); 
        return x;
    }
};   
int root; 
int arr[maxn];   
struct Splay { 
    #define lson ch[x][0] 
    #define rson ch[x][1] 
    stack<int>S; 
    int cnt,tp; 
    int ch[maxn][2],f[maxn],val[maxn],siz[maxn],tag[maxn],key[maxn];      
    void init() {
        for(int i=1;i<maxn;++i) S.push(i);    
    }      
    int newnode() {
        int x=S.top();S.pop(); 
        return x;    
    }
    void mark(int x,int d) { 
        val[x]-=d, tag[x]+=d;   
    }
    int get(int x) {
        return ch[f[x]][1]==x; 
    }
    void pushup(int x) {
        siz[x]=siz[lson]+siz[rson]+1;    
    }   
    void pushdown(int x) {
        if(tag[x]) mark(lson,tag[x]),mark(rson,tag[x]),tag[x]=0;  
    }
    void rotate(int x) {
        int old=f[x],fold=f[old],which=get(x); 
        ch[old][which]=ch[x][which^1],f[ch[old][which]]=old; 
        ch[x][which^1]=old,f[old]=x,f[x]=fold; 
        if(fold) ch[fold][ch[fold][1]==old]=x; 
        pushup(old),pushup(x); 
    }
    void splay(int x,int &tar) {
        int u=f[tar],fa; 
        for(;(fa=f[x])^u;rotate(x)) 
            if(f[fa]^u) 
                rotate(get(fa)==get(x)?fa:x); 
        tar=x; 
    }
    int pre(int v) {
        int x=root,re=0; 
        while(x) { 
            pushdown(x);   
            if(val[x]<=v) re=x,x=rson;  
            else x=lson;    
        }    
        return re;   
    }         
    int nxt(int v) {
        int x=root,re=0; 
        while(x) {
            pushdown(x); 
            if(val[x]>=v) re=x,x=lson;   
            else x=rson; 
        } 
        return re;   
    } 
    void build(int &x,int ff,int l,int r) {
        x=newnode();  
        int mid=(l+r)>>1;  
        f[x]=ff,val[x]=arr[mid],siz[x]=1;   
        if(l<mid) build(lson,x,l,mid-1);  
        if(r>mid) build(rson,x,mid+1,r);     
        pushup(x);     
    }
    int insert(int &x,int ff,int k) {
        if(!x) {
            x=newnode();   
            f[x]=ff,val[x]=k,siz[x]=1; 
            pushup(x);    
            return x;     
        } 
        pushdown(x); 
        int a=insert(ch[x][k>val[x]],x,k);   
        pushup(x);  
        return a;     
    }
    void dfs(int x) {
        if(!x) return;  
        pushdown(x); 
        key[++tp]=val[x];       
        if(lson) dfs(lson); 
        if(rson) dfs(rson);  
        S.push(x);   
        ch[x][0]=ch[x][1]=f[x]=val[x]=siz[x]=tag[x]=0;                    
    }
    int kth(int k) {
        int x=root;  
        while(1) {
            pushdown(x);  
            if(k>siz[lson]) { 
                k-=(siz[lson]+1); 
                if(k==0) return val[x];   
                else x=rson;   
            }
            else x=lson;   
        }
    }
    void solve(int k) { 
        int pr=pre(k),nx=nxt(k<<1);  
        if(!pr) mark(root,k);   
        else if(!nx) {
            splay(pr,root);   
            int a=ch[root][1];  
            ch[root][1]=f[ch[root][1]]=0; 
            pushup(root);         
            tp=0; 
            dfs(a);   
            for(int i=1;i<=tp;++i) {
                int cc=insert(root,0,key[i]-k); 
                if(i%6==0) splay(cc,root);  
            }
        }
        else {    
            splay(pr,root),splay(nx,ch[root][1]);
            int a=ch[ch[root][1]][0];        
            ch[ch[root][1]][0]=0, pushup(ch[root][1]);        
            tp=0, dfs(a);    
            mark(ch[root][1], k);     
            for(int i=1;i<=tp;++i) {
                int cc=insert(root,0,key[i]-k); 
                if(i%6==0) splay(cc,root);  
            }
        }
    }
    #undef lson 
    #undef rson
}tr; 
int main() { 
    using namespace IO;  
    // setIO("input");   
    tr.init();    
    int n,m; 
    n=rd(),m=rd(); 
    for(int i=1;i<=n;++i) arr[i]=rd();  
    sort(arr+1,arr+1+n);
    tr.build(root,0,1,n);     
    for(int cas=1;cas<=m;++cas) {
        int op,k; 
        op=rd(),k=rd();  
        if(op==1) printf("%d\n",tr.kth(k));  
        else tr.solve(k);  
    } 
    return 0; 
}