满江红,玄 1关,马蜂良好
查看原帖
满江红,玄 1关,马蜂良好
764773
AstaVenti_楼主2025/1/14 10:46
#include<bits/stdc++.h>
using namespace std;
const int mod=998344353;
struct node{
	int vl,ky,lc,rc,sz;
}t[100005];
int n,rt,x,y,z,k,tt;
string s;
struct fhq_treap{
	void upd(int nw){
		if(nw!=0)t[nw].sz=t[t[nw].lc].sz+t[t[nw].rc].sz+1;
	}
	int NEW(int w){
		t[++tt].vl=w,t[tt].ky=1ll*rand()*rand()%mod;
		t[tt].lc=t[tt].rc=0,t[tt].sz=1;
		return tt;
	}
	void spt(int nw,int&a,int&b,int k){
		if(nw==0){
			a=b=0;
			return;
		}
		if(t[nw].vl<=k){
			a=nw;
			spt(t[nw].rc,t[a].rc,b,k);
		}else{
			b=nw;
			spt(t[nw].lc,a,t[b].lc,k);
		}
		upd(nw);
	}
	void mrg(int&nw,int a,int b){
		if(a==0||b==0){
			nw=a+b;
			return;
		}
		if(t[a].ky>t[b].ky){
			nw=a;
			mrg(t[nw].rc,t[a].rc,b);
		}else{
			nw=b;
			mrg(t[nw].lc,a,t[b].lc);
		} 
		upd(nw);
	} 
	int gtrk(int k){
		int nw=rt;
		while(1){
			if(k<=t[t[nw].lc].sz)nw=t[nw].lc;
			else if(k>t[t[nw].lc].sz+1)k-=t[t[nw].lc].sz+1,nw=t[nw].rc;
			else return t[nw].vl;
		}
	}
}FHQ1,FHQ2;
map<pair<int,int>,bool>mp;
bool isdel[100005];
int qz1[100005],qz2[100005],qz[100005];
int cnt=0,tmpans=0;
int main(){
	memset(isdel,0,sizeof(isdel));
	cin>>n;
	for(int i=0,a,b,c,k;i<n;i++){
		cin>>s;
		if(s[0]=='A'){
			cin>>a>>b>>c;
			if(a>0){
				int w=floor(((c*1.0)-b)/a)+1;
				int nw=FHQ1.NEW(w);
				FHQ1.spt(rt,x,y,w);
				FHQ1.mrg(x,x,nw);
				FHQ1.mrg(rt,x,y);
				cnt++;
				qz[cnt]=qz1[cnt]=w;
			}else if(a==0){
				tmpans+=(b>c);
				qz[cnt]=-1;
			}else{
				int w=ceil(((c*1.0)-b)/a)-1;
				int nw=FHQ2.NEW(w);
				FHQ2.spt(rt,x,y,w);
				FHQ2.mrg(x,x,nw);
				FHQ2.mrg(rt,x,y);
				cnt++;
				qz[cnt]=qz2[cnt]=w;					
			}
		}
		if(s[0]=='D'){
			cin>>k;
			if(isdel[k]){
				continue;
			}
			if(qz[cnt]==-1){
				tmpans--;
				continue;
			}
			if(qz1[k]!=0){
				int w=floor(((c*1.0)-b)/a)+1;
				FHQ1.spt(rt,x,y,w);
				FHQ1.spt(x,x,z,w-1);
				FHQ1.mrg(z,t[z].lc,t[z].rc);
				FHQ1.mrg(rt,x,z);
				FHQ1.mrg(rt,rt,y);
			}else if(qz2[k]!=0){
				int w=ceil(((c*1.0)-b)/a)-1;
				FHQ2.spt(rt,x,y,w);
				FHQ2.spt(x,x,z,w-1);
				FHQ2.mrg(z,t[z].lc,t[z].rc);
				FHQ2.mrg(rt,x,z);
				FHQ2.mrg(rt,rt,y);
			} 
			isdel[k]=1;
		}
		if(s[0]=='Q'){
			cin>>k;
			FHQ1.spt(rt,x,y,k);
			int ans=t[x].sz;
			FHQ1.mrg(rt,x,y);
//			cout<<"---\n"<<ans<<"\n";
			FHQ2.spt(rt,x,y,k-1);
			ans+=t[y].sz;
			FHQ2.mrg(rt,x,y);
//			cout<<ans<<"\n";
			cout<<ans+tmpans<<endl;
//			cout<<"---\n";
		}
	}
}
2025/1/14 10:46
加载中...