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

POOPE

板子。。。。
题意：给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。
这个空间。。50倍。。。。
每次新开节点，与原来节点公用左右儿子(随便认儿子，然后在更新维护)

#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;
#define nmr 205050
#define olinr return
#define love_nmr 0
int n;
int m;
int p;
int len;
int cnt;
int rt[nmr];
int ls[nmr<<5];
int rs[nmr<<5];
int num[nmr<<5];
int a[nmr];
int b[nmr];
inline int read()
{
  char ch=getchar();
  int f=1,x=0;
  while(!isdigit(ch))
  {
    if(ch=='-')
      f=-f;
    ch=getchar();
  }  
  while(isdigit(ch))
  {
    x=(x<<1)+(x<<3)+(ch^48);
    ch=getchar();
  }
  return x*f;
}
inline void put(int x)
{
  if(x<0)
  {
    putchar('-');
    x=-x;
  }
  if(x>9)
    put(x/10);
  putchar(x%10+'0');
}
inline void build(int &o,int l,int r)
{
  o=++cnt;
  if(l==r) olinr;
  int mid=(l+r)>>1;
  build(ls[o],l,mid);
  build(rs[o],mid+1,r);
}
inline int add(int o,int l,int r)
{
  int root=++cnt;
  ls[root]=ls[o];
  rs[root]=rs[o];
  num[root]=num[o]+1;
  if(l==r) olinr root;
  int mid=(l+r)>>1;
  if(p<=mid) ls[root]=add(ls[root],l,mid);
  if(p>mid) rs[root]=add(rs[root],mid+1,r);
  olinr root;
}
inline int query(int l,int r,int x,int y,int k)
{
  int ans=0;
  int pos=num[ls[y]]-num[ls[x]];
  if(l==r) olinr l;
  int mid=(l+r)>>1;
  if(k<=pos) ans=query(l,mid,ls[x],ls[y],k);
  if(k>pos) ans=query(mid+1,r,rs[x],rs[y],k-pos);
  return ans;
}
int main()
{
  n=read();
  m=read();
  for(int i=1;i<=n;i++)  
    b[i]=a[i]=read();
  sort(b+1,b+n+1);
  len=unique(b+1,b+n+1)-b-1;
  build(rt[0],1,len);
  for(int i=1;i<=n;i++)
  {
    p=lower_bound(b+1,b+len+1,a[i])-b;
    rt[i]=add(rt[i-1],1,len);
  }
  while(m--)
  {
    int l=read();
    int r=read();
    int k=read();
    put(b[query(1,len,rt[l-1],rt[r],k)]);
    putchar('\n');
  }
  olinr love_nmr;
}

----olinr