主席树当然是很厉害的呀
【BZOJ 1901】 Zju2112 Dynamic Rankings
各种线段树https://wenku.baidu.com/view/a79e05ff941ea76e58fa046b.html
突然明白了主席树是什么鬼东西，网上博客看了一大堆看懵逼了。
http://blog.csdn.net/column/details/persistence-ds.html
离线的主席树 【POJ 2104】K-th Number
非递归版本
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN=100000+100;
const int MAXM=MAXN*20;
int tot,n,m;
int da[MAXN],sDa[MAXN];
int leftChild[MAXM],rightChild[MAXM],wei[MAXM],chairTNode[MAXM*20];
/**********************************
*参数：待处理元素区间
*功能：建立一棵空线段树
*返回值：返回根节点下标
***********************************/
int Build(int left,int right)
{
int id=tot++;
wei[id]=0;
if(left<right)
{
int mid=(left+right)>>1;
leftChild[id]=Build(left,mid);
rightChild[id]=Build(mid+1,right);
}
return id;
}
int Update(int root,int pos,int val)
{
int l=1,r=m,mid,newRoot=tot++,retRoot=newRoot;
wei[newRoot]=wei[root]+val;
while(l<r)
{
mid=(l+r)>>1;
if(pos<=mid)
{
//确定节点孩子节点
leftChild[newRoot]=tot++;
rightChild[newRoot]=rightChild[root];
//确定待跟新节点以及历史版本
newRoot=leftChild[newRoot];
root=leftChild[root];
r=mid;
}
else
{
rightChild[newRoot]=tot++;
leftChild[newRoot]=leftChild[root];
newRoot=rightChild[newRoot];
root=rightChild[root];
l=mid+1;
}
wei[newRoot]=wei[root]+val;
}
return retRoot;
}
int Query(int leftRoot,int rightRoot,int k)
{
int l=1,r=m,mid;
while(l<r)
{
mid=(l+r)>>1;
if(wei[leftChild[leftRoot]]-wei[leftChild[rightRoot]]>=k)//第k小值在左子树
{
//确定查找新区间
leftRoot=leftChild[leftRoot];
rightRoot=leftChild[rightRoot];
r=mid;
}
else
{
k-=wei[leftChild[leftRoot]]-wei[leftChild[rightRoot]];
leftRoot=rightChild[leftRoot];
rightRoot=rightChild[rightRoot];
l=mid+1;
}
}
return l;
}
int main()
{
int q,i;
int ql,qr,k;
while(scanf("%d%d",&n,&q)!=EOF)
{
m=0;
tot=0;
for(i=1;i<=n;i++)
{
scanf("%d",&da[i]);
sDa[i]=da[i];
}
sort(sDa+1,sDa+n+1);
m=unique(sDa+1,sDa+1+n)-sDa-1;
chairTNode[n+1]=Build(1,m);
cout<<chairTNode[n+1]<<endl;
//cout<<"**********"<<endl;
printf("tot = %d\n",tot);
for(i=n;i>=1;i--) // 建n棵线段树
{
int pos=lower_bound(sDa+1,sDa+1+m,da[i])-sDa;
printf("pos = %d\n",pos);
chairTNode[i]=Update(chairTNode[i+1],pos,1);
printf("tot = %d\n",tot);
}
while(q--)
{
scanf("%d%d%d",&ql,&qr,&k);
printf("%d\n",sDa[Query(chairTNode[ql],chairTNode[qr+1],k)]);
}
printf("tot = %d\n",tot);
}
system("pause");
return 0;
}
递归版本
#define lson l, m
#define rson m+1, r
const int N=1e5+5;
int L[N<<5], R[N<<5], sum[N<<5];
int tot;
int a[N], T[N], Hash[N];
int build(int l, int r)
{
int rt=(++tot);
sum[rt]=0;
if(l<r)
{
int m=(l+r)>>1;
L[rt]=build(lson);
R[rt]=build(rson);
}
return rt;
}
int update(int pre, int l, int r, int x)
{
int rt=(++tot);
L[rt]=L[pre], R[rt]=R[pre], sum[rt]=sum[pre]+1;
if(l<r)
{
int m=(l+r)>>1;
if(x<=m)
L[rt]=update(L[pre], lson, x);
else
R[rt]=update(R[pre], rson, x);
}
return rt;
}
int query(int u, int v, int l, int r, int k)
{
if(l>=r)
return l;
int m=(l+r)>>1;
int num=sum[L[v]]-sum[L[u]];
if(num>=k)
return query(L[u], L[v], lson, k);
else
return query(R[u], R[v], rson, k-num);
}
int main()
{
// int t;
// scanf("%d", &t);
// while(t--)
// {
tot=0;
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
{
scanf("%d", &a[i]);
Hash[i]=a[i];
}
sort(Hash+1, Hash+n+1);
int d=unique(Hash+1, Hash+n+1)-Hash-1;
T[0]=build(1, d);
for(int i=1; i<=n; i++)
{
int x=lower_bound(Hash+1, Hash+d+1, a[i])-Hash;
T[i]=update(T[i-1], 1, d, x);
}
while(m--)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int x=query(T[l-1], T[r], 1, d, k);
printf("%d\n", Hash[x]);
}
// }
}
image.png
差不多知道主席树这个鬼东西的原理了。
把我的ppt上的图片，结合递归版本的代码看一下，应该很容易就理解了
image.png
image.png
image.png
image.png
