题意描述

给出 $n$ 次操作，每次操作是下列的一种：

添加一条形如 $ax + b > c$ 的不等式
删除其中一条不等式
询问当 $x = k$ 时成立的不等式的个数

请快速处理以上操作并输出相应的结果。

输入格式

第一行为一个正整数 $n$，代表接下来有 $n$ 行。

接下来每一行可能有 $3$ 种形式：

Add a b c：表明要往不等式组添加一条不等式 $ax+b>c$。
Del i：代表删除掉第 $i$ 条添加的不等式（最先添加的是第 $1$ 条）。
Query k：代表一个询问，即当 $x=k$ 时，在当前不等式组内成立的不等式的数量。

注意：一开始不等式组为空，$a,b,c,i,k$ 均为整数，且保证所有操作均合法，不会出现要求删除尚未添加的不等式的情况。

输出格式

对于每一个询问 Query k，输出一行一个整数，代表询问的答案。

Input & Output ‘s examples

Input ‘s eg

9
Add 1 1 1
Add -2 4 3
Query 0
Del 1
Query 0
Del 2
Query 0
Add 8 9 100
Query 10

Output ‘s eg

数据范围和约定

对于 $20\%$ 的数据，保证 $n\leq 10^3$。

对于 $40\%$ 的数据，保证 $n\leq 10^4$。

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^5$ ，$a,b,c \in \lbrack -10^8,10^8 \rbrack$，$k\in \lbrack-10^6,10^6 \rbrack$。

分析

直接带入维护并不好维护，考虑移项。

对于不等式 $ax + b > c$ ，移项之后有以下三种情况：

$a = 0$，移项后成了 $b > c$。这种情况要么恒成立要么永远不成立，特判即可
$a > 0$，移项后成了 $x > \lceil \frac{c - b}{a} \rceil$。
$a < 0$，移项后成了 $x < \lfloor \frac{c - b}{a} \rfloor$。

对于情况 $2$ 和情况 $3$，我们各开一个树状数组维护区间内大于或小于某个数的个数即可。

设 $t1$ 维护 $a > 0$ 的情况， $t2$ 维护 $a < 0$ 的情况，则查询 $x = k$ 的答案即为

$cnt + \sum_{i = k + 1}^{10^6} t1[i] + \sum_{i = 1}^{k - 1} t2[i]$

其中，$cnt$ 为恒成立的不等式的数目。

单次操作的时间复杂度均为 $O(\log k)$，总时间复杂度为 $O(n \log k)$。足以通过本题。

细节部分将在代码注释中呈现，建议仔细参考。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 1000000 + 5;
const int HA = 998244353;

int tree1[M << 1] , tree2[M << 1] , lim = (M << 1);

int lowbit(int x) { return x & (-x); }

void add(int x , int val , int tree[]){     
    //由于树状数组不可以有0 ，为防止越界，我在每一个x上加了一个M'
    x += M;
    for(int i = x; i <= lim; i += lowbit(i)){
        tree[i] += val;
    }
}

int query(int x , int tree[]){
    x += M;
    int ans = 0;
    for(int i = x; i ; i -= lowbit(i)){
        ans += tree[i];
    }
    return ans;
}

int type[M << 1] , tk[M << 1] , tot , cnt; 

// type[i] 第i个操作的类型    tk[i] 第i个操作的x值 或 k值

// type[i] = 2 第i个操作需要变号    type[i] = 1 不需要变号
// type[i] = (1 << 30) 恒成立且可忽视  type[i] = -(1 << 30) 不成立且可忽视


void insert(){
    int a , b , c;
    read(a) , read(b) , read(c);
    if(a == 0){ //处理恒成立情况
        if(b > c){
            cnt ++ , type[++ tot] = (1 << 30);
        }
        else{
            type[++ tot] = -(1 << 30);
        }
    }
    else if(a < 0){
        tk[++ tot] = (ceil)((1.0 * c - b) / a);
        type[tot] = 2;
        if(tk[tot] > (int)1e6){
            //由于k的范围为[-1e6 , 1e6]，则解出结果大于1e6 或 小于-1e6 的不等式均可视为恒成立不等式
            cnt ++ , type[tot] = (1 << 30);
        }
        else if(tk[tot] < (int)-1e6){
            type[tot] = -(1 << 30);
        }
        else{
            //树状数组维护小于某个数的个数
            add(tk[tot] , 1 , tree2);
        }
        
    }
    else if(a > 0){ //大体同上
        tk[++ tot] = (floor)((1.0 * c - b) / a);
        type[tot] = 1;
        if(tk[tot] > (int)1e6){
            type[tot] = -(1 << 30);
        }
        else if(tk[tot] < (int)-1e6){
            cnt ++ , type[tot] = (1 << 30);
        }
        else{
            add(tk[tot] , 1 , tree1);
        }
    }
}

int del[M << 1];

void Delete(){
    int k; read(k);
    
    if(del[k]) return ; //记录该不等式是否已经删除
    del[k] = 1;
    
    //根据删除的不等式的不同选择删除的树状数组
    if(type[k] == (1 << 30)) cnt --;
    else if(type[k] == 1){  
        add(tk[k] , -1 , tree1);
    }
    else if(type[k] == 2){
        add(tk[k] , -1 , tree2);
    }
}

int Query(){
    int x; read(x);
    //利用前缀和思想进行查询
    return cnt + query(x - 1 , tree1) + query((int)1e6 , tree2) - query(x , tree2);
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n; read(n);
    
    char op[10];
    while(n --){
        scanf("%s" , op + 1);
        if(op[1] == 'A'){
            insert();
        }
        else if(op[1] == 'D'){
            Delete();
        }
        else if(op[1] == 'Q'){
            printf("%d\n" , Query());
        }
        
    }

    return 0;
}