FHQ-Treap样例已过0pts求调
查看原帖
FHQ-Treap样例已过0pts求调
735763
_ChongYun_楼主2025/1/15 10:26

WA 0pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,ans=0;
int rt1,rt2,l1=0,r1=0,l2=0,r2=0,px1,px2,cnt1=0,cnt2=0;
struct node{
	int a,b,c;
}qry[4000005];
int tot=0;
struct FHQ_Treap{
	int l,r,siz,val,randval;
}Treap1[10000005],Treap2[10000005];
void pushup1(int p){
	Treap1[p].siz=Treap1[Treap1[p].l].siz+Treap1[Treap1[p].r].siz+1;
	return ;
}
void build1(int x){
	++cnt1;
	Treap1[cnt1].l=Treap1[cnt1].r=0;
	Treap1[cnt1].siz=1;
	Treap1[cnt1].val=x;
	Treap1[cnt1].randval=rand();
	return ;
}
void Split1(int p,int val,int &l,int &r){
	if(!p){
		l=r=0;
		return ;
	}
	if(Treap1[p].val<=val){ 
		l=p; 
		Split1(Treap1[p].r,val,Treap1[p].r,r); 
	}else{
		r=p; 
		Split1(Treap1[p].l,val,l,Treap1[p].l); 
	}
	pushup1(p);
	return ;
}

int Merge1(int l,int r){
	if(!l||!r) return l+r;
	if(Treap1[l].randval<=Treap1[r].randval){
		Treap1[l].r=Merge1(Treap1[l].r,r);
		pushup1(l);
		return l;
	}
	Treap1[r].l=Merge1(l,Treap1[r].l);
	pushup1(r);
	return r;
}

void Insert1(int x){
	Split1(rt1,x,l1,r1);
	build1(x);
	rt1=Merge1(Merge1(l1,cnt1),r1);
	return ;
}

void Delete1(int x){
	Split1(rt1,x,l1,r1);
	Split1(l1,x-1,l1,px1);
	px1=Merge1(Treap1[px1].l,Treap1[px1].r);
	rt1=Merge1(Merge1(l1,px1),r1);
	return ;
}
void pushup2(int p){
	Treap2[p].siz=Treap2[Treap2[p].l].siz+Treap2[Treap2[p].r].siz+1;
	return ;
}

void build2(int x){
	++cnt2;
	Treap2[cnt2].l=Treap2[cnt2].r=0;
	Treap2[cnt2].siz=1;
	Treap2[cnt2].val=x;
	Treap2[cnt2].randval=rand();
	return ;
}
void Split2(int p,int val,int &l,int &r){
	if(!p){
		l=r=0;
		return ;
	}
	if(Treap2[p].val<=val){ 
		l=p; 
		Split2(Treap2[p].r,val,Treap2[p].r,r); 
	}else{
		r=p; 
		Split2(Treap2[p].l,val,l,Treap2[p].l); 
	}
	pushup2(p);
	return ;
}

int Merge2(int l,int r){
	if(!l||!r) return l+r;
	if(Treap2[l].randval<=Treap2[r].randval){
		Treap2[l].r=Merge2(Treap2[l].r,r);
		pushup2(l);
		return l;
	}
	Treap2[r].l=Merge2(l,Treap2[r].l);
	pushup2(r);
	return r;
}

void Insert2(int x){
	Split2(rt2,x,l2,r2);
	build2(x);
	rt2=Merge2(Merge2(l2,cnt2),r2);
	return ;
}

void Delete2(int x){
	Split2(rt2,x,l2,r2);
	Split2(l2,x-1,l2,px2);
	px2=Merge2(Treap2[px2].l,Treap2[px2].r);
	rt2=Merge2(Merge2(l2,px2),r2);
	return ;
}
int rk1(int p,int k){
	if(!p) return 0;
	if(k==Treap1[Treap1[p].l].siz+1) return p;
	if(k<Treap1[Treap1[p].l].siz+1) return rk1(Treap1[p].l,k);
	k-=Treap1[Treap1[p].l].siz+1;
	return rk1(Treap1[p].r,k);
}

int rk2(int p,int k){
	if(!p) return 0;
	if(k==Treap2[Treap2[p].l].siz+1) return p;
	if(k<Treap2[Treap2[p].l].siz+1) return rk2(Treap2[p].l,k);
	k-=Treap2[Treap2[p].l].siz+1;
	return rk2(Treap2[p].r,k);
}
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
signed main(){
	q=read();
	while(q--){
		string op; cin>>op;
		if(op=="Add"){
			int a,b,c;
			a=read(); b=read(); c=read();
			if(a<0) Insert2(ceil((c*1.0-b*1.0)/a*1.0)-1);
			if(a==0&&c-b<0) ans++;
			if(a>0) Insert1(floor((c*1.0-b*1.0)/a*1.0)+1);
			qry[++tot]={a,b,c};
		}
		if(op=="Del"){
			int x=read();
			int a=qry[x].a,b=qry[x].b,c=qry[x].c;
			if(a<0) Delete2(ceil((c*1.0-b*1.0)/a*1.0)-1);
			if(a==0&&c-b<0) ans--;
			if(a>0) Delete1(floor((c*1.0-b*1.0)/a*1.0)+1);
		}
		if(op=="Query"){
			int x=read();
			int now1=Treap1[rt1].siz;
			int now2=Treap2[rt2].siz;
			Insert1(x); Insert2(x);
			printf("%lld\n",rk1(rt1,x)-1+Treap2[rt2].siz-rk2(rt2,x)+ans);
			if(now1!=Treap1[rt1].siz) Delete1(x);
			if(now2!=Treap2[rt2].siz) Delete2(x);
		}
	}
	return 0;
}
2025/1/15 10:26
加载中...