P5482 [JLOI2011]不等式组,cckk

题目描述

旺汪与旺喵最近在做一些不等式的练习。这些不等式都是形如 ax+b>cax+b>c 的一元不等式。当然，解这些不等式对旺汪来说太简单了，所以旺喵想挑战旺汪。旺喵给出一组一元不等式，并给出一个数值。旺汪需要回答的是 x=kx=k 时成立的不等式的数量。聪明的旺汪每次都很快就给出了答案。你的任务是快速的验证旺汪的答案是不是正确的。

输入格式

输入第一行为一个正整数 nn，代表接下来有 nn 行。

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

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

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

1
1
0
0

说明/提示

样例 1 说明

第 11 条添加到不等式组的不等式为 x+1>1x+1>1，第 22 条为 −2x+4>3−2x+4>3。所以第 11 个询问的时候只有第 22 条不等式可以成立，故输出 1。

然后删除第 11 条不等式，再询问的时候依然是只有第 22 条不等式可以成立，故输出 11 。

再删除第 22 条不等式后，因为不等式组里面没有不等式了，所以没有不等式可以被满足，故输出 00。

继续加入第 33 条不等式 8x+9>1008x+9>100，当 x=k=10x=k=10 时有 8\times 10+9=89<1008×10+9=89<100，故也没有不等式可以被满足，依然输出 00。

数据规模与约定

• 对于 20\%20% 的数据，保证 n\leq 10^3n≤103。
• 对于 40\%40% 的数据，保证 n\leq 10^4n≤104。
• 对于 100\%100% 的数据，保证 1\leq n\leq 10^51≤n≤105，a,b,c\in[-10^8,10^8]a,b,c∈[−108,108]，k\in[-10^6,10^6]k∈[−106,106]。

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

using namespace std;

const int MAXN = 300005;
const int INF=0x3f3f3f3f;

struct treap{
    struct node{
        int l,r;
        int val, pri, size;
    };
    struct node* t;
    int p, root;

    treap():p(0),root(0){
        t = (node*)malloc(MAXN * sizeof(node));
    }
    ~treap(){
        free((void*)t);
    }

    void update(int x)
    {
        t[x].size = 1 + t[t[x].l].size + t[t[x].r].size;
    }

    void split(int now, int v, int &x, int &y)
    {
        if(!now){
            x=y=0;
            return;
        }
        if(t[now].val<=v){
            x=now;
            split(t[now].r, v, t[now].r, y);
        }
        else{
            y=now;
            split(t[now].l, v, x, t[now].l);
        }
        update(now);
    }

    int merge(int x, int y)
    {
        if(!x || !y)
            return x+y;
        if(t[x].pri < t[y].pri){
            t[x].r = merge(t[x].r, y);
            update(x);
            return x;
        }
        else{
            t[y].l = merge(x, t[y].l);
            update(y);
            return y;
        }
    }

    int create_node(int v)
    {
        t[++p].size=1;
        t[p].val = v;
        t[p].pri = rand();
        return p;
    }

    void insert(int v)
    {
        int x,y;
        split(root,v,x,y);
        root=merge(merge(x,create_node(v)),y);
    }

    void del(int v)
    {
        int x,y,z;
        split(root,v,x,y);
        split(x, v-1, x, z);
        z=merge(t[z].l, t[z].r);
        root=merge(merge(x,z),y);
    }

    int rk(int v)
    {
        int x,y;
        split(root, v-1, x, y);
        int ans =t[x].size;
        root = merge(x,y);
        return ans;
    }

    int rk2(int v)
    {
        int x, y;
        split(root, v, x, y);
        int ans = t[y].size;
        root = merge(x,y);
        return ans;
    }

    int kth(int now, int k)
    {
        while(true){
            if(k<=t[t[now].l].size)
                now=t[now].l;
            else if(k==t[t[now].l].size+1)
                return t[now].val;
            else{
                k-=t[t[now].l].size + 1;
                now = t[now].r;
            }
        }
    }

    int pre(int v)
    {
        int x,y;
        split(root, v-1, x, y);
        int ans = kth(x, t[x].size);
        root=merge(x,y);
        return ans;
    }

    int suc(int v)
    {
        int x,y;
        split(root, v, x, y);
        int ans = kth(y,1);
        root=merge(x,y);
        return ans;
    }
};

int a[MAXN], b[MAXN], c[MAXN],d[MAXN];
int cnt;
int res[MAXN];

int main()
{
    int n;
    string s;
    cin>>n;

    treap t1,t2;
    // t1 for positive a
    // t2 for negative a

    int ans = 0;

    for(int i = 1; i <= n; ++i){
        cin>>s;
        switch(s[0]){
            case 'A':{
                cnt++;
                cin>>a[cnt]>>b[cnt]>>c[cnt];
                d[cnt] = 1;

                if(a[cnt] > 0){
                    // solution : x > (c-b) / a, x >= floor((c-b)/a)
                    res[cnt] = floor(1.0*(c[cnt]-b[cnt])/a[cnt]);
                    t1.insert(res[cnt]);
                }
                else if(a[cnt] == 0){
                    // solution: b > c
                    if(b[cnt]>c[cnt]){
                        ans++;
                    }
                }
                else{
                    // solution : x < (c-b) / a, x <= ceil((c-b)/a)
                    res[cnt] = ceil(1.0*(c[cnt]-b[cnt])/a[cnt]);
                    t2.insert(res[cnt]);
                }

            }
            break;
            
            case 'D':{
                int k;
                cin >> k;
                if(d[k] == 0)
                    break;
                d[k]--;
                if(a[k] > 0){
                    t1.del(res[k]);
                }
                else if(a[k] == 0){
                    if(b[k] > c[k])
                        ans--;
                }
                else{
                    t2.del(res[k]);
                }
            }
            break;

            case 'Q':{
                int k;
                cin>>k;
                cout << ans + t1.rk(k) +  t2.rk2(k) << endl;
            }
            break;

        }
    }
    return 0;       
}