感觉是一道比较有意思的题目qwq。

珂能会有更好の阅读体验

Descripstion

题目链接

• 给一堆形如 $ax+b>c$ 的不等式
• 刚开始没有不等式
• 需要支持：

1. 插入一个形如 $ax+b>c$ 的不等式；
2. 删除第 $i$ 个插入的不等式；
3. 查询 $x=k$ 的时候成立的不等式的个数。

$1\le n\le10^5,a,b,c\in[-10^8,10^8],k\in[-10^6,10^6]$。

Solution

看上去很不可做......而且这似乎和序列维护没啥关系啊qwq

然后我们机智地翻了一下这题标签：

哦~所以这和平衡树有啥联系啊。。？？？

诶，等下，$ax+b>c$ 似乎是能化简的说qwq

$ax+b>c$，那不就是 $ax>c-b$ 嘛qwq

那分类讨论一下：

当 $a>0$ 时，那么直接移项，得到 $x>\dfrac{c-b}{a}$

当 $a=0$ 时，那么 $ax=0$，这个不等式的成立与否和 $x$ 的取值无关，判断一下 $b$ 和 $c$ 的大小关系，再额外维护一个变量 $r$ 表示即可。

当 $a<0$ 时，移项，但注意两边除以负数，不等式要反向，所以得到 $x<\dfrac{c-b}{a}$。

那么我们就不用管什么不等式了，直接开一个数组存一下每一个不等式的 $\dfrac{c-b}{a}$ 即可。

每次查询的时候，相当于需要在数组中，找一下大于/小于 $k$ 的数，那不就是......

插入一个数
删除第 $i$ 个数
查询全局大于/小于 $k$ 的数的个数

诶，第三个不就是查询排名吗？

所以，这题就是要求：插入、删除、查询排名咯？

懂了，直接硬上平衡树！

大概就是建两个 $\text{Splay/Treap/奇奇怪怪的东西}$，一个表示不等式方向为 $<$ 的，另一个是不等式方向为 $>$ 的，然后就变成了一个裸的 插入+删除+查询排名 的平衡树板子了。

但是，但是，但是，对窝这种蒟蒻来说，硬要搞一个 $\text{Splay}$ 那种写一棵要耗费一小时+一头的头发的东西，有点难受诶。

然后我们机智地（又）翻了一下这题标签：

哦~所以还可以用树状数组？？？能支持插入、删除、查询排名的数据结构，不就是平衡树嘛，还有啥啊......？

然后注意到值域比较小，$k$ 只有 $\text{1e6}$。

诶，这和其他序列维护题通常的 $\text{1e9}$ 范围不太一样啊。

那么难道这题需要从值域入手去思考？

我们建一个值域上的树状数组，仿照逆序对那题的思路，每次加进来一个不等式，也就是加入一个 $\dfrac{c-b}{a}$ 的时候，直接在对应的值域位置上 $+1$。

仔细想一想，如果在值域上考虑，那么当 $x=k$ 的时候，要查询有多少个 $x>\dots$ 和 $x<\dots$ 成立，相当于什么呢？

不就是，前缀/后缀和嘛！

对呀，每次我们查询的时候，$k$ 在值域上相当于一个点。

把整个值域看成数轴，那么 $k$ 左边的 $\dfrac{c-b}{a}$，一定都小于 $k$。

也就是说，当 $x=k$ 时，$k$ 左边的 $\dfrac{c-b}{a}$ 都小于 $k$，那么 $x>\dfrac{c-b}{a}$ 一定成立。小于的话同理，就是后缀和。

然后删除，那就相当于在值域上对应的点 $-1$ 嘛。

所以此题变成了：

单点 $+1$
单点 $-1$
查询前缀和

懂了，直接树状数组！单点修改，查询前缀和，想到的第一个就是树状数组！

具体大概就是维护两个树状数组，一个代表前缀和，一个代表后缀和，然后查询的时候加一起就行了。

然而要用树状数组，还有一些 $\begin{matrix}\tiny\mathsf{d\acute{u}\ li\acute{u}\ x\grave{i}\ ji\acute{e}}\\\text{东西}\end{matrix}$ 需要处理：

Q： $a,b,c$ 的值域是 $m=\text{1e8}$，那你不应该开 $\text{1e8}$ 值域吗qwq，这 $O(m\log m)$ 的树状数组不就炸了qwq

A：其实不会。

首先我们要计算的是 $\dfrac{c-b}{a}$，不一定会有 $\text{1e8}$ qwq。

就算有了一些毒瘤数据，那也不用管在 $[-10^6,10^6]$ 之外的数据。毕竟 $k$ 只有 $1\text{e6}$，那么在这个范围之外的点，一定 会（不会） 被算进 前缀（后缀） 和里，直接特判一下，并加到之前说的 $r$ 里面即可。

所以最后范围还是 $\text{1e6}$ qwq。

Q：有负数和 $0$ qwq，众所周知铃和负数不能做下标。

A：直接平移整个值域，把 $[-10^6,10^6]$ 搞成 $[1,2\times10^6+1]$ 即可。

Q：$\dfrac{c-b}{a}$ 算出来是实数诶qwq，如果不是整数，那你怎么存啊qwq，这回总不能平移值域了吧qwq

A：但是 $k$ 是整数啊QAQ

其实插入的时候，如果 $a>0$，那么直接把它下取整，看作 $\left\lfloor\dfrac{c-b}{a}\right\rfloor$ 就行啦。

虽然会产生误差，但是，$\textbf{k}$ 是整数啊......

毕竟，如果 $k>\dfrac{c-b}{a}$，且 $k$ 是整数，那么一定有 $\left\lfloor k \right\rfloor>\dfrac{c-b}{a}$。

$a<0$ 时，一样的，只不过要改成上取整。

可以尝试举一下反例，然后你大概就懂为什么下取整的误差不会产生影响了。

Q：云浅好珂爱啊qwq

A：那当然awa

最后，放一下代码吧qwq：

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

#define MAXN 1000001
#define MAXM 2000001
#define lowbit(x) ((x)&(-(x)))

using namespace std;

int r,n,t[MAXN],l[MAXN];
//r：恒成立的不等式数量
//t[]：用于记录每一个 (c-b)/a
//l[]：用于记录每个不等式的性质
//l[id]=0 表示不等式方向为 >
//l[id]=1 表示不等式方向为 <
//l[id]=23333333 表示不等式恒成立
//l[id]=-23333333 表示不等式恒不成立
bool del[MAXN];//del[]：是否已经删除

struct BIT{

    int c[MAXN<<2];

    inline void PreFix(){
        memset(c,0,sizeof(c));
    }

    inline void modify(int x,int v){
        x+=MAXN;
        for(int i=x;i<=MAXM;i+=lowbit(i)){
            c[i]+=v;
        }
    }

    inline int query(int x){
        x+=MAXN;
        int ans=0;
        for(int i=x;i;i-=lowbit(i)){
            ans+=c[i];
        }
        return ans;
    }

};//树状数组

BIT tree1,tree2;

int cnt=0;

void donothing(){
    //珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！珂朵莉珂爱！
    //铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！铃酱 txdy！
    //『君指先跃动の光は、私の一生不変の信仰に、唯私のお姉さま永生き！』
}

#define qwq 23333333
#define awa 1000000

int main(void){

    //freopen("P5482_1.in","r",stdin);
    //freopen("P548201.out","w",stdout);
    tree1.PreFix();tree2.PreFix();

    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        char opt[8];
        scanf("%s",opt);
        if(opt[0]=='A'){
            ++cnt;
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            //分类讨论，上面已经说过。
            if(a==0){
                if(b>c){
                    r++;
                    l[cnt]=qwq;
                }
                else l[cnt]=-qwq;
            }
            else if(a>0){
                int p=(floor)((c*1.-b)/a);
                l[cnt]=0;
                t[cnt]=p;
                if(p+awa<0){
                    r++;
                    l[cnt]=qwq;
                }
                else if(p>awa)l[cnt]=-qwq;
                else{
                    tree1.modify(p,1);
                }
            }
            else{
                int p=(ceil)((c*1.-b)/a);
                l[cnt]=1;
                t[cnt]=p;
                if(p+awa<0)l[cnt]=-qwq;
                else if(p>awa){
                    l[cnt]=qwq;
                    r++;
                }
                else{
                    tree2.modify(p,1);
                }
            }
        }
        else if(opt[0]=='D'){
            int id;
            scanf("%d",&id);
            if(del[id])continue;
            del[id]=1;
            if(l[id]==qwq)r--;
            else if(l[id]==-qwq)donothing();
            else if(l[id]==0)tree1.modify(t[id],-1);
            else if(l[id]==1)tree2.modify(t[id],-1);
        }
        else{
            int k;
            scanf("%d",&k);
            printf("%d\n",r+tree1.query(k-1)+tree2.query(awa)-tree2.query(k));
        }
    }

    return 0;
}