40pts求助!ytq说这题做对就和我在一起,求助各位帮助%%%
查看原帖
40pts求助!ytq说这题做对就和我在一起,求助各位帮助%%%
817044
cjwdyzxfblzs楼主2023/5/5 19:55

不知道为什么会WA好多

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(233);
inline int read()
{
    int o = 1, p = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            o = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        p = p * 10 + c - '0',
        c = getchar();
    return o * p;
}
const int N = 100010;
struct node
{
    node *ls, *rs;
    int val;
    int rand;
    int size;
    explicit node(int x) : size(1)
    {
        ls = rs = nullptr;
        val = x;
        rand = rnd();
        size = 1;
    }
};
struct FHQ
{
    node *root;
    node *L, *R, *Z;
    int idx;
    void push_up(node *u)
    {
        if (u == nullptr)
            return;
        u->size = (u->ls ? u->ls->size : 0) + (u->rs ? u->rs->size : 0) + 1;
    }
    node *newnode(int val)
    {
        return new node(val);
    }
    void split(node *u, int x, node *&L, node *&R)
    {
        if (!u)
            return L = R = nullptr, void();
        if (u->val <= x)
        {
            L = u;
            split(u->rs, x, u->rs, R);
        }
        else
        {
            R = u;
            split(u->ls, x, L, u->ls);
        }
        push_up(u);
    }
    node *merge(node *x, node *y)
    {
        if (x == nullptr)
            return y;
        if (y == nullptr)
            return x;
        if (x->rand < y->rand)
        {
            x->rs = merge(x->rs, y);
            push_up(x);
            return x;
        }
        else
        {
            y->ls = merge(x, y->ls);
            push_up(y);
            return y;
        }
    }
    void insert(int val)
    {
        split(root, val - 1, L, R);
        root = merge(merge(L, new node(val)), R);
    }
    void del(int pos)
    {
        split(root, pos, L, R);
        split(L, pos - 1, L, Z);
        root = merge(L, R);
    }
    int yjx(int val)
    {
        split(root, val, L, R);
        int xxx = (R != nullptr ? R->size : 0);
        root = merge(L, R);
        return xxx;
    }
    int qsy(int val)
    {
        split(root, val - 1, L, R);
        int xxx = (L != nullptr ? L->size : 0);
        root = merge(L, R);
        return xxx;
    }
} f1, f2;
int n;
struct nep
{
    double a, b, c;
    bool alive;
    int val()
    {
        if (a > 0)
            return floor((c - b) / a);
        else
            return ceil((c - b) / a);
    }
} ne[N];
int cnt = 0;
int ze = 0;
signed main()
{
    // freopen("rand.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string str;
        int a, b, c;
        cin >> str;
        if (str[0] == 'A')
        {
            cin >> a >> b >> c;
            ne[++cnt].a = a;
            ne[cnt].b = b;
            ne[cnt].c = c;
            ne[cnt].alive = true;
            if (a > 0)
            {
                f1.insert(ne[cnt].val());
                // cout << " :  " << ne[cnt].val() << endl;
                continue;
            }
            else if (a < 0)
                f2.insert(ne[cnt].val());
            else
                ze += (b > c);
            //  cout << "  ze : "<< ze << endl;
        }
        else if (str[0] == 'D')
        {
            cin >> a;
            if (ne[a].alive)
            {
                ne[a].alive = false;
                if (ne[a].a > 0)
                    f1.del(ne[a].val());
                else if (ne[a].a < 0)
                    f2.del(ne[a].val());
                else
                    ze -= (ne[a].b > ne[a].c);
            }
        }
        else
        {
            cin >> a;
            cout << f2.yjx(a) + f1.qsy(a) + ze << "\n";
        }
    }

    return 0;
}
2023/5/5 19:55
加载中...