关于离散化的讨论
查看原帖
关于离散化的讨论
235302
wxk123楼主2023/7/18 22:41

用的权值线段树,一开始只对op==1的操作做离散化,得了92pts,改成对除了op==4之外所有操作进行离散化了之后就AC了,但是我的查找用的是二分+找第k小的方式啊,离散化不应该对答案有影响吧...qwq求解

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
const int MAXN=400020;
int R[MAXN<<5],L[MAXN<<5],b[MAXN],id=0,num[MAXN<<5],n,m,T[MAXN<<2];
int build(int l,int r){
	int now=++id;
	num[now]=0;
	if(l>=r){
		return now;
	}
	int mid=(l+r)/2;
	L[now]=build(l,mid);
	R[now]=build(mid+1,r);
	return now;
}
int update(int pre,int l,int r,int x,int	val){
	int now=++id;
	L[now]=L[pre];R[now]=R[pre];
	num[now]=num[pre]+val;
	if(l>=r)
	return now;
	int mid=(l+r)/2;
	if(mid>=x)
	L[now]=update(L[pre],l,mid,x,val);
	else
	R[now]=update(R[pre],mid+1,r,x,val);
	return now;
}
int find(int u,int v,int l,int r,int k){
	if(l>=r)
	return l;
	int hav=num[L[v]]-num[L[u]];
	int mid=(l+r)>>1;
	if(hav>=k)
	return find(L[u],L[v],l,mid,k);
	else
	return find(R[u],R[v],mid+1,r,k-hav);
}
struct	quer{
	int	op,x;
}Q[MAXN];
int main(){
	scanf("%lld",&n);
	int	x,y;
	int	cont=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&Q[i].op,&Q[i].x);
		if(Q[i].op==1||Q[i].op==2||Q[i].op==3||Q[i].op==5||Q[i].op==6)
		//if(Q[i].op==1)
		b[++cont]=Q[i].x;
	}
	int q=unique(b+1,b+1+cont)-b-1;
	T[0]=build(1,q);
	T[1]=T[0];
	sort(b+1,b+1+cont);
	int	tot=0;
	for(int i=1;i<=n;i++)
	{
	int cha,l,r;
//	cout<<i<<endl;
		switch(Q[i].op){
			case	1:
					tot++;
					cha=lower_bound(b+1,b+1+cont,Q[i].x)-b;
					T[1]=update(T[1],1,q,cha,1);
					break;
			case	2:
					tot--;
					cha=lower_bound(b+1,b+1+cont,Q[i].x)-b;
					T[1]=update(T[1],1,q,cha,-1);
					break;			
			case	3:
					l=0;r=tot;
					while(l+1<r){
					int	mid=(l+r)/2;
					if(b[find(T[0],T[1],1,q,mid)]>=Q[i].x)
					r=mid;
					else
					l=mid;
				}
					cout<<r<<endl;
					break;
			case	4:
					cout<<b[find(T[0],T[1],1,q,Q[i].x)]<<endl;
					break;
			case	5:
					l=1;	r=tot+1;
					while(l+1<r){
					int	mid=(l+r)/2;
					if(b[find(T[0],T[1],1,q,mid)]<Q[i].x)
					l=mid;
					else
					r=mid;
				}
					cout<<b[find(T[0],T[1],1,q,l)]<<endl;
					break;
			case	6:
				int	l=0;int	r=tot;
				while(l+1<r){
					int	mid=(l+r)/2;
					if(b[find(T[0],T[1],1,q,mid)]>Q[i].x)
					r=mid;
					else
					l=mid;
				}
					cout<<b[find(T[0],T[1],1,q,r)]<<endl;
					break;								
		}
	 }
} 
2023/7/18 22:41
加载中...