全wa,树状数组
查看原帖
全wa,树状数组
365532
Mr_ll楼主2022/2/17 16:36
#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=1e6+10;
int n,a,b,f,fh[INF/10+5],zhi[INF/10+5],cnt,c[INF+INF+10];
bool bo[INF];
string opt;
void add(int x,long long y){
	x+=INF+1;
	for(;x<=2e6+10;x+=x&(-x)) c[x]+=y;
}
long long query(int x){
	long long ans=0;
	x+=INF+1;
	for(;x;x-=x&-x) ans+=c[x];
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>opt;
		if(opt[0]=='A'){
			scanf("%d%d%d",&a,&b,&f);
			if(a==0){
				if(b>f){
					fh[++cnt]=-1;
					zhi[cnt]=INF;
					add(-INF+INF,1);
					add(INF+INF+1,-1);
				}
				continue;
			}
			cnt++;
			if(a>0){
				int z=floor((double)(f-b)/(double)a)+1;
				if(z>1e6) continue;
				if(z<-1e6) z=-1e6;
				zhi[cnt]=z;fh[cnt]=1,add(z,1);add(INF+1,-1);
			}
			else{
				int z=ceil((double)(f-b)/(double)a)-1;
				if(z<-1e6) continue;
				if(z>1e6) z=1e6;
				zhi[cnt]=z;fh[cnt]=-1,add(-INF,1);add(z+1,-1);
			} 
		//	cout<<"KK"<<endl;
		}
		else if(opt[0]=='D'){
			scanf("%d",&a);
			if(bo[a]) continue;
			bo[a]=1; 
			if(fh[a]>0) add(zhi[a],-1),add(INF+1,1);
			else add(-INF,-1),add(zhi[a]+1,1);
		}
		else if(opt[0]=='Q'){
			scanf("%d",&a);
			printf("%d\n",query(a));
		}
	}
	return 0;
}
2022/2/17 16:36
加载中...