RT,我的代码开O2会T,不开AC
代码:
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
std::mt19937 rnd(233);
ll mi;
template<int T> struct fhq{
struct node{
int l,r,s,key;
ll val,tag;
}t[T+5];
int tot,rt,cnt;
fhq(){
tot=rt=0;
cnt=0;
}
inline int newnode(int val){
tot++;
t[tot].s=1;
t[tot].l=t[tot].r=0;
t[tot].val=val;
t[tot].key=rnd();
t[tot].tag=0;
return tot;
}
inline int pushup(int x){
t[x].s=t[t[x].l].s+t[t[x].r].s+1;
}
inline void down(int x){
if(t[x].tag!=0){
t[t[x].l].val+=t[x].tag;
t[t[x].r].val+=t[x].tag;
t[t[x].l].tag+=t[x].tag;
t[t[x].r].tag+=t[x].tag;
t[x].tag=0;
return;
}
}
void split(int p,ll val,int &l,int &r){
if(!p) {
l=r=0;
return;
}
down(p);
if(t[p].val<=val){
l=p;
split(t[p].r,val,t[p].r,r);
}else{
r=p;
split(t[p].l,val,l,t[p].l);
}
pushup(p);
}
int merge(int l,int r){
if(!l||!r) return l|r;
if(t[l].key>t[r].key){
down(l);
t[l].r=merge(t[l].r,r);
pushup(l);
return l;
}else{
down(r);
t[r].l=merge(l,t[r].l);
pushup(r);
return r;
}
}
inline void insert(ll val){
if(val<mi) return;
int dl,dr;
split(rt,val,dl,dr);
rt=merge(merge(dl,newnode(val)),dr);
}
inline int rank_find(int rnk){
if(rnk>t[rt].s) return -1;
rnk=t[rt].s-rnk+1;
int p=rt,cnt=0;
while(1){
down(p);
if(t[t[p].l].s+1==rnk) return t[p].val;
else if(t[t[p].l].s+1<rnk) rnk-=t[t[p].l].s+1,p=t[p].r;
else p=t[p].l;
}
}
inline void add(ll val){
t[rt].tag+=val;
t[rt].val+=val;
if(val<0){
int dl,dr;
split(rt,mi-1,dl,dr);
cnt+=t[dl].s;
rt=dr;
}
}
};
fhq<300020> t;
int n;
int main(){
n=in(); mi=in();
while(n--){
char op[9];
ll v;
sf("%s",op+1);
sf("%lld",&v);
if(op[1]=='I'){
t.insert(v);
}else{
if(op[1]=='F'){
pf("%d\n",t.rank_find(v));
}else{
if(op[1]=='S') v=-v;
t.add(v);
}
}
}
pf("%d\n",t.cnt);
return 0;
}