Luogu主席树

2017-07-30

主席树模板

题目背景 小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。 题目描述 小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。 可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间（i,j）不互相包含。 输入输出格式 输入格式： 第一行输入两个数n，m，你可以假设n<300001 并且 m<50001；m表示他喂了m次。 第二行n个整数，表示第i只狗的漂亮值为ai。 接下来m行，每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。 输出格式： M行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

主席树模板题，【阅兵ing，看主席写主席】 直接pia代码吧

#include<iostream>
#include<cstdio>
#include<algorithm>
#define TN 9000000
#define N 300001
#define M 500001
using namespace std;
int n,m;
int s[TN],ls[TN],rs[TN];
int knt,root[N],a[N],b[N];
using namespace std;
void buid(int A,int &B,int l,int r,int it)
{
	int mid=(l+r)>>1;
	B=++knt;
	s[B]=s[A]+1;
	if(l==r) return;
	if(it<=mid)	buid(ls[A],ls[B],l,mid,it);
	else buid(rs[A],rs[B],mid+1,r,it);
	if(!ls[B]) ls[B]=ls[A];
	if(!rs[B]) rs[B]=rs[A];
}
int ask(int V,int U,int l,int r,int k)
{
	if(l==r) return r;
	int mid=(l+r)>>1;
	if(s[ls[V]]-s[ls[U]]>=k) return ask(ls[V],ls[U],l,mid,k);
	else return ask(rs[V],rs[U],mid+1,r,k-s[ls[V]]+s[ls[U]]);
}
int main()
{
	scanf("%d%d",&n,&m);
	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)
	{
		int it=lower_bound(b+1,b+n+1,a[i])-b;
		buid(root[i-1],root[i],1,n,it);
	}
	for(int i=1;i<=m;++i)
	{
		int u,v,k;
		scanf("%d%d%d",&u,&v,&k);
		printf("%d\n",b[ask(root[v],root[u-1],1,n,k)]);
	}
	return 0;
}
Comment Box
(update the code to your comment plugin in comment-full.html)