CF840D Destiny(主席树)

题目地址：https://www.luogu.com.cn/problem/CF840D

这一题是一个主席树入门题，我们只需要将普通的主席树模板的查询过程进行修改即可

查询

1

现在我们面临左右两个儿子，求出左边的\(size\)和右边的\(size\)
如果左边的\(size\)比标准值\(\frac{r-l+1}{k}\)要大，那么走左边，走左边不出解再走右边，两边的\(size\)都小于等于\(\frac{r-l+1}{k}\)的话直接返回\(-1\)

2

现在我们走到了叶子节点，按照常规的思路是要返回l或r(l==r)
但是这里我们要做一下特判，只有当当前叶子节点的size大于标准值时返回l，否则返回-1

代码写出来就是这样子的：

int query(int l,int r,int x,int y,int k) {
	if(l==r) {//特判叶子节点
		if(siz[x]-siz[y]>k)return l;
		else return -1;
	}
	int t1=siz[lp[x]]-siz[lp[y]],t2=siz[rp[x]]-siz[rp[y]];
	int mid=(l+r)/2,ans=-1;
	if(t1>k)//走左边
		ans=query(l,mid,lp[x],lp[y],k);
	if(t2>k&&ans==-1)//左边走不了走右边
		ans=query(mid+1,r,rp[x],rp[y],k);
	return ans;//返回答案（如果左右都走不了返回初始值-1）
}

剩下过程和模板一样

这一题可以不用离散化

AC Code

#include
using namespace std;
int n,m,cnt=0,a[500010],b[500010],lh[500010],t1,t2,t3;
int siz[20000000],lp[20000000],rp[20000000],rt[500010];
void build(int &now,int l,int r) {
	now=++cnt;
	if(l==r)return ;
	int mid=(l+r)/2;
	build(lp[now],l,mid);
	build(rp[now],mid+1,r);
}
void add(int l,int r,int &now,int pre,int x) {
	now=++cnt;
	siz[now]=siz[pre]+1;
	lp[now]=lp[pre];
	rp[now]=rp[pre];
	int mid=(l+r)/2;
	if(l==r)return ;
	if(x<=mid)
		add(l,mid,lp[now],lp[pre],x);
	else
		add(mid+1,r,rp[now],rp[pre],x);
}
int query(int l,int r,int x,int y,int k) {
	if(l==r) {
		if(siz[x]-siz[y]>k)return l;
		else return -1;
	}
	int t1=siz[lp[x]]-siz[lp[y]],t2=siz[rp[x]]-siz[rp[y]];
	int mid=(l+r)/2,ans=-1;
	if(t1>k)
		ans=query(l,mid,lp[x],lp[y],k);
	if(t2>k&&ans==-1)
		ans=query(mid+1,r,rp[x],rp[y],k);
	return ans;
}
int main() {
	scanf("%d%d",&n,&m);
	build(rt[0],1,5e5);
	for(int i=1; i<=n; i++)scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1; i<=n; i++)
		lh[i]=lower_bound(b+1,b+n+1,a[i])-b;
	for(int i=1; i<=n; i++)add(1,5e5,rt[i],rt[i-1],lh[i]);
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d",&t1,&t2,&t3);
		int ans=query(1,5e5,rt[t2],rt[t1-1],(t2-t1+1)/t3);
		if(ans!=-1)ans=b[ans];
		printf("%d\n",ans);
	}
	return 0;
}

最后附上一道想法一样的题目：https://www.luogu.com.cn/problem/P3567(Double Experience)