可持久化线段树
- 节点的
l,r不再存边界而是用来存编号，查询和更改时边界作为参数下传 - 由于线段树是一段的，每次修改的那一段在原版本都必定存在，因此可以直接将信息复制过来，只需要将要修改的点所在的区间(
l,r其中一个)赋值一个新节点即可(即l,r总是一个变一个不变) - 因此每次修改只会增加
logn个节点 - 缺点：由于有多个版本，懒标记很难下传
给定一个序列，每次操作询问l,r内的第k大数
- 离散化按值建树
- 从左到右插入一个新值，建新版本
- 每次询问
[l,r]可以发现利用前缀和的思想,当前值域中，[l,r]的数量为版本r的数量-版本l-1的数量，因此可以两个版本同时下传计算
cpp
struct Node{
int l,r,cnt;
} t[N<<5];
int idx;
vector<int> nums;
int find(int x){
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
void pushup(int p){
t[p].cnt=t[t[p].l].cnt+t[t[p].r].cnt;
}
int build(int l,int r){
int p=++idx;
if(l==r)return p;
int mid=l+r>>1;
t[p].l=build(l,mid),t[p].r=build(mid+1,r);
pushup(p);
return p;
}
int insert(int p,int l,int r,int x){
int q=++idx;
t[q]=t[p];
if(l==r){
t[q].cnt++;
return q;
}
int mid=l+r>>1;
if(x<=mid)t[q].l=insert(t[p].l,l,mid,x);
else t[q].r=insert(t[p].r,mid+1,r,x);
pushup(q);
return q;
}
int query(int p,int q,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
int cnt=t[t[q].l].cnt-t[t[p].l].cnt;
if(k<=cnt)return query(t[p].l,t[q].l,l,mid,k);
return query(t[p].r,t[q].r,mid+1,r,k-cnt);
}
int n,m,a[N],root[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
nums.push_back(a[i]);
}
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
root[0]=build(0,nums.size()-1);
for(int i=1;i<=n;i++){
root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
}
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<nums[query(root[l-1],root[r],0,nums.size()-1,k)]<<"\n";
}
}