Title Link

thinking

In fact, this problem is to modify the delete operation in the tree. I have a way of doing it. When deleting, if the number to be deleted is larger than the root of this subtree, then turn the root into the right child of the root, which is equivalent to deleting the entire left subtree and root node. Then you need to re maintain the siz and maintain the balance.

I wrote the rotate function wrong. 30 minutes. I didn't get it right

The meaning of this sentence was adjusted for another 30 minutes. Twenty-three thousand three hundred and thirty-three

Code

//Delete once after each modification and change the delete function
/*
* @Author: wxyww
* @Date:   2018-12-02 08:41:38
* @Last Modified time: 2018-12-02 10:02:49
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
#define ls TR[cur].ch[0]
#define rs TR[cur].ch[1]
typedef long long ll;
const int N = 100000 + 100,INF = 1e9 + 7;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int ch[2],id,val,siz,cnt;
}TR[N];
int MIN;
void up(int cur) {
    TR[cur].siz = TR[ls].siz + TR[rs].siz + TR[cur].cnt;
}
void rotate(int &cur,int f) {
    int son = TR[cur].ch[f];
    TR[cur].ch[f] = TR[son].ch[f ^ 1];
    TR[son].ch[f ^ 1] = cur;
    up(cur);
    cur = son;
    up(cur);
}
int tot;
void insert(int &cur,int val) {
    if(!cur) {
        cur = ++tot;
        TR[cur].id = rand();
        TR[cur].val = val;
        TR[cur].siz = TR[cur].cnt = 1;
        return;
    }
    TR[cur].siz++;
    if(val == TR[cur].val) {TR[cur].cnt++;return;}
    int d = val > TR[cur].val;
    insert(TR[cur].ch[d],val);
    if(TR[TR[cur].ch[d]].id < TR[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
    if(!cur) return;
    if(val <= TR[cur].val) del(ls,val);
    else {
        del(rs,val);
        cur = rs;
    }
    up(cur);
    if(TR[ls].id < TR[cur].id && ls) rotate(cur,0);
    if(TR[rs].id < TR[cur].id && rs) rotate(cur,1);
}
int kth(int cur,int now) {
    while(1) {
        if(now > TR[rs].siz + TR[cur].cnt) now -= TR[rs].siz + TR[cur].cnt,cur = ls;
        else if(now <= TR[rs].siz) cur = rs;
        else return TR[cur].val; 
    }
}
int main() {
    int rt = 0;
    int n = read(),change = 0,num = 0;
    MIN = read();
    char c;
    while(n--) {
        int x;
        scanf("\n%c %d",&c,&x);
        if(c == 'I') {
            x -= change;
            if(x >= MIN) num++,insert(rt,x);
        }
        if(c == 'A') MIN -= x,change += x;
        if(c == 'S') {
            MIN += x;
            del(rt,MIN);
            change -= x;
        }
        if(c == 'F') {
            if(x > TR[rt].siz) puts("-1");
            else printf("%d\n",kth(rt,x) + change);
        }
    }
    cout<<num - TR[rt].siz<<endl;
    return 0;
}

a brief remark

Time will turn what you owe into something you can't afford, and turn a lot of things into something you can't. ——Darling, touch your head