P3834

Aryper · 2021-08-12 15:58:53 · 个人记录

【模板】可持久化线段树 2（主席树）

这题有多种解法。虽说是卡死要用可持久化线段树了，不过之后我还会再尝试一些诸如归并树，线段树套平衡树，以及离线分治。

法一：可持久化线段树

利用可持久化线段树可以非常巧妙地解决该题。

我们首先要转变观念，那就是要在值域上建立线段树，而非下标上建立线段树。当然，值域要先经过离散化。

原因就是，我们要将二分答案的过程融合进线段树的查找中，优化掉一个 \log 的复杂度。

然后我们建立线段树还不够，要建立一颗可持久化线段树。那么，每个历史版本到底存储了什么？修改与查询又是什么？

答案是，我们按照序列的顺序，依次向可持久化线段树中添加 a_i，然后每个历史版本 i 存储的就是添加至 a_i 的线段树版本，维护了信息 cnt，每个节点的 cnt 表示该区间（值域上）有多少 a_i。

而我们的查询，就是查询历史版本 l_i-1 与 r_i。

还记得刚才我们建立值域线段树的目的吗？没错，是为了将二分答案的过程融合进线段树查找。现在我们就可以叙述具体的方法了。

首先，我们要了解一个原理。线段树的每个版本的根记作 rt_i，那么 l_i-1，r_i 的版本的根就分别是 rt_{l_i-1}，rt_{r_i}，那么 cnt_{rt_{l_i-1}}-cnt_{rt_{r_i}} 就等于 r_i-l_i+1 。这说明了什么？这说明可持久化线段树上对应的节点，不同版本之间是具有可减性的，而且相减的结果，就代表对应值域上的数在 [l_i,r_i] 中增加了多少。

接着，我们利用该原理可知，设对应节点分别为 p，q，左儿子分别为 l(p)，l(q)，我们查询的排名为 k，则：

若 cnt_{l(p)}-cnt_{l(q)}\ge k，就说明我们要查询的值在左儿子对应的值域中；反之则在右儿子对应的值域中。

那么这样，我们就能很好的二分答案得到排名为 k 的数了。

时间复杂度 O((m+n)\log n)，空间复杂度 O(n\log n)。

然后，如果还想支持动态修改，需要在最外层套一个树状数组，但空间复杂度较高。

代码（可持久化线段树）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=2e5;

struct sgt{
    ll l,r,cnt;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define cnt(x) tree[x].cnt
}tree[N*30];

ll n,m,amt,l,r,k,tot;

ll uq[N+5],rt[N+5],a[N+5];

ll build(ll l,ll r) {
    ll p=++tot;
    if(l==r) return p;
    ll mid=(l+r)>>1;
    l(p)=build(l,mid);r(p)=build(mid+1,r);
    return p;
}

ll ins(ll cur,ll l,ll r,ll loc,ll val) {
    ll p=++tot;
    tree[p]=tree[cur];
    if(l==r) {
        cnt(p)+=val;return p;
    }
    ll mid=(l+r)>>1;
    if(loc<=mid) {
        l(p)=ins(l(cur),l,mid,loc,val);
    }
    else {
        r(p)=ins(r(cur),mid+1,r,loc,val);
    }
    cnt(p)=cnt(l(p))+cnt(r(p));
    return p;
}

ll ask(ll p,ll q,ll l,ll r,ll k) {
    if(l==r) return l;
    ll mid=(l+r)>>1;
    ll lcnt=cnt(l(p))-cnt(l(q));
    if(k<=lcnt) return ask(l(p),l(q),l,mid,k);
    else return ask(r(p),r(q),mid+1,r,k-lcnt);
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();uq[++amt]=a[i];
    }

    sort(uq+1,uq+amt+1);
    tot=unique(uq+1,uq+amt+1)-uq-1;

    rt[0]=build(1,amt);

    for(ll i=1;i<=n;i++) {
        a[i]=lower_bound(uq+1,uq+amt+1,a[i])-uq;
        rt[i]=ins(rt[i-1],1,amt,a[i],1);
    }

    for(ll i=1;i<=m;i++) {
        l=read();r=read();k=read();
        write(uq[ask(rt[r],rt[l-1],1,amt,k)]);
        putchar('\n');
    }

    return 0;
}