luogup3834（主席树模板）

给定由N个正整数构成的序列，将对于指定的闭区间查询m次其区间内第k小值。1≤N,M≤2e5。

有一个做法，是对于每个序列的前缀建一颗权值线段树，然后通过权值线段树相减得到的权值线段树来查询第k小值。由于单点修改只需要改动logn个结点，第i个主席树可以依托第i-1个存在。具体的做法是将路径上的点从上到下依次克隆一遍。时间复杂度和空间复杂度都是nlogn。

#include <cctype>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=2e5+5, maxstree=maxn*60;

struct node{

    int l, r, x;

}stree[maxstree];

//a：离散化后的序列 b：离散化的数对应的值

int n, m, a[maxn], b[maxn], cntu;

//cntnode：主席树一共有几个结点

int cntnode=1, root[maxn];  //root：第i棵线段树的根的位置

//在主席树的当前区间[l, r)中插入值为v的结点

//now位置的结点会被拷贝一份生成新的结点

void insert(int &now, int l, int r, int v){

    stree[cntnode]=stree[now]; now=cntnode;  //（此处一举两得，既更新了父节点的孩子编号，又把操作转到了被复制的节点）

    ++stree[cntnode++].x;

    if (l==r-1) return;

    int mid=(l+r)>>1;

    if (v<mid) insert(stree[now].l, l, mid, v);

    else insert(stree[now].r, mid, r, v);

}

//在区间[l, r)中，定位第k大数

int query(int now1, int now2, int l, int r, int k){

    if (l==r-1) return l;

    int t=stree[stree[now2].l].x-stree[stree[now1].l].x, mid=(l+r)>>1;

    if (k<=t) return query(stree[now1].l, stree[now2].l, l, mid, k);

    else return query(stree[now1].r, stree[now2].r, mid, r, k-t);

}

inline void get(int &x){

    char c; int flag=1;

    for (; c=getchar(), !isdigit(c); )

        if (c=='-') flag=-1;

    for (x=c-48; c=getchar(), isdigit(c); )

        x=(x<<3)+(x<<1)+c-48; x*=flag;

}

int main(){

    get(n); get(m);

    for (int i=0; i<n; ++i){ get(a[i]); b[i]=a[i]; }

    sort(b, b+n); cntu=unique(b, b+n)-b;

    for (int i=0; i<n; ++i) a[i]=lower_bound(b, b+cntu, a[i])-b;

    for (int i=0; i<n; ++i){ root[i+1]=root[i]; insert(root[i+1], 0, n, a[i]); }

    int t1, t2, t3;

    while (m--){

        get(t1); get(t2); get(t3);

        printf("%d\n", b[query(root[t1-1], root[t2], 0, n, t3)]);

    }

    return 0;

}

巴特西

luogup3834（主席树模板）

luogup3834（主席树模板）

最新文章

热门文章