Treep 全部MLE??????
查看原帖
Treep 全部MLE??????
750803
_Revenge_楼主2022/9/25 19:40

是哪里写错了吗? 还是说空间卡的太ex.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N=2e5+50;
const int M=1e5+50;
const int Mod=1e9+7;
const int Inf=INT_MAX;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int sum=0,root=0;

int num[N],v[N],rd[N],son[N][2],siz[N];

void push_up(int p){
	siz[p]=siz[son[p][0]]+siz[son[p][1]]+num[p];
}

void rotate(int &p,int d){
	int k=son[p][d^1];
	son[p][d^1]=son[k][d];
	son[k][d]=p;
	push_up(p);
	push_up(k);
	p=k;
}

void ins(int &p,int x){
	if(!p){
		++sum;
		p=sum;
		num[p]=siz[p]=1;
		rd[p]=rand();
		v[p]=x;
		return;
	}
	if(v[p]==x){
		siz[p]++;
		num[p]++;
		return;
	}
	int d=x>v[p];
	ins(son[p][d],x);
	if(rd[p]<rd[son[p][d]]) rotate(p,d^1);
	push_up(p);
}

void del(int &p,int x){
	if(!p) return;
	if(v[p]>x) del(son[p][0],x);else 
	if(v[p]<x) del(son[p][1],x);else{
		if(!son[p][0]&&!son[p][1]){
			num[p]--;siz[p]--;
			if(!num[p]) p=0;
		}else
		if(!son[p][0]&&son[p][1]){
			rotate(p,0);
			del(son[p][0],x);
		}else
		if(son[p][0]&&!son[p][1]){
			rotate(p,1);
			del(son[p][1],x);
		}else{
			int d=rd[son[p][0]]>rd[son[p][1]];
			rotate(p,d);
			del(son[p][d],x);
		}
	} 
	push_up(p);
}

int rk(int p,int x){
	if(!p) return 1;
	if(x==v[p]) return siz[son[p][0]]+1;
	if(x<v[p]) return rk(son[p][0],x); else
	if(x>v[p]) return siz[son[p][0]]+num[p]+rk(son[p][1],x);
}

int fd(int p,int x){
	if(!p) return 0;
	if(siz[son[p][0]]>=x) return fd(son[p][0],x); else
	if(siz[son[p][0]]+num[p]<x)
		return fd(son[p][1],x-siz[son[p][0]]-num[p]);
	else 
		return v[p];
}

int pre(int p,int x){
	if(!p) return -Inf;
	if(v[p]>=x) return pre(son[p][0],x);
	else return max(v[p],pre(son[p][1],x));
}

int suc(int p,int x){
	if(!p) return Inf;
	if(v[p]<=x) return suc(son[p][1],x);
	else return min(v[p],suc(son[p][0],x));
}

int n,m;

int main()
{
	srand(time(NULL));
	n=read(),m=read();
	for(int i=1;i<=n;++i) ins(root,read());
	int ans=0,last=0;
	while(m--){
		int opt=read(),x=read();
		x^=last;
		if(opt==1) ins(root,x); else
		if(opt==2) del(root,x); else
		if(opt==3) last=rk(root,x); else
		if(opt==4) last=fd(root,x); else
		if(opt==5) last=pre(root,x); else
		if(opt==6) last=suc(root,x); 
		if(opt>=3) ans^=last;
	}
	printf("%d\n",ans);
	return 0;
}

2022/9/25 19:40
加载中...