关于O2
查看原帖
关于O2
560006
yzq_yzq楼主2023/8/25 19:10

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;
}

2023/8/25 19:10
加载中...