救救孩子,为啥就爆0了,用的是树状数组
查看原帖
救救孩子,为啥就爆0了,用的是树状数组
236296
_spy楼主2021/10/4 00:05
#include<bits/stdc++.h>
const int maxn=1e6+10;
using namespace std;

int n;
int cnt;
int kind[maxn],tmp[maxn],tot;
int z[2*maxn],f[2*maxn];

void modify(int x,int y,int t[]){
	x += maxn;
	 
	for(int i=x;i<=2e6+10; i += i & (-i)){
		t[i] += y;
	}
	return;
}

int ask(int x,int t[]){
	x+=maxn;
	int ans=0;
	for(int i=x;i;i -= (-i) & i){
		ans += t[i];
	}
	return ans;
}

bool used[maxn];
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		char s[20];
		cin>>s;
		if(s[0] == 'A'){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(a == 0){
				if(b>c) cnt++,kind[++tot] = 1;
				else kind[++tot] = 0; 
			}
			
			if(a>0){//x>....形式 
				tmp[++tot] = floor((c*1.0-b)/a);
				//cout<<tmp[tot]<<"tmp \n";
				kind[tot] = 2 ;
				if(tmp[tot] > 1e6) kind[ tot ] = 0;
				else if(tmp[tot] < -1e6) kind[tot] = 1 , cnt++; 
				else modify(tmp[tot],1,z);
			}
			else {
				tmp[++tot]=ceil((c*1.0-b)/a);
				 
				//cout<<tmp[tot]<<"tmp \n";
				kind[tot] = 3;
				if(tmp[tot] > 1e6)  kind [ tot ] = 1,cnt++;
				else if(tmp[ tot ] < -1e6) kind [ tot ]=0;
				else modify(tmp[tot],1,f);
			}
		}
		if(s[0] == 'D'){
			int x;
			scanf("%d",&x);
			if(used[x]) continue;
			used[x]=1;
	
			if(kind[x] == 1) cnt--;
			if(kind[x] == 2) modify(tmp[x],-1,z);
			if(kind[x] == 3) modify(tmp[x],-1,f);
		}
		if(s[0] == 'Q'){
			int k;
			scanf("%d",&k);
			//cout<<ask(k,z)<<"  "<<k<<endl;
			printf("%d\n",ask(k-1,z)+(ask(1e6+10,f)-ask(k,f))+cnt);
		}
	}
	
	return 0;
}
2021/10/4 00:05
加载中...