先膜拜一下初三大爷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)]);
}
}
。我们可以用类似于拓扑排序的方法来计算这个权值。先把所有度为1的点放入队列中，令他们的权值都为1。然后一层一层往上搜，每次发现当前的这个点度变为1时，就计算一下他的权值，把他儿子（注意：这里的儿子是有限制的：已经算好权值且和他不在同一层）的权值从小到大排个序，然后第一个数乘以A1，第二个数乘以A2，…，第n个数乘以An，A为自己定一个质数，然后加起来取模一个P就好了。至此，此题就顺利解决了。
