72分 做法动态开点 WA #8 #10 #11 #12玄关求条

#include<bits/stdc++.h>
//#include<windows.h>
#define int long long
#define los tree[x].ls
#define ros tree[x].rs
using namespace std;
const int N=1e5+5;
struct node{
	int ls,rs;
	int minn,maxx,val;
	node(){
		minn=1e15;
		maxx=-1e15;
	}
}tree[N*5];
int cnt,root,n=2e7+100,Q,mi,ma,vsum,ans=1e7+10,flag;
void push_up(int x){
	tree[x].maxx=max(tree[los].maxx,tree[ros].maxx);
	tree[x].minn=min(tree[los].minn,tree[ros].minn);
	tree[x].val=tree[los].val+tree[ros].val;
}
void Qxiu(int l,int r,int left,int right,int& x,int f){
	if(!x)x=++cnt;
	if(left<=l&&r<=right){
		if(f==-n){
			if(tree[x].val)tree[x].val--;
			if(!tree[x].val)tree[x].maxx=-1e15,tree[x].minn=1e15;
		}
		else{
			tree[x].maxx=tree[x].minn=f;
			tree[x].val++;
		}
		return ;
	}
	int mid=l+r>>1;
	if(left<=mid)Qxiu(l,mid,left,right,los,f);
	if(right>mid)Qxiu(mid+1,r,left,right,ros,f);
	push_up(x);
}
void Qzo(int l,int r,int left,int right,int& x){
	if(l==1&&r==n)mi=1e15,ma=-1e15,vsum=0;
	if(!x)x=++cnt;
	if(left<=l&&r<=right){
		vsum+=tree[x].val;
		mi=min(mi,tree[x].minn);
		ma=max(ma,tree[x].maxx);
		return ;
	}
	int mid=l+r>>1;
	if(left<=mid)Qzo(l,mid,left,right,los);
	if(right>mid)Qzo(mid+1,r,left,right,ros);
	push_up(x);
}
void Qzo1(int &x,int vll,int l,int r){//需要修改改成log^2 
	if(!x)return;
	//Sleep(100);
	//cout<<"res:"<<l<<" "<<r<<"\n";
	if(l==r){
		cout<<l-ans<<"\n";
		flag=0;
		return ;
	}
	int mid=l+r>>1;
	int lv,rv;
	if(l-1>0)Qzo(1,n,1,l-1,root);
	lv=vsum;
	Qzo(1,n,1,mid,root);
	rv=vsum;
	if(vll>=lv&&vll<=tree[los].val+lv&&flag)Qzo1(los,vll,l,mid);
	if(vll>=rv&&vll<=tree[ros].val+rv&&flag)Qzo1(ros,vll,mid+1,r);
	push_up(x);
}
signed main(){
	cin>>Q;
	while(Q--){
		flag=1;
		int op,x;
		cin>>op>>x;
		x+=ans;
		if(op==1){
			Qxiu(1,n,x,x,root,x);
		}
		if(op==2){
			Qxiu(1,n,x,x,root,-n);
		}
		if(op==3){
			Qzo(1,n,1,x-1,root);
			cout<<vsum+1<<"\n";
		}
		if(op==4){
			Qzo1(root,x-ans,1,n);
		}
		if(op==5){
			Qzo(1,n,1,x-1,root);
			cout<<ma-ans<<"\n";
		}
		if(op==6){
			Qzo(1,n,x+1,n,root);
			cout<<mi-ans<<"\n";
		}
	}
	return 0;
}