Fhq,但炸了
查看原帖
Fhq,但炸了
302750
Main_WF楼主2022/7/21 20:23

freopen读入错误数据是没有任何输出,貌似主函数里那个for循环炸了,i没有到达rd就退出循环了

#include<bits/stdc++.h>
#define INF 80005
using namespace std;
const int maxn=16e4+1;
int tot,root,p[maxn],b[maxn],l=INF,rd;
struct Fhq
{
	int v[maxn],r[maxn],s[maxn],ch[maxn][2];
	
	int New(int x)
	{
		v[++tot]=x;
		r[tot]=rand();
		s[tot]=1;
		return tot;
	}
	
	void up(int x)
	{
		s[x]=s[ch[x][0]]+s[ch[x][1]]+1; 
	}
	
	void spilt(int now,int k,int &x,int&y)
	{
		if(!now)x=y=0;
		else
		{
			if(v[now]<=k)x=now,spilt(ch[now][1],k,ch[now][1],y);
			else y=now,spilt(ch[now][0],k,x,ch[now][0]);
			up(now);
		}
	}
	
	int merge(int x,int y)
	{
		if(!x||!y)return x+y;
		if(r[x]<r[y])
		{
			ch[x][1]=merge(ch[x][1],y);
			up(x);
			return x;
		}
		else
		{
			ch[y][0]=merge(x,ch[y][0]);
			up(y);
			return y;
		}
	}
	
	void insert(int x) 
	{
		int a,c;
		spilt(root,x,a,c);
		root=merge(merge(a,New(x)),c);
	}
	
	void remove(int x)
	{
		int a,z,c;
		spilt(root,x-1,a,z);
		spilt(z,x,z,c);
		root=merge(a,c);
	}
	
	void top(int x)
	{
		remove(p[x]);
		insert(--l);
		p[x]=l;
		b[l]=x;
	}
	
	void bottom(int x)
	{
		remove(p[x]);
		insert(++rd);
		p[x]=rd;
		b[rd]=x;
	}
	
	void Insert(int x,int t)
	{
		if(t==-1&&p[x]!=l)
		{
			int a,c;
			spilt(root,p[x]-1,a,c);
			int now=a;
			while(ch[now][1])
				now=ch[now][1];
			root=merge(a,c);
			int a1=x;int a2=b[v[now]];int b1=p[x];int b2=v[now];
			p[a1]=b2;p[a2]=b1;b[b1]=a2;b[b2]=a2; 
		}else if(t==1&&p[x]!=rd)
		{
			int a,c;
			spilt(root,p[x],a,c);
			int now=c;
			while(ch[now][0])
				now=ch[now][0];
			root=merge(a,c);
			int a1=x;int a2=b[v[now]];int b1=p[x];int b2=v[now];
			p[a1]=b2;p[a2]=b1;b[b1]=a2;b[b2]=a2;
		}
	}
	
	void ask(int x)
	{
		x=p[x];
		int now=root;
		int cnt=0;
		while(v[now]!=x)
		{
			int d=x>v[now];
			if(d)
				cnt+=s[ch[now][0]]+1,now=ch[now][1];
			else
				now=ch[now][0];
		}
		cnt+=s[ch[now][0]];
		cout<<cnt<<'\n';
	}
	
	void query(int k)
	{
		int now=root;
		while(1)
		{
			if(k<=s[ch[now][0]])
				now=ch[now][0];
			else if(k==s[ch[now][0]]+1)
				break;
			else
				k-=s[ch[now][0]]+1,now=ch[now][1]; 
		}
		cout<<b[v[now]]<<'\n';
	}
}fhq;
int main()
{
	freopen("2596.in","r",stdin);
	int n,m,ttt;
	cin>>n>>m;
	rd=n+INF-1;
	int i,a;
	for(i=l;i<=rd;i++)
	{
		cin>>a;
		fhq.insert(i);
		p[a]=i;
		b[i]=a;
	}
	while(m--)
	{
		string str;
		int num;
		cin>>str>>num;
		if(str=="Top")
			fhq.top(num);
		if(str=="Bottom")
			fhq.bottom(num);
		if(str=="Insert")
		{
			int tt;
			cin>>tt;
			fhq.Insert(num,tt);
		}
		if(str=="Ask")
			fhq.ask(num);
		if(str=="Query")
			fhq.query(num);
	}
}
2022/7/21 20:23
加载中...