RE
查看原帖
RE
384214
esquigybcu楼主2021/8/30 16:49
#include <stdio.h>
#include <math.h>

const int N = 1e5 + 10, K = 1e6 + 10;
inline int lowbit(int x){return x & -x;}

int q, kind[N], k[N], cnt; int top;
bool deleted[N];
// kind[i] = 0 <=> k[i] < x
// kind[i] = 1 <=> k[i] > x
// kind[i] = 2 <=> 恒成立
// kind[i] = 3 <=> 恒不成立
// cnt为恒成立的个数

int tree0[2 * K], tree1[2 * K];
// 分别对应kind = 0, kind = 1

int query(int *tree, int x)
{
    x += N; // [-K, K] |-> [0, 2K]
    int ans = 0;
    for (; x; x -= lowbit(x))
        ans += tree[x];
    return ans;
}

void add(int* tree, int x, int y)
{
    x += N;
    for (; x < 2 * K; x += lowbit(x))
        tree[x] += y;
}

int main()
{
    scanf("%d", &q);
    int a, b, c, x;
    char s[20];
    while (q--)
    {
        scanf(" %s", s);
        if (s[0] == 'A')
        {
            scanf("%d %d %d", &a, &b, &c);
            if (a == 0)
            {
                if (b > c)
                    cnt++, kind[top] = 2;
                else
                    kind[top] = 3;
                top++;
            }
            else if (a > 0) // x > k
            {
                k[top] = floor(((double)c - b) / a);
                kind[top] = 0;
                if (k[top] > 1e6)
                    kind[top] = 3;
                else if (k[top] < -1e6)
                    kind[top] = 2, cnt++;
                else
                    add(tree0, k[top], 1);
                top++;
            }
            else if (a < 0) // x < k
            {
                k[top] = ceil(((double)c - b) / a);
                kind[top] = 1;
                if (k[top] < -1e6)
                    kind[top] = 3;
                else if (k[top] > 1e6)
                    kind[top] = 2, cnt++;
                else
                    add(tree1, k[top], 1);
                top++;
            }
        }
        else if (s[0] == 'Q')
        {
            scanf("%d", &x);
            printf("%d\n", query(tree0, x - 1) + query(tree1, 1e6) - query(tree1, x) + cnt);
        }
        else if (s[0] == 'D')
        {
            scanf("%d", &x);
            x--;
            if (deleted[x])
                continue;
            deleted[x] = true;
            if (kind[x] == 0)
                add(tree0, k[x], -1);
            else if (kind[x] == 1)
                add(tree1, k[x], -1);
            else if (kind[x] == 2)
                cnt--;
        }
    }
    return 0;
}
2021/8/30 16:49
加载中...