主席树入门题-2018湘潭邀请赛部分题解*

（有任何问题欢迎留言或私聊

本题完全是主席树裸题，我这里简单提一下我对主席树的理解。我的题解在后面，你可以直接去看题解。
感觉我写的应该挺好理解的，只要你学了线段树，可能你不会写，但应该能有个印象。

主席树：

主席树又称可持久化线段树，数据离散化后，编号为i的节点维护的是前缀1-i这段区间的线段树。
如果用普通线段树的方法写，你要建n个线段树，时间和空间都太浪费了，于是某神人开发这意数据结构。
你会发现i号节点维护的是前缀i这段区间的线段树，而i和它左右的两个线段树只差了一个元素而已；而且每一个线段树的结构是一模一样的，不同的只是每个线段树包含的值域不同。
所以你要利用前一个线段树信息；相较于前一颗树只是多了一个值，也就只有包含这个值的log个节点不同，所以对于每一个线段树，我们只需要新开log个节点,其它的节点就用第i-1颗线段树的节点。

处理：

对于主席树，我们要开一个root数组来储存每一个线段树的根，最开始是一个空树，所以root[0]=0;而主席树的节点储存的是左右儿子的编号信息。
因为每个线段树的构造完全相同，只是所包含的值域不同；所以对于区间[L,R]这段线段树你可以由root[R]-root[L-1]得到。
注意，相邻两颗线段树只有当前待处理的元素不同，其余位置完全一样。
因此，如果待处理的元素进入线段树的左子树的话，右子树是完全一样的，可以共用，即直接让当前线段树节点的右子树指向相邻的上一棵线段树的右子树；若进入右子树，情况可以类比。
这个过程时间复杂度为O(logn)，空间复杂度为 O(logn)。

另外推荐一下：
qsc学姐的主席树算法直播课

C. Just h-index

The h-index of an author is the largest h where he has at least h papers with citations not less than h. Bobo has published n papers with citations a1,a2,…,an respectively. One day, he raises q questions. The i-th question is described by two integers li and ri, asking the h-index of Bobo if has only published papers with citations ali,ali+1,…,ari.
Input The input consists of several test cases and is terminated by end-of-le. The rst line of each test case contains two integers n and q. The second line contains n integers a1,a2,…,an. The i-th of last q lines contains two integers li and ri.
Output For each question, print an integer which denotes the answer.
Constraint 1≤ n,q ≤105 1≤ ai ≤ n 1≤ li ≤ ri ≤ n The sum of n does not exceed 250,000. The sum of q does not exceed 250,000.
Sample Input
5 3
1 5 3 2 1
1 3
2 4
1 5
5 1
1 2 3 4 5
1 5
Sample Output
2 2 2
3

题意及思路：

给你一段长度为n的序列，q次询问；每次询问[L,R]区间内的h值是多少？

h值的意思：
栗子：4 2 6 3 1；表示这区间内，1，2，3，4，6各出现了一次。h值表示大于等于h的数出现了不少于h次且h要最大。

你会发现这个题和主席树的入门题静态区间第k小十分相像；
本题要求的是最大的第k大的数出现了不少于k次。
其实就是求区间第k大问题，你可以直接求，也可以转化为求区间第k小，两种方法我都ac了。
对于最大化一个值的问题二分一下就行了。

用主席数求出第mid大的数，如果mid<=这个数，则L=mid+1;反之R=mid-1;
二分的写法大同小异，用自己习惯的写法就好。

数据量是1e5，主席树的复杂度是O(nlogn)；q次查询，主席树查询是O(log)，二分的复杂度是O(log)，所以本题复杂度是O(nlog^2)二分加主席树完全可过。

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 200005;
const int INF = 0x3f3f3f3f;
int n,q,tot;
struct lp
{
 int l,r,sum;
 lp(){l=r=sum=0;}
}cw[N*20];
int ar[N],br[N],now[N];
int root[N];
void update(int l,int r,int last,int &cur,int x){
 cw[++tot]=cw[last];
 cw[tot].sum++;
 cur=tot;
 if(l==r)return;
 int mid = (l+r)>>1;
 if(x<=mid){
  update(l,mid,cw[last].l,cw[cur].l,x);
 }else {
  update(mid+1,r,cw[last].r,cw[cur].r,x);
 }
}
int query(int l,int r,int last,int cur,int k){
 if(l==r)return l;
 int l1=cw[last].l,l2=cw[cur].l,r1=cw[last].r,r2=cw[cur].r;
 int summ=cw[l2].sum-cw[l1].sum;
 int mid=(l+r)>>1;
 if(k<=summ){
  return query(l,mid,cw[last].l,cw[cur].l,k);
 }else{
  return query(mid+1,r,cw[last].r,cw[cur].r,k-summ);
 }
}
int main(){
 while(~scanf("%d%d",&n,&q)){
  memset(root,0,sizeof(root));
  cw[0].l=cw[0].r=cw[0].sum=0;
  for(int i=1;i<=n;++i){
   scanf("%d",&br[i]);
   ar[i]=br[i];
  }
  sort(br+1,br+1+n);
  int k=1;
  for(int i=2;i<=n;++i){
   if(br[i]!=br[i-1])br[++k]=br[i];
  }
  tot=0;
  for(int i=1;i<=n;++i){
   now[i]=lower_bound(br+1,br+1+k,ar[i])-br;
  }
  for(int i=1;i<=n;++i){
   update(1,k,root[i-1],root[i],now[i]);
  }
  while(q--){
   int u,v;
   scanf("%d%d",&u,&v);
   int L=1,R=v-u+1,mid,ans=1;
   while(L<=R){//二分的写法大同小异，用自己习惯的写法
    mid=(L+R)>>1;
    int tmp=query(1,k,root[u-1],root[v],v-u+1-mid+1);
    if(mid>br[tmp]){
     ans=mid-1;
     R=mid-1;
    }else{
     ans=mid;
     L=mid+1;
    }
   }
   printf("%d\n",ans);
  }
 }
 return 0;
}

主席树板子

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000 + 5;

int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20];

int n, k, tot, sz, ql, qr, x, q, T;

void Build(int& o, int l, int r){
    o = ++ tot;
    sum[o] = 0;
    if(l == r) return;
    int m = (l + r) >> 1;
    Build(ls[o], l, m);
    Build(rs[o], m + 1, r);
}

void update(int& o, int l, int r, int last, int p){
    o = ++ tot;
    ls[o] = ls[last];
    rs[o] = rs[last];
    sum[o] = sum[last] + 1;
    if(l == r) return;
    int m = (l + r) >> 1;
    if(p <= m)  update(ls[o], l, m, ls[last], p);
    else update(rs[o], m + 1, r, rs[last], p);
}

int query(int ss, int tt, int l, int r, int k){
    if(l == r) return l;
    int m = (l + r) >> 1;
    int cnt = sum[ls[tt]] - sum[ls[ss]];
    if(k <= cnt) return query(ls[ss], ls[tt], l, m, k);
    else return query(rs[ss], rs[tt], m + 1, r, k - cnt);
}

void work(){
    scanf("%d%d%d", &ql, &qr, &x);
    int ans = query(rt[ql - 1], rt[qr], 1, sz, x);
    printf("%d\n", b[ans]);
}

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = a[i];
        sort(b + 1, b + n + 1);
        sz = unique(b + 1, b + n + 1) - (b + 1);
        tot = 0;
        Build(rt[0],1, sz);
        //for(int i = 0; i <= 4 * n; i ++)printf("%d,rt =  %d,ls =  %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]);
        for(int i = 1; i <= n; i ++)a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b;
        for(int i = 1; i <= n; i ++)update(rt[i], 1, sz, rt[i - 1], a[i]);
        for(int i = 0; i <= 5 * n; i ++)printf("%d,rt =  %d,ls =  %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]);
        while(q --)work();
    }
    return 0;
}

划分树归并树模板：点这里

分块模板：点这里

神代码

极角排序等基础计算几何模板

struct lp
{
 double x,y,rad;
 int id;
 lp(){}
 lp(double a,double b){x=a,y=b;}
 lp operator - (const lp &b) const{
        return lp(x - b.x, y - b.y);
    }
}cw[N],st,p[N];
inline double dist(lp &a,lp &b){
 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline double crossDot(lp a,lp b){
 return a.x*b.y-a.y*b.x;
}
inline double area2(lp a,lp b,lp c){
 return crossDot(b-a,c-a);
}
bool cmp2(lp a,lp b){
 lp c;
 c.x=c.y=0;
 double tmp=area2(c,a,b);
 if(tmp==0)return a.x<b.x;
 return tmp>0;
}
int Quadrant1(lp a)//象限排序，注意包含四个坐标轴
{
    if(a.x>0&&a.y>=0)  return 3;
    if(a.x<=0&&a.y>0)  return 4;
    if(a.x<0&&a.y==0)  return 4;
    if(a.x<0&&a.y<=0)  return 1;
    if(a.x>=0&&a.y<0)  return 2;
}
bool cmp5(lp &a,lp &b){
 int qa=Quadrant1(a),qb=Quadrant1(b);
 if(qa==qb){
  return cmp2(a,b);
 }
 return qa<qb;
}
double myatan(double y,double x)
{
 double t=atan2(y,x);
 return t>=0?t:2*PI+t;
}
bool cmp(lp &a,lp &b){
 return a.rad<b.rad;
}
bool Left(lp &a,lp &b){
 return (a.x*b.y-a.y*b.x)>=0;
}

struct lp
{
    double x,y,rad;
    int id;
    lp(){}
    lp(double a,double b){x=a,y=b;}
    lp operator - (const lp &b) const{
        return lp(x - b.x, y - b.y);
    }
}cw[N];
inline double crossDot(lp a,lp b){
    return a.x*b.y-a.y*b.x;
}
inline double area2(lp a,lp b,lp c){
    return crossDot(b-a,c-a);
}

bool cmp1(lp a,lp b){
    double p=atan2(a.y,a.x),q=atan2(b.y,b.x);
    if(p!=q){
        return p<q;
    }
    return a.x<b.x;
}
bool cmp2(lp a,lp b){
    lp c;
    c.x=c.y=0;
    double tmp=area2(c,a,b);
    if(tmp==0)return a.x<b.x;
    return tmp>0;
}
int Quadrant(lp a)//象限排序，注意包含四个坐标轴
{
    if(a.x>0&&a.y>=0)  return 1;
    if(a.x<=0&&a.y>0)  return 2;
    if(a.x<0&&a.y<=0)  return 3;
    if(a.x>=0&&a.y<0)  return 4;
    return -1;
}
bool cmp3(lp a,lp b){
    if(Quadrant(a)==Quadrant(b)){
        return cmp1(a,b);
    }
    return Quadrant(a)<Quadrant(b);
}

bool cmp4(const lp &a, const lp &b)//先按象限排序，再按极角排序，再按远近排序 
{
    if (a.y == 0 && b.y == 0 && a.x*b.x <= 0)return a.x>b.x;
    if (a.y == 0 && a.x >= 0 && b.y != 0)return true;
    if (b.y == 0 && b.x >= 0 && a.y != 0)return false;
    if (b.y*a.y <= 0)return a.y>b.y;
    lp one;
    one.y = one.x = 0;
    return area2(one,a,b) > 0 || (area2(one,a,b) == 0 && a.x < b.x);    
}
int Quadrant1(lp a)//象限排序，注意包含四个坐标轴
{
    if(a.x>0&&a.y>=0)  return 3;
    if(a.x<=0&&a.y>0)  return 4;
    if(a.x<0&&a.y==0)  return 4;
    if(a.x<0&&a.y<=0)  return 1;
    if(a.x>=0&&a.y<0)  return 2;
}
bool cmp5(lp &a,lp &b){
    int qa=Quadrant1(a),qb=Quadrant1(b);

    if(qa==qb){
        return cmp2(a,b);
    }
    return qa<qb;
}