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

题面

https://www.luogu.org/problem/P3834

题解

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct lsh {
  int id,val;
  bool operator < (const lsh rhs) const {
    return val<rhs.val;
  }
} a[205000];

struct node {
  int lson,rson,lb,rb,val;
} tree[8500000];

int n,m,oto[205000],root[205000],cnt=1,rk;

void maketree(int x,int lb,int rb){
  tree[x].lb=lb; tree[x].rb=rb;
  if (lb==rb) return;
  int mid=(lb+rb)/2;
  tree[x].lson=cnt+1;
  maketree(++cnt,lb,mid);
  tree[x].rson=cnt+1;
  maketree(++cnt,mid+1,rb);
}

void build(int now,int pre,int loc){
  tree[now]=tree[pre];
  tree[now].val++;
  if (tree[pre].lb==tree[pre].rb) return;
  int mid=(tree[pre].lb+tree[pre].rb)/2;
  if (loc<=mid) {
    tree[now].lson=cnt+1;
    build(++cnt,tree[pre].lson,loc);
  }
  else {
    tree[now].rson=cnt+1;
    build(++cnt,tree[pre].rson,loc);
  }
}

int findbykth(int l,int r,int rank) {
  if (tree[l].lb==tree[l].rb) return a[tree[l].rb].val;
  if (tree[tree[r].lson].val-tree[tree[l].lson].val+rk>=rank) return findbykth(tree[l].lson,tree[r].lson,rank);
  else rk+=tree[tree[r].lson].val-tree[tree[l].lson].val; return findbykth(tree[l].rson,tree[r].rson,rank);
}

int main(){
  int i,l,r,k;
  scanf("%d %d",&n,&m);
  for (i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;
  sort(a+1,a+n+1); 
  for (i=1;i<=n;i++) oto[a[i].id]=i;
  root[0]=1;
  maketree(cnt,1,n);
  for (i=1;i<=n;i++) {
    root[i]=cnt+1;
    build(++cnt,root[i-1],oto[i]);
  }
  for (i=1;i<=m;i++) {
    scanf("%d %d %d",&l,&r,&k);
    rk=0;
    printf("%d\n",findbykth(root[l-1],root[r],k));
  }
  return 0;
}