数据结构：主席树

BZOJ3524

这道题是BZOJ的权限题，我去vijos的newbzoj上面交了一次，但是可能是他们的数据出毛病了

这道题应该算是裸的主席树的板子，一般情况下，主席树是不允许修改的，如果主席树可以支持修改那么就变成了树套树之树状数组套主席树的问题了

为了熟悉树套树我先来熟悉了一下这个问题

只有查询，没有修改

int n,m,sz;
int root[500005],lch[1000005],rch[1000005],sum[1000005];

这里sz是线段树的节点个数，root是一个数对应的子线段树的根？（这种说法可能不太严谨）

这里的线段树应该是权值线段树了，所以sum里存的就是相当于平衡树中size的东西

void update(int l,int r,int x,int &y,int v)
{
    y=++sz;
    sum[y]=sum[x]+1;
    if(l==r) return;
    lch[y]=lch[x];rch[y]=rch[x];
    int mid=(l+r)>>1;
    if(v<=mid) update(l,mid,lch[x],lch[y],v);
    else update(mid+1,r,rch[x],rch[y],v);
}

这个函数每个元素都对应调用了一次，这就是构建主席树的过程了

这里x存的是上一个元素的线段树根，看来是把他们耦合在一起了

接下来是查询;

int que(int L,int R)
{
    int l=1,r=n,mid,x,y,tmp=(R-L+1)>>1;
    x=root[L-1];y=root[R];
    while(l!=r)
    {
        if(sum[y]-sum[x]<=tmp) return 0;
        mid=(l+r)>>1;
        if(sum[lch[y]]-sum[lch[x]]>tmp)
        {
            r=mid;x=lch[x];y=lch[y];
        }
        else if(sum[rch[y]]-sum[rch[x]]>tmp)
        {
            l=mid+1;x=rch[x];y=rch[y];
        }
        else return 0;
    }
    return l;
}

题目要求的是查第（R-L+1）大的数是多少，这里的tmp我们如果赋值成别的，就应该是第k大是多少了

然后给出完整的实现：

 1 #include<cstdio>
 2 int n,m,sz;
 3 int root[500005],lch[1000005],rch[1000005],sum[1000005];
 4 inline int read()
 5 {
 6     char ch=getchar();
 7     while(!(ch>='0'&&ch<='9')) ch=getchar();
 8     int x=0;
 9     while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
10     return x;
11 }
12 void update(int l,int r,int x,int &y,int v)
13 {
14     y=++sz;
15     sum[y]=sum[x]+1;
16     if(l==r) return;
17     lch[y]=lch[x];rch[y]=rch[x];
18     int mid=(l+r)>>1;
19     if(v<=mid) update(l,mid,lch[x],lch[y],v);
20     else update(mid+1,r,rch[x],rch[y],v);
21 }
22 int que(int L,int R)
23 {
24     int l=1,r=n,mid,x,y,tmp=(R-L+1)>>1;
25     x=root[L-1];y=root[R];
26     while(l!=r)
27     {
28         if(sum[y]-sum[x]<=tmp) return 0;
29         mid=(l+r)>>1;
30         if(sum[lch[y]]-sum[lch[x]]>tmp)
31         {
32             r=mid;x=lch[x];y=lch[y];
33         }
34         else if(sum[rch[y]]-sum[rch[x]]>tmp)
35         {
36             l=mid+1;x=rch[x];y=rch[y];
37         }
38         else return 0;
39     }
40     return l;
41 }
42 int main()
43 {
44     n=read();m=read();
45     for(int i=1;i<=n;i++)
46     {
47         int x;x=read();
48         update(1,n,root[i-1],root[i],x);
49     }
50     for(int i=1;i<=m;i++)
51     {
52         int l,r;l=read();r=read();
53         printf("%d
",que(l,r));
54     }
55     return 0;
56 }

其实我觉得这种高级的数据结构，板子的重要性要大于完全融会贯通会修改

至少现阶段我是这么认为的，可能是菜吧