权值树MLE58分求调玄关
查看原帖
权值树MLE58分求调玄关
1062499
粥2414楼主2025/1/7 18:27

c数组原来开的30*N,然后炸了以为开大了,结果改成N还是MLE

#include<bits/stdc++.h>
#define ll int
#define dd double
#define lson c[id].ls
#define rson c[id].rs
#define mid ((l+r)/2)
using namespace std;
inline ll read(){
	ll 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*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
const ll N=1e5+9;
ll n;
ll sum;
struct NODE{
	ll ls,rs;
	ll cnt;
}c[N];
void pu(ll id){
	c[id].cnt=c[lson].cnt+c[rson].cnt;
}
void change(int &id,int l,int r,int x,short v){
	if(!id){
		id=++sum;
	}
	if(l==r){
		c[id].cnt+=v;
		return;
	}
	if(x<=mid){
		change(lson,l,mid,x,v);
	}
	else{
		change(rson,mid+1,r,x,v);
	}
	pu(id);
}
ll pai(int id,int l,int r,ll ql,ll qr){
	if(ql<=l&&r<=qr){
		return c[id].cnt;
	}
	ll ans=0;
	if(ql<=mid){
		if(id==1){
		}
		ans+=pai(lson,l,mid,ql,qr);
	}
	if(qr>mid){
		ans+=pai(rson,mid+1,r,ql,qr);
	}
	return ans;
}
ll vi(ll id,ll l,ll r,ll x){//第x大的数的值
	if(l==r){
		return l;
	}
	if(x<=c[lson].cnt){
		return vi(lson,l,mid,x);
	}
	else{
		return vi(rson,mid+1,r,x-c[lson].cnt);
	}
}
int main(){
	n=read();
	ll kkk=0;
	for(int i=1;i<=n;i++){
		ll opt=read(),x=read();
		if(opt==1){
			change(kkk,-1e7,1e7,x,1);
		}
		if(opt==2){
			change(kkk,-1e7,1e7,x,-1);
		}
		if(opt==3){
			write(pai(1,-1e7,1e7,-1e7,x-1)+1);
			putchar('\n');
		}
		if(opt==4){
			write(vi(1,-1e7,1e7,x));
			putchar('\n');
		}
		if(opt==5){
			ll lh=pai(1,-1e7,1e7,-1e7,x-1);
			write(vi(1,-1e7,1e7,lh));
			putchar('\n');
		}
		if(opt==6){
			ll lh=pai(1,-1e7,1e7,-1e7,x)+1;
			write(vi(1,-1e7,1e7,lh));
			putchar('\n');
		}
	}

	return 0;
}
2025/1/7 18:27
加载中...