一些知识
主席树，原名可持久化线段树，发明人黄嘉泰（hjt），其姓名拼音缩写和我国的一位曾任国家主席的人的姓名拼音缩写相同，故得名。
主要思想：主席树是利用函数式的编程思想使得线段树支持查询历史版本，同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构。
对于原序列的每一个前缀 建立出一棵线段树维护值域上每个数出现的次数，则其树是可减的。主席树的每个节点保存的是一棵线段树，维护的区间信息，结构相同，因此具有可加减性（关键）。
模板
模板题 P3834 【模板】可持久化线段树 2（主席树）。静态区间第 小。
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=1000000+10;
int n,m,a[N],rnk[N],root[N],cnt=0,end;
struct SGT
{
struct node{int lson,rson,size;}t[N*30];
#define mid ((l+r)/2)
int clone(int pos)//继承上一个历史版本节点，再更新本次历史版本的信息
{
t[++cnt]=t[pos];
t[cnt].size++;//树节点维护元素个数
return cnt;
}
int build(int root,int l,int r)
{
root=++cnt;
if(l==r) return root;
t[root].lson=build(t[root].lson,l,mid);
t[root].rson=build(t[root].rson,mid+1,r);
return root;
}
int update(int pre,int l,int r,int pos)
{
int root=clone(pre);
if(l==r) return root;
if(pos<=mid) t[root].lson=update(t[root].lson,l,mid,pos);
else t[root].rson=update(t[root].rson,mid+1,r,pos);
return root;
}
int query(int x,int y,int l,int r,int rnk)
{
if(l==r) return l;
int Lsize=t[t[y].lson].size-t[t[x].lson].size;
/* 注意 [l,r] 本身就是位次，是 rnk 数组上的实际位次。
x 的左儿子和 y 的左儿子管理的区间是完全相同的，都是位次 [l,mid]。
如果 x y 都是根节点，rnk 则是 a 数组区间 [x,y] 内的排名。
x 和 y 总是一起行动，如果 Lsize>=rnk 说明此时 a 数组区间数字中，
位次小于等于 mid 的数量都大于 rnk 个，a 数组区间数字的第 rnk 小的位次，
必然小于 mid，需要访问左儿子。 */
if(rnk<=Lsize) return query(t[x].lson,t[y].lson,l,mid,rnk);
else return query(t[x].rson,t[y].rson,mid+1,r,rnk-Lsize);
}
}Tree;
void yzmain()
{
int t1,t2,t3;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
rnk[i]=a[i];
}
sort(rnk+1,rnk+1+n);
end=unique(rnk+1,rnk+1+n)-(rnk+1);//离散化
root[0]=Tree.build(root[0],1,end);//建初始版本树
for(int i=1;i<=n;i++)//建各历史版本树
{
int t1=lower_bound(rnk+1,rnk+1+end,a[i])-rnk;
//对于元素单调上升的数列
//lower_bound：返回第一个大于等于给定数的位置。
//upper_bound：返回第一个大于给定数的位置。
root[i]=Tree.update(root[i-1],1,end,t1);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
t3=Tree.query(root[t1-1],root[t2],1,end,t3);
printf("%d\n",rnk[t3]);//注意输出对象
}
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
首先我们要将所有数字离散化。对原数组 a，通过去重排序的到 b[1...end]，以此得到每个数值的值和位次之间的关系。
主席树相当于是在每个位置维护了一个线段树，管理区间是位次 。
线段树的节点是一个区间 ，这里的 和 都是离散后数的位次。主席树节点中维护的值，是 之间这个区间内出现了数的次数，通过历史版本保留历史权值变化。相邻历史版本间的节点，都共享一个儿子，所以我们动态开辟新版本的节点时，先继承上一个历史版本的节点信息，再按照需求修改其中一个儿子。
然后当我们查询的时候，就是利用到了前缀和的思想。如果查询 ，对比第 版本的线段树和第 版本的线段树，寻找到 第 小，对应在 rnk 数组中第几小，从而实现查询。
P3567 [POI2014]KUR-Couriers
题意
给一个长度为 的正整数序列 。共有 组询问，每次询问一个区间 ，是否存在一个数在 中出现的次数严格大于一半。如果存在，输出这个数，否则输出 。
，。
点击查看题解
题解
易知， 上如果存在一个数字，其个数超过一半，即 ，则这个数字要么是唯一的，要么不存在。实际上对应主席树上叶子节点 大于等于区间长度的一半。
因为总是寻找管理区间 大于等于一半的节点，所以会在 区间长度的次数内找到这个点，如果到不了叶子就输出 。
代码
#include<bits/stdc++.h>
using namespace std;
namespace _FullMarks
{
const int N=1000000+10;
int n,m,rnk[N],root[N],cnt=0;
struct SGT
{
struct node{int lson,rson,size;}t[N*30];
#define mid ((l+r)/2)
int clone(int pos)
{
t[++cnt]=t[pos];
t[cnt].size++;
return cnt;
}
int build(int root,int l,int r)
{
root=++cnt;
if(l==r) return root;
t[root].lson=build(t[root].lson,l,mid);
t[root].rson=build(t[root].rson,mid+1,r);
return root;
}
int update(int pre,int l,int r,int pos)
{
int root=clone(pre);
if(l==r) return root;
if(pos<=mid) t[root].lson=update(t[root].lson,l,mid,pos);
else t[root].rson=update(t[root].rson,mid+1,r,pos);
return root;
}
int query(int x,int y,int l,int r,int size)
{
if(l==r) return l;
int Lsize=t[t[y].lson].size-t[t[x].lson].size;
int Rsize=t[t[y].rson].size-t[t[x].rson].size;
if(size<Lsize) return query(t[x].lson,t[y].lson,l,mid,size);
else if(size<Rsize) return query(t[x].rson,t[y].rson,mid+1,r,size);
else return 0;
}
}Tree;
void yzmain()
{
int t1,t2;
scanf("%d%d",&n,&m);
root[0]=Tree.build(root[0],1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&t1);
root[i]=Tree.update(root[i-1],1,n,t1);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
t2=Tree.query(root[t1-1],root[t2],1,n,(t2-t1+1)/2);
printf("%d\n",t2);
}
return;
}
}
int main()
{
_FullMarks::yzmain();
return 0;
}
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/be4dde0f66a1/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
