我怀疑是push_down搞错了,除了wa还有一个tle
#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define maxn 300010
using namespace std;
struct node{
int s[2], p, v, size, lazy;
void init(int _p, int _v) {
p = _p; v = _v;
}
}tree[maxn];
int idx;
void push_down(int index) {
tree[index].v += tree[index].lazy;
tree[tree[index].s[0]].lazy += tree[index].lazy;
tree[tree[index].s[1]].lazy += tree[index].lazy;
tree[index].lazy = 0;
}
void push_up(int index) {
tree[index].size = tree[tree[index].s[0]].size + tree[tree[index].s[1]].size + 1;
}
int root;
int ws(int index) {
return tree[tree[index].p].s[1] == index;
}
int setson(int son, int father, int whichson) {
if(father) tree[father].s[whichson] = son;
if(son) tree[son].p = father;
}
void rotate(int index) {
int f = tree[index].p, ff = tree[f].p, w = ws(index), wf = ws(f);
int son = tree[index].s[!w];
setson(son, f, w); setson(index, ff, wf); setson(f, index, !w);
push_up(f); push_up(index);
}
void splay(int index, int rt = 0) {
while(tree[index].p != rt) {
int f = tree[index].p, ff = tree[f].p;
if(ff != rt) {
if(ws(index) == ws(f)) {
rotate(f);
} else {
rotate(index);
}
}
rotate(index);
}
if(!rt) root = index;
}
void insert(int index) {
int u = root, p = 0;
while(u) {
push_down(u);
p = u;
u = tree[u].s[index > tree[u].v];
}
u = ++idx;
tree[u].size = 1;
tree[u].p = p;
tree[u].v = index;
tree[p].s[index > tree[p].v] = u;
splay(u);
}
int n, minn;
int ans = 0;
int ask_v(int index) {
int u = root, p = 0;
while(u) {
push_down(u);
p = u;
if(tree[tree[u].s[0]].size+1 == index) {
int anstemp = tree[u].v;splay(u);
return anstemp;
} else if(tree[tree[u].s[0]].size+1 > index) {
u = tree[u].s[0];
} else {
u = tree[u].s[1];
index = index-tree[tree[u].s[0]].size-1;
}
}
return 0;
}
int ask_index(int index) {
int u = root, p=0;
while(u) {
push_down(u);
p = u;
u = tree[u].s[index > tree[u].v];
}
return p;
}
int idxminn;
void del() {
int temp1 = ask_index(minn);
temp1++;
if(temp1 == idxminn) {
return;
}
splay(temp1); splay(idxminn, temp1);
ans += tree[tree[idxminn].s[1]].size;
tree[idxminn].s[1] = 0;
push_up(idxminn); push_up(temp1);
}
signed main() {
// freopen("a.in","r",stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> minn; int sum = 0;
insert(inf); insert(-inf);
idxminn = idx;
for(int i=1; i<=n; ++i) {
char ch; cin >> ch;
if(ch == 'I') {
int k; cin >> k;
if(k>minn) insert(k);
} else if(ch == 'A') {
int k; cin >> k;
tree[root].lazy += k;
} else if(ch == 'S') {
int k; cin >> k;
tree[root].lazy -= k;
del();
//
} else if(ch == 'F') {
int k; cin >> k;
if(k > tree[root].size-2) {
cout << -1 << endl;
} else {
cout << ask_v(tree[root].size-k) << endl;
}
}
}
cout << ans;
return 0;
}
/*
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
*/