蒟蒻60分WA求助
查看原帖
蒟蒻60分WA求助
118000
returnG楼主2020/8/24 21:45

#5#6#7#8WA了,目前没有找到bug

用的treap,代码如下(码风见谅):

#include <bits/stdc++.h>
using namespace std;
int n,root=0,tot=0;
struct node{
	int key,val,cnt,siz,l,r;
}tr[1000005];
void update(int u){
	tr[u].siz=tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].cnt;
}
int newnode(int x){
	tr[++tot].cnt=1;
	tr[tot].key=x;
	tr[tot].val=rand();
	tr[tot].siz=1;
	tr[tot].l=tr[tot].r=0;
	return tot;
}
void lt(int &u){
	int p=tr[u].r;
	tr[u].r=tr[p].l;
	tr[p].l=u;
	tr[p].siz=tr[u].siz;
	update(u);
	u=p;
}
void rt(int &u){
	int p=tr[u].l;
	tr[u].l=tr[p].r;
	tr[p].r=u;
	tr[p].siz=tr[u].siz;
	update(u);
	u=p;
}
void insert(int &u,int x){
	if(!u){
		u=newnode(x);
		return ;
	}else{
		tr[u].siz++;
	}
	if(tr[u].key==x){
		tr[u].cnt++;
		return ;
	}
	if(tr[u].key<x){
		insert(tr[u].r,x);
		if(tr[u].val>tr[tr[u].r].val)lt(u);
	}else{
		insert(tr[u].l,x);
		if(tr[u].val>tr[tr[u].l].val)rt(u);
	}
}
void del(int &u,int x){
	if(tr[u].key==x){
		if(tr[u].cnt>1){
			tr[u].cnt--;
			return ;
		}
		if(!tr[u].l||!tr[u].r){
			u=tr[u].l+tr[u].r;
			return ;
		}
		if(tr[tr[u].l].val<tr[tr[u].r].val){
			lt(u);
			del(u,x);
		}else{
			rt(u);
			del(u,x);
		}
		return ;
	}
	tr[u].siz--;
	if(tr[u].key<x){
		del(tr[u].r,x);
	}else{
		del(tr[u].l,x);
	}
	return ;
}
int torank(const int x){
	int u=root,res=0;
	while(u){
//		cout<<"!"<<u<<"!"<<tr[u].l<<"!"<<tr[u].r<<"!"<<tr[u].key<<endl;
		if(tr[u].key==x)return res+tr[tr[u].l].siz+1;
		if(x<tr[u].key)u=tr[u].l;
		else res+=tr[tr[u].l].siz+tr[u].cnt,u=tr[u].r;
	}
}
int tonum(int x){
	int u=root;
	while(u){
		if(tr[tr[u].l].siz<x&&x<=tr[tr[u].l].siz+tr[u].cnt)return tr[u].key;
		if(x<=tr[tr[u].l].siz)u=tr[u].l;
		else x-=tr[u].cnt+tr[tr[u].l].siz,u=tr[u].r;
	}
	return 0;
}
int topre(int x){
	int u=root,res=0;
	while(u){
		if(tr[u].key<x)res=tr[u].key,u=tr[u].r;
		else u=tr[u].l;
	}
	return res;
}
int tonxt(int x){
	int u=root,res=0;
	while(u){
		if(tr[u].key>x)res=tr[u].key,u=tr[u].l;
		else u=tr[u].r;
	}
	return res;
}
void pmid(int u){
	if(!u)return ;
	pmid(tr[u].l);
	cout<<tr[u].key<<' ';
	pmid(tr[u].r);
}
int main() {
	scanf("%d",&n);
	while(n--){
		int x,y;
		scanf("%d%d",&x,&y);
		switch(x){
			case 1:{
				insert(root,y);
				break;
			}
			case 2:{
				del(root,y);
				break;
			}
			case 3:{
				printf("%d\n",torank(y));
				break;
			}
			case 4:{
				printf("%d\n",tonum(y));
				break;
			}
			case 5:{
				printf("%d\n",topre(y));
				break;
			}
			case 6:{
				printf("%d\n",tonxt(y));
				break;
			}
		}
		/*
		pmid(root);
		cout<<endl;
		cout<<endl;
		*/
	}
	return 0;
}
2020/8/24 21:45
加载中...