P3834 【模板】可持久化线段树 1（主席树）
板子。。。。题意：给定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;
int ls;
int rs;
int num;
int a;
int b;
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,l,mid);
build(rs,mid+1,r);
}
inline int add(int o,int l,int r)
{
int root=++cnt;
ls=ls;
rs=rs;
num=num+1;
if(l==r) olinr root;
int mid=(l+r)>>1;
if(p<=mid) ls=add(ls,l,mid);
if(p>mid) rs=add(rs,mid+1,r);
olinr root;
}
inline int query(int l,int r,int x,int y,int k)
{
int ans=0;
int pos=num]-num];
if(l==r) olinr l;
int mid=(l+r)>>1;
if(k<=pos) ans=query(l,mid,ls,ls,k);
if(k>pos) ans=query(mid+1,r,rs,rs,k-pos);
return ans;
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
b=a=read();
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;
build(rt,1,len);
for(int i=1;i<=n;i++)
{
p=lower_bound(b+1,b+len+1,a)-b;
rt=add(rt,1,len);
}
while(m--)
{
int l=read();
int r=read();
int k=read();
put(b,rt,k)]);
putchar('\n');
}
olinr love_nmr;
}
----olinr
文档来源：51CTO技术博客https://blog.51cto.com/u_15314204/3190980
页:
[1]