Chrysanthemum's Blog

先膜拜一下初三大爷zyd，毕竟是他的点拨，再膜拜一下即将摘金牌的lyz大爷，毕竟也有他的帮助。

好了，现在开始讲主席树。听说这东西很多别名，比如，可持久化线段树，函数式版本的线段树……他的主要思想就是存许多棵线段树，存的是一段数字区间出现次数。

对于每个前缀1...i，我们建一棵线段树Ti，存的是数字区间出现的次数。但这会MLE，然后我们又可以发现，Ti与Ti-1两棵线段树就相差了i这个点的值，所以只改变了logn个点，因此，Ti只要在Ti-1的基础上在最多建logn个，其他的直接指向Ti-1上的点就可以了，这样就解决了内存的问题，因此，主席树成功建完。

现在要用主席树来解决实际问题啦

一个经典问题是给你n个数，每次询问区间l-r第k大值。

假设我们现在已经离线处理好所有的线段树，我们只要在Tr与Tl-1两棵树上解决这个问题，我们令root[i]为Ti的根节点编号，令p1为当前在Tl-1上的节点编号，p2为当前在Tr上的节点编号，由于任意两棵线段树的大小形态都是完全一样的，因此p1，p2表示的数字区间是完全一样。我们令tr[p].sum为编号为p的数字区间出现次数，tr[p].l为p的左儿子的编号，tr[p].r为p的右儿子的节点编号。如果num[tr[p2].l]-num[tr[p1].l]>=k那么第k大数在左儿子的区间里，那么就往左儿子递归找第k大，否则就往右儿子递归找第（k-num[tr[p2].l]+num[tr[p1].l]）大（因为要把左儿子的次数减掉）。因此这个经典问题就在nlogn的复杂度里完美解决了。

最后附上这个题的代码。 

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,cnt,a[100010],b[100010],root[100010],n1,x,y,k;
struct node{int l,r,sum;}tr[400010];
void change(int l,int r,int &p,int x)
{
	tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
	if (l==r) return;
	int mid=(l+r)>>1;
	if (x<=mid) change(l,mid,tr[p].l,x);else change(mid+1,r,tr[p].r,x); 
}
int ask(int p1,int p2,int l,int r,int k)
{
	if (l==r) return l;
	int t=tr[tr[p2].l].sum-tr[tr[p1].l].sum;
	int mid=(l+r)>>1;
	if (t>=k) return ask(tr[p1].l,tr[p2].l,l,mid,k);else return ask(tr[p1].r,tr[p2].r,mid+1,r,k-t);
}
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);
	n1=unique(b+1,b+n+1)-b-1;
	for (int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n1+1,a[i])-b;//离散化
	for (int i=1;i<=n;i++){root[i]=root[i-1];change(1,n,root[i],a[i]);} //构建主席树
	while (m--)
	{
		scanf("%d%d%d",&x,&y,&k);
		printf("%d\n",b[ask(root[x-1],root[y],1,n,k)]);
	}
}