1 条题解

  • 0
    @ 2023-7-6 15:48:08
    #include <bits/stdc++.h>
    const int N = 100005;
    int rt,tot,fa[N],ch[N][2],val[N],cnt[N],sz[N];
    struct Splay {
    	void maintain(int x){
    		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
    	}
    	bool get(int x){
    		return x==ch[fa[x]][1];
    	}
    	void clear(int x){
    		ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
    	}
    	void rotate(int x){
    		int y=fa[x],z=fa[y],chk=get(x);
    		ch[y][chk]=ch[x][chk^1];
    		if(ch[x][chk^1])fa[ch[x][chk^1]]=y;
    		ch[x][chk^1]=y;
    		fa[y]=x;
    		fa[x]=z;
    		if(z)ch[z][y==ch[z][1]]=x;
    		maintain(y);
    		maintain(x);
    	}
    	void splay(int x){
    		for (int f=fa[x];f=fa[x],f;rotate(x)){
    			if(fa[f])rotate(get(x)==get(f)?f:x);
    		}
    		rt=x;
    	}
    	void ins(int k){
    		if(!rt){
    			val[++tot]=k;
    			cnt[tot]++;
    			rt=tot;
    			maintain(rt);
    			return;
    		}
    		int cur=rt,f=0;
    		while(1){
    			if(val[cur]==k){
    				cnt[cur]++;
    				maintain(cur);
    				maintain(f);
    				splay(cur);
    				break;
    			}
    			f=cur;
    			cur=ch[cur][val[cur]<k];
    			if(!cur){
    				val[++tot]=k;
    				cnt[tot]++;
    				fa[tot]=f;
    				ch[f][val[f]<k]=tot;
    				maintain(tot);
    				maintain(f);
    				splay(tot);
    				break;
    			}
    		}
    	}
    	int rk(int k){
    		int res=0,cur=rt;
    		while(1){
    			if(k<val[cur]){
    				cur = ch[cur][0];
    			}
    			else{
    				res+=sz[ch[cur][0]];
    				if(k==val[cur]){
    					splay(cur);
    					return res + 1;
    				}
    				res+=cnt[cur];
    				cur=ch[cur][1];
    			}
    		}
    	}
    	int kth(int k){
    		int cur=rt;
    		while(1){
    			if(ch[cur][0]&&k<=sz[ch[cur][0]]){
    				cur=ch[cur][0];
    			}
    			else{
    				k-=cnt[cur]+sz[ch[cur][0]];
    				if(k<=0){
    					splay(cur);
    					return val[cur];
    				}
    				cur = ch[cur][1];
    			}
    		}
    	}
    	int pre(){
    		int cur=ch[rt][0];
    		if(!cur)return cur;
    		while(ch[cur][1])cur=ch[cur][1];
    		splay(cur);
    		return cur;
    	}
    	int nxt(){
    		int cur=ch[rt][1];
    		if(!cur)return cur;
    		while(ch[cur][0])cur=ch[cur][0];
    		splay(cur);
    		return cur;
    	}
    	void del(int k){
    		rk(k);
    		if(cnt[rt]>1){
    			cnt[rt]--;
    			maintain(rt);
    			return;
    		}
    		if(!ch[rt][0]&&!ch[rt][1]){
    			clear(rt);
    			rt=0;
    			return;
    		}
    		if(!ch[rt][0]){
    			int cur=rt;
    			rt=ch[rt][1];
    			fa[rt]=0;
    			clear(cur);
    			return;
    		}
    		if(!ch[rt][1]){
    			int cur=rt;
    			rt=ch[rt][0];
    			fa[rt]=0;
    			clear(cur);
    			return;
    		}
    		int cur=rt;
    		int x=pre();
    		fa[ch[cur][1]]=x;
    		ch[x][1]=ch[cur][1];
    		clear(cur);
    		maintain(rt);
    	}
    }tree;
    int main() {
    	int n;
    	std::cin>>n;
    	int a,b,c;
    	a=n/100;
    	b=n%100/10;
    	c=n%10;
    	tree.ins(a);
    	tree.ins(b);
    	tree.ins(c);
    	std::cout<<tree.kth(3)-tree.kth(1);
    	return 0;
    }
    

    信息

    ID
    664
    时间
    1000ms
    内存
    16MiB
    难度
    10
    标签
    递交数
    7
    已通过
    4
    上传者