image.png

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int N=1000001;
int n,c1[N*2+10],c2[N*2+10],tx[N],ty[N],tot,spe,tz[N];

/*
ty[i]表示第i个Add a b c的类型（1<<30代表情况2.，-(1<<30)表示情况1.）
tx[i]表示第i个Add a b c的k值 （ty[i]==1<<30 or ty[i]==-(1<<30)的情况下你可以认为它不存在）
*/

//树状数组板子(因为树状数组不能出现0所以给每个x都加上了一个N)
int lowbit(int x)
{
	return x&(x^(x-1));
}

void add(int x,int k,int c[])
{
	x+=N;
	while(x<=2000001)
	{
		c[x]+=k;
		x+=lowbit(x);
	}
}

int getsum(int x,int c[])
{
	x+=N;
	int ans=0;
	while(x)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

void work()
{
	scanf("%d",&n);
	char s[10];
	int x,y,z;
	while(n--)
	{
		scanf("%s",s);
		if(s[0]=='A')
		{
			scanf("%d %d %d",&x,&y,&z);
			if(x==0)
			{
				if(y>z)
					spe++,ty[++tot]=1<<30;
				else
					ty[++tot]=-(1<<30);
			}
			else if(x<0)
			{
				//先把k值算出来（记在tx里），然后分情况讨论
				tx[++tot]=(ceil)((z*1.-y)/x),ty[tot]=2;
				if(tx[tot]>1000000)
					spe++,ty[tot]=1<<30;
				else if(tx[tot]<-1000000)
					ty[tot]=-(1<<30);
				else
					add(tx[tot],1,c2);
			}
			else
			{
				//同上
				tx[++tot]=(floor)((z*1.-y)/x),ty[tot]=1;
				if(tx[tot]>1000000)
					ty[tot]=-(1<<30);
				else if(tx[tot]<-1000000)
					ty[tot]=1<<30,spe++;
				else
					add(tx[tot],1,c1);
			}
		}
		else if(s[0]=='D')
		{
			//Delete 没什么技术含量
			scanf("%d",&x);
			if(tz[x])
				continue;
			tz[x]=1;
			if(ty[x]==1<<30)
				spe--;
			else if(ty[x]==1)
				add(tx[x],-1,c1);
			else if(ty[x]==2)
				add(tx[x],-1,c2);
		}
		else
		{
			//输出答案
			scanf("%d",&x);
			printf("%d\n",getsum(x-1,c1)+getsum(1000000,c2)-getsum(x,c2)+spe);
		}
	}
}

int main()
{
	//freopen("P5482.in","r",stdin);
	//freopen("P5482.out","w",stdout);
	work();
	return 0;
}

超烦人的细节题！(本人调了好几天 )

这里介绍一种只用到一只树状数组的写法(离线)。

树状数组的下标是：所有可能出现的数据进行离散化之后的值。

其含义为：当 x 离散化后值为 i 时能满足的不等式个数为 query(i) 个。

处理数据 首先我们先读入所有数据，并对数据处理：

Add ai bi ci：

若 ai>0 将 aix+bi>ci 转化成 x≥ti 的形式 。

若 ai<0 将 aix+bi>ci 转化成 x≤ti 的形式 。

并将 ti 丢进离散化的序列中。

注意：所有的除法运算都是向 0 取整，还要注意除法变号问题等等。

Del：

在处理 Add时提前记录第 x个 Add操作所对应的输入操作编号。

Query：

将 ki丢进离散化序列中。 之后将序列中的数离散化，给 Add中的 ti和 Query中的ki都附上一个离散化后的值( Insteadi) 。

计算答案 Add：

若 ai>0 则在 [ti,+∞) 区间内的 Insteadx 都可以使不等式成立。

同理，若 ai<0 则在 (−∞,ti] 区间内的 Insteadx 都可以使不等式成立。

在区间内加 1 即可 。

Del和 Add几乎一致，变为区间减 1。

Query ki即可直接查询并输出 Query(Insteadi)。代码我就不放出来了