求助P5482,40PT
  • 板块灌水区
  • 楼主Grimgod
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/3/2 16:51
  • 上次更新2023/10/23 23:21:06
查看原帖
求助P5482,40PT
495512
Grimgod楼主2023/3/2 16:51

不要问我为什么发灌水,因为学术版和题目总版几乎没有人看

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0,x=0;char ch;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
} 
int n;
string str;
int g,h,ph;
int root1,tot1,root2,tot2;
struct fhq_treap{
	int l,r;
	int dat,size,val;
}t1[500005],t2[500005];
int x,y,z;
int New1(int k){
	t1[++tot1].val=k;
	t1[tot1].dat=rand();
	t1[tot1].size=1;
	return tot1;
}
void pushup1(int p){
	t1[p].size=t1[t1[p].l].size+t1[t1[p].r].size+1; 
}
void split1(int p,int k,int &x,int &y){
	if(!p){
		x=y=0;
		return ;
	}
	if(t1[p].val<=k){
		x=p;
		split1(t1[p].r,k,t1[p].r,y);
	}
	else{
		y=p;
		split1(t1[p].l,k,x,t1[p].l);
	}
	pushup1(p);
}
int merge1(int x,int y){
	if(!x||!y) return x+y;
	if(t1[x].dat<t1[y].dat){
		t1[x].r=merge1(t1[x].r,y);
		pushup1(x);
		return x;
	}
	else{
		t1[y].l=merge1(x,t1[y].l);
		pushup1(y);
		return y;
	}
}
void insert1(int k){
	split1(root1,k,x,y);
	root1=merge1(merge1(x,New1(k)),y);
}
void del1(int k){
	split1(root1,k,x,z);
	split1(x,k-1,x,y);
	y=merge1(t1[y].l,t1[y].r);
	root1=merge1(merge1(x,y),z);
}
int getrank1(int k){
	split1(root1,k-1,x,y);
	int ans=t1[x].size+1;
	root1=merge1(x,y);
	return ans; 
}
int New2(int k){
	t2[++tot2].val=k;
	t2[tot2].dat=rand();
	t2[tot2].size=1;
	return tot2;
}
void pushup2(int p){
	t2[p].size=t2[t2[p].l].size+t2[t2[p].r].size+1; 
}
void split2(int p,int k,int &x,int &y){
	if(!p){
		x=y=0;
		return ;
	}
	if(t2[p].val<=k){
		x=p;
		split2(t2[p].r,k,t2[p].r,y);
	}
	else{
		y=p;
		split2(t2[p].l,k,x,t2[p].l);
	}
	pushup2(p);
}
int merge2(int x,int y){
	if(!x||!y) return x+y;
	if(t2[x].dat<t2[y].dat){
		t2[x].r=merge2(t2[x].r,y);
		pushup2(x);
		return x;
	}
	else{
		t2[y].l=merge2(x,t2[y].l);
		pushup2(y);
		return y;
	}
}
void insert2(int k){
	split2(root2,k,x,y);
	root2=merge2(merge2(x,New2(k)),y);
}
void del2(int k){
	split2(root2,k,x,z);
	split2(x,k-1,x,y);
	y=merge2(t2[y].l,t2[y].r);
	root2=merge2(merge2(x,y),z);
}
int getrank2(int k){
	split2(root2,k-1,x,y);
	int ans=t2[x].size+1;
	root2=merge2(x,y);
	return ans; 
}
int a[500005],b[500005],c[500005];
int flag[500005];
int cnt;
int pointer;
int getfirst(int k){
	return getrank1(k)-1;
}
int getsecond(int k){
	return t2[root2].size-getrank2(k)+1; 
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		cin>>str;
		if(str[0]=='A'){
			a[++pointer]=read(),b[pointer]=read(),c[pointer]=read();
			if(a[pointer]==0) {
				if(b[pointer]>c[pointer]) cnt++;
			}
			else {
				//k.push_back((c[i]-b[i])/a[i]);
				if(a[pointer]>0){
					int ins=floor((c[pointer]-b[pointer])/(a[pointer]*1.0))+1;
					insert1(ins);
				}
				if(a[pointer]<0){
					int ins=ceil((c[pointer]-b[pointer])/(a[pointer]*1.0))-1;
					insert2(ins);
				}
			}
		}
		if(str[0]=='D'){
			g=read();
			if(flag[g]) continue;
			flag[g]=1;
			if(a[g]==0){
				if(b[g]>c[g]) cnt--;
			}
			if(a[g]>0){
				int ins=floor((c[g]-b[g])/(a[g]*1.0))+1;
				del1(ins);
			}
			if(a[g]<0){
				int ins=ceil((c[g]-b[g])/(a[g]*1.0))-1;
				del2(ins);
			}
		}
		if(str[0]=='Q'){
			g=read();
			//cout<<getrank1(g)-1<<endl;
			//cout<<getrank2(g)-1<<endl;
			//cout<<cnt<<endl;
			cout<<getfirst(g)+getsecond(g)+cnt<<endl; 
			//cout<<getrank2(0x3f3f3f3f)-getrank2(g+1)+1<<endl;
		}
	}
	return 0;
}
2023/3/2 16:51
加载中...