P1110 （平衡树实现）

难度1

还是比较板的一道题，考的是对平衡树各功能的灵活使用。首先看要求的操作，发现操作三在每次插入时求下前驱后继即可，因为如果答案不是有这个更新的，那么这个答案必定在之前计算过，所以能保证正确性。然后看操作二，发现在每次插入时，有一个原来的差不能再对答案做出贡献，并且有两个新的差进来，考虑维护两颗平衡树分别维护操作二和操作三即可。

同时注意常数带来的问题，比如输入操作的op是个字符串时可考虑只看有区分性的字符，这样会快很多

#include<bits/stdc++.h>
using namespace std;
long long n,T,x,y,a[500005],minn2=1e16;
string op;
vector<long long>v[500005];
namespace treap{
    struct node{
        long long val,rd;//val 值/rd 优先级 
    }p[1000005];
    long long root,size[1000005],son[1000005][2],cnt=0,rx,ry,rz;
    void update(long long rt){
        size[rt]=size[son[rt][0]]+size[son[rt][1]]+1;
    }
    long long add(long long x){
        cnt++;
        size[cnt]=1;
        p[cnt].val=x;
        p[cnt].rd=rand();
        return cnt;
    }
    void split(long long rt,long long key,long long &x,long long &y){
        if(!rt){
            x=y=0;
            return;
        }
        if(p[rt].val<=key){
            x=rt;
            split(son[rt][1],key,son[rt][1],y);
        }
        else{
            y=rt;
            split(son[rt][0],key,x,son[rt][0]);
        }
        update(rt);
    }
    long long merge(long long l,long long r){
        if(!l||!r) return l+r;
        if(p[l].rd<p[r].rd){
            son[l][1]=merge(son[l][1],r);
            update(l);
            return l;
        }else{
            son[r][0]=merge(l,son[r][0]);
            update(r);
            return r;
        }
    }
    long long getrank(long long x,long long k){
        while(true){
            if(k<=size[son[x][0]]){
                x=son[x][0];
            }
            else if(k>size[son[x][0]]+1){
                k-=(size[son[x][0]]+1);
                x=son[x][1];
            }
            else{
                return x;
            }
        }
    }
    void insert(long long x){
        split(root,x,rx,ry);
        root=merge(merge(rx,add(x)),ry);
    }//插入x
    long long getpre(long long x){
        long long gg;
        split(root,x,rx,ry);
        if(!rx) return 1e16;
        gg=getrank(rx,size[rx]);
        root=merge(rx,ry);
        return p[gg].val;
    }//查询x的前驱 
    long long getnxt(long long x){
        long long gg;
        split(root,x-1,rx,ry);
        if(!ry) return 1e16;
        gg=getrank(ry,1);
        root=merge(rx,ry);
        return p[gg].val;
    }//查询x的后继 
}
namespace treap1{
    struct node{
        long long val,rd;//val 值/rd 优先级 
    }p[1000005];
    long long root,size[1000005],son[1000005][2],cnt=0,rx,ry,rz;
    void update(long long rt){
        size[rt]=size[son[rt][0]]+size[son[rt][1]]+1;
    }long long add(long long x){
        cnt++;
        size[cnt]=1;
        p[cnt].val=x;
        p[cnt].rd=rand();
        return cnt;
    }
    void split(long long rt,long long key,long long &x,long long &y){
        if(!rt){
            x=y=0;
            return;
        }if(p[rt].val<=key){
            x=rt;
            split(son[rt][1],key,son[rt][1],y);
        }else{
            y=rt;
            split(son[rt][0],key,x,son[rt][0]);
        }
        update(rt);
    }
    long long merge(long long l,long long r){
        if(!l||!r) return l+r;
        if(p[l].rd<p[r].rd){
            son[l][1]=merge(son[l][1],r);
            update(l);
            return l;
        }else{
            son[r][0]=merge(l,son[r][0]);
            update(r);
            return r;
        }
    }
    long long getrank(long long x,long long k){
        while(true){
            if(k<=size[son[x][0]]){
                x=son[x][0];
            }else if(k>size[son[x][0]]+1){
                k-=(size[son[x][0]]+1);
                x=son[x][1];
            }else{
                return x;
            }
        }
    }
    void insert(long long x){
        split(root,x,rx,ry);
        root=merge(merge(rx,add(x)),ry);
    }//插入x
    void del(long long x){
        split(root,x,rx,rz);
        split(rx,x-1,rx,ry);
        ry=merge(son[ry][0],son[ry][1]);
        root=merge(merge(rx,ry),rz);
    }//删除x
    long long getrnk(long long x){
        return p[getrank(root,x)].val;
    }
}
int main(){
	srand(time(0));
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>T;
	for(long long i=1;i<=n;i++){
		cin>>x;
		a[i]=x;
		v[i].push_back(x);
		if(i>1) treap1::insert(abs(a[i]-a[i-1]));
		minn2=min(minn2,min(abs(x-treap::getpre(x)),abs(x-treap::getnxt(x))));
		treap::insert(x);
	}
	while(T--){
		cin>>op;
		if(op[0]=='I'){
			cin>>x>>y;
			treap1::del(abs(v[x][v[x].size()-1]-v[x+1][0]));
			treap1::insert(abs(v[x][v[x].size()-1]-y));
			treap1::insert(abs(y-v[x+1][0]));
			v[x].push_back(y);
			minn2=min(minn2,min(abs(y-treap::getpre(y)),abs(y-treap::getnxt(y))));
			treap::insert(y);
		}else if(op[4]=='G'){
			cout<<treap1::getrnk(1)<<"\n";
		}else{
			cout<<minn2<<"\n";
		}
	} 
	
	return 0;
}