fhq-Treap 56pts 求助
查看原帖
fhq-Treap 56pts 求助
356003
Moeebius楼主2022/5/4 20:16

RT,#5~#10出现奇异MLE,TLE和WA,求调

/*
* @ Author: Xiaohuba
* @ Usage: OI Problem
* @ Language: C++
*/
#include<bits/stdc++.h>
using namespace std;

/* ---File Head Begin--- */
namespace Xiaohuba_File_Head
{
	//def
	#define ll long long
	#define lll __int128
	#define pii pair<int,int>
	#define mkp make_pair
	#define vi vector<int>
	#define vs vector<string>
	#define viit vector<int>::iterator
	#define pb push_back
	#define il inline 
	#define pch putchar
	#define gch getchar
	#define Endl putchar('\n')
	#define Space putchar(' ')
	#define For(x,st,ed) for(register int x=(st),END=(ed);x<=END;++x)
	#define ForDown(x,st,ed) for(register int x=(st),END=(ed);x>=END;--x)
	#define sq(x) (x*x)
	#define Set(a,b) memset(a,b,sizeof(a))
	#define Cpy(a,b) memcpy(a,b,sizeof(a))
	#define PRIME_MOD 100000007ll
	#ifdef ONLINE_JUDGE
		#define log2 __lg
		#define gcd __gcd
	#endif
	//io
	template <typename T>
	il void read(T & tmp){ tmp=0;char c=getchar();bool flg=0;while(!isdigit(c)) flg=c=='-',c=getchar();while(isdigit(c)) tmp=(tmp<<3)+(tmp<<1)+c-'0',c=getchar();if(flg) tmp*=-1; }
	template <typename T, typename... Args>
	il void read(T &tmp, Args &...tmps){ read(tmp);read(tmps...); }
	template <typename T>
	il void __write(const T &x){ if(x==0) return;__write(x/10);putchar(x%10+'0'); }
	template <typename T>
	il void write(const T &x){ if(x==0) putchar('0');if(x<0) putchar('-');__write((x<0 ? -x : x)); }
	template <typename T>
	il void write_with_space(const T &x){ write(x);Space; }
	template <typename T>
	il void write_with_endl(const T &x){ write(x);Endl; }
	template <typename T, typename... Args>
	il void write_with_space(const T &x, const Args &...y){ write_with_space(x);write_with_space(y...); }
	il void __getline(istream & istr, string & str){ getline(istr,str);if(*(str.end()-1)=='\r') str.erase(str.end()-1); } 
	#define getline __getline
};
using namespace Xiaohuba_File_Head;
/* ---File Head End--- */

class FHQ_Treap
{
	public:
	struct Node
	{
		int lc,rc,v,w,size;
	};
	Node tr[10001];int cnt,root;
	il int New(int x)
	{
		tr[++cnt]=(Node){0,0,x,rand(),1};
		return cnt;
	}
	il void pushUp(int id)
	{
		tr[id].size=tr[tr[id].lc].size+tr[tr[id].rc].size+1;
	}
	il void split(int v, int &x, int &y, int id)
	{
		if(!id)
		{
			x=y=0;
			return;
		}
		if(tr[id].v<=v)
		{
			x=id;
			split(v,tr[id].rc,y,tr[id].rc);
		} else {
			y=id;
			split(v,x,tr[id].lc,tr[id].lc);
		}
		pushUp(id);
	}
	il int merge(int x, int y)
	{
		if(!x || !y) return x+y;
		if(tr[x].w > tr[y].w)
		{
			tr[x].rc=merge(tr[x].rc,y);
			pushUp(x);
			return x;
		} else {
			tr[y].lc=merge(x,tr[y].lc);
			pushUp(y);
			return y;
		}
	}
	il void insert(int v)
	{
		int x,y;
		split(v,x,y,root);
		root=merge(merge(x,New(v)),y);
	}
	il void erase(int v)
	{
		int x,y,z;
		split(v,x,y,root);
		split(v-1,x,z,x);
		z=merge(tr[z].lc,tr[z].rc);
		root=merge(merge(x,z),y);
	}
	il int rank(int v)
	{
		int x,y;
		split(v-1,x,y,root);
		int res=tr[x].size+1;
		root=merge(x,y);
		return res;
	}
	il int kth(int k)
	{
		int u=root;
		while(u)
		{
			if(tr[tr[u].lc].size+1==k) break;
			if(tr[tr[u].lc].size+1>k) u=tr[u].lc;
			else
			{
				k-=tr[tr[u].lc].size+1;
				u=tr[u].rc;
			}
		}
		return tr[u].v;
	}
	il int pre(int v)
	{
		int x,y;
		split(v-1,x,y,root);
		int u=x;
		while(tr[u].rc) u=tr[u].rc;
		root=merge(x,y);
		return tr[u].v;
	}
	il int nxt(int v)
	{
		int x,y;
		split(v,x,y,root);
		int u=y;
		while(tr[u].lc) u=tr[u].lc;
		root=merge(x,y);
		return tr[u].v;
	}
};
FHQ_Treap bt;
int T;
signed main()
{
	srand(666);
	read(T);
	while(T--)
	{
		int op,x;
		read(op,x);
		switch(op)
		{
			case 1:
			bt.insert(x);
			break;
			case 2:
			bt.erase(x);
			break;
			case 3:
			write_with_endl(bt.rank(x));
			break;
			case 4:
			write_with_endl(bt.kth(x));
			break;
			case 5:
			write_with_endl(bt.pre(x));
			break;
			case 6:
			write_with_endl(bt.nxt(x));
		}
	}
	return 0;
}
2022/5/4 20:16
加载中...