题面

传送门

思路

这道题目是陈立杰论文《重量平衡树和后缀平衡树在信息学奥赛中的应用》中关于重量平衡树维护序列排名算法的一个应用

具体方法为：令根节点保存一个实数区间$[0,1]$

若当前节点是$[l,r]$，则左儿子是$[l,mid]$，右儿子是$[mid,r]$

令$f[x]=(l[x]+r[x])*0.5$，则$f$比较大小则等价于序列中的元素比较大小

此时，用重量平衡树来实现这一过程，可以做到均摊$O(\log n)$修改，$O(1)$查询两个点之间的大小关系

本题中，考虑使用一棵平衡树来维护所有位置的排名，再用一棵权值线段树统计答案，权值线段树中保存对应区间的最大的点的下标，利用上面求出的$f$值来比大小

平衡树选取替罪羊树，实现时我们维护一个$node$类，保存它的左半和右半部分（本题中数是由两个部分组成的，也就是括号序列）在平衡树中的排名

插入时按照题目给定的方式比较即可，不需要删除

Code

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cassert>

#include<vector>

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

//scapegoat

double f[600010];int root,unb;

struct node{

	int l,r;

	friend bool operator >(node x,node y){

		if(f[x.l]>f[y.l]) return 1;

		if(f[x.l]==f[y.l]&&f[x.r]>f[y.r]) return 1;

		return 0;

	}

	friend bool operator ==(node x,node y){

		return (f[x.l]==f[y.l])&&(f[x.r]==f[y.r]);

	}

};

namespace scp{

	node a[600010];

	int siz[600010],key[600010][2],ch[600010][2],pos[600010],cntn;

	void update(int x){

		siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;

	}

	vector<int>str;

	void dfs(int u){

		if(!u) return;

		dfs(ch[u][0]);

		str.push_back(u);

		dfs(ch[u][1]);

	}

	void build(int &cur,int l,int r,double ql,double qr){

		if(l>r){cur=0;return;}

		int mid=(l+r)>>1;double md=(ql+qr)*0.5;

		cur=str[mid];

		f[cur]=md;

		build(ch[cur][0],l,mid-1,ql,md);

		build(ch[cur][1],mid+1,r,md,qr);

		update(cur);

	}

	void rebuild(int &u,double l,double r){

		str.clear();

		dfs(u);

		build(u,0,str.size()-1,l,r);

	}

	double alpha=0.75;int cho;

	int insert(int &cur,node val,double ql,double qr){

		double mid=(ql+qr)*0.5;

		if(!cur){

			cur=++cntn;f[cur]=mid;a[cur]=val;siz[cur]=1;

			return cur;

		}

		int p;

		if(val==a[cur]){p=cur;return p;}

		else{

			siz[cur]++;

			if(val>a[cur]) p=insert(ch[cur][1],val,mid,qr);

			else p=insert(ch[cur][0],val,ql,mid);

		}

		if((double)(siz[cur]*0.75)>(double)(max(siz[ch[cur][0]],siz[ch[cur][1]]))){

			if(unb){

				if(ch[cur][0]==unb) rebuild(ch[cur][0],ql,mid);

				else rebuild(ch[cur][1],mid,qr);

				unb=0;

			}

		}

		else unb=cur;

		return p;

	}

}

int maxn[1000010],pos[1000010];

void change(int l,int r,int p,int cur){

	int mid=(l+r)>>1;

	if(l==r){maxn[p]=l;return;}

	if(mid>=cur) change(l,mid,p<<1,cur);

	else change(mid+1,r,p<<1|1,cur);

	if(f[pos[maxn[p<<1]]]>=f[pos[maxn[p<<1|1]]]) maxn[p]=maxn[p<<1];

	else maxn[p]=maxn[p<<1|1];

}

int query(int l,int r,int ql,int qr,int num){

	if(l>=ql&&r<=qr) return maxn[num];

	int mid=(l+r)>>1,re,re1;

	if(mid>=qr) return query(l,mid,ql,qr,num<<1);

	else if(mid<ql) return query(mid+1,r,ql,qr,num<<1|1);

	else{

		re=query(l,mid,ql,mid,num<<1);

		re1=query(mid+1,r,mid+1,qr,num<<1|1);

		if(f[pos[re]]>=f[pos[re1]]) return re;

		else return re1;

	}

}

int n,Q;

int main(){

	n=read();Q=read();int i,t1,t2,t3;char s[10];

	scp::insert(root,(node){0,0},0,1);f[0]=-1;

	for(i=1;i<=n;i++) pos[i]=1;

	for(i=1;i<=n;i++) change(1,n,1,i);

	while(Q--){

		scanf("%s",s);

		t1=read();t2=read();

		if(s[0]=='C'){

			t3=read();unb=0;

			pos[t3]=scp::insert(root,(node){pos[t1],pos[t2]},0,1);

			if(unb) scp::rebuild(root,0,1);

			change(1,n,1,t3);

		}

		else printf("%d\n",query(1,n,t1,t2,1));

	}

}

巴特西

[BZOJ3600] 没有人的算术 [重量平衡树+权值线段树]

题面

思路

Code

最新文章

热门文章