有鬼是吧?????
查看原帖
有鬼是吧?????
833124
BIOS楼主2023/8/4 17:35
#include <iostream>
using namespace std;
const int N = 3e5 + 5, INF = 0x7f7f7f7f;
struct node
{
    int l, r, k, v, size;
} tr[N];
int idx, k, lim, n, root, tot, tmp;
char op;
int get(int k)
{
    tr[++idx].k = k, tr[idx].size = 1, tr[idx].v = rand();
    return idx;
}
void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}
void split(int p, int k, int &x, int &y)
{
    if (!p)
    {
        x = y = 0;
        return;
    }
    if (tr[p].k <= k)
        x = p, split(tr[x].r, k, tr[x].r, y);
    else
        y = p, split(tr[y].l, k, x, tr[y].l);
    pushup(p);
}
int merge(int x, int y)
{
    if (!x || !y)
        return x | y;
    if (tr[x].v < tr[y].v)
    {
        tr[x].r = merge(tr[x].r, y), pushup(x);
        return x;
    }
    tr[y].l = merge(x, tr[y].l), pushup(y);
    return y;
}
void insert(int k)
{
    int x, y, z;
    split(root, k, x, y), z = get(k);
    root = merge(merge(x, z), y);
}
int get_key(int p, int k)
{
    if (tr[tr[p].l].size >= k)
        return get_key(tr[p].l, k);
    if (tr[tr[p].l].size + 1 == k)
        return tr[p].k;
    return get_key(tr[p].r, k - tr[tr[p].l].size - 1);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> lim;
    int x, y, z;
    while (n--)
    {
        cin >> op >> k;
        if (op == 'I')
        {
            if (k >= lim)
            {
                k -= tmp, split(root, k, x, y);
                root = merge(x, merge(get(k), y));
            }
        }
        else if (op == 'A')
            tmp += k;
        else if (op == 'S')
        {
            tmp -= k, split(root, lim - tmp - 1, x, y);
            tot += tr[x].size, root = y;
        }
        else
        {
            if (k > tr[root].size)
                printf("-1\n");
            else
                cout << get_key(root, tr[root].size + 1 - k) + tmp << "\n";
        }
    }
    cout << tot << endl;
}

我不理解,为什么我对F的询问输出“-1”总是在最后出现,也就是在tot后面出现,我的tot输出不是最后一行?????

2023/8/4 17:35
加载中...