题解
#include <bits/stdc++.h>
using namespace std;
const int mxn = 18e6+7 ;
#define ll long long
#define eps 1e-5
#define open freopen("input.in","r",stdin);freopen("output.in","w",stdout);
int rd(){
int x = 1, y = 0 ; char c = getchar();
while(!isdigit(c)) {if(c=='-') x = -1 ; c = getchar();}
while(isdigit(c)) {y = (y<<1) + (y<<3) + (c^48);c = getchar();}
return x*y;
}
int n,m,t,k,ans,cnt,p;
int si;/// 节点个数
int a[mxn] , b[mxn] ,id[mxn] , sum[mxn] , lc[mxn] , rc[mxn] , val[mxn];
////数据，离散数据，每颗线段树根节点编号 ，节点权值,记录左右子节点
void build(int &x,int l,int r)
{
x = ++si ; ///增加节点
if(l==r){ val[x] = a[l] ; return ;}
int mid = (l+r)>>1;
build(lc[x],l,mid); build(rc[x],mid+1,r);
}
void update(int &x,int pre,int l,int r,int loc,int value)
{
x = ++si;
lc[x] = lc[pre] , rc[x] = rc[pre] , val[x] = val[pre] ;
if(l==r) {val[x]=value;return;}
int mid = (l+r)>>1;
if(loc<=mid) update(lc[x],lc[pre],l,mid,loc,value);
else update(rc[x],rc[pre],mid+1,r,loc,value);
}
int query(int &x,int l,int r,int loc)
{
if(l==r) return val[x];
int mid = (l+r)>>1;
if(loc<=mid) return query(lc[x],l,mid,loc);
else return query(rc[x],mid+1,r,loc);
}
void solve()
{
n = rd() , m = rd() ;
for(int i=1;i<=n;i++) a[i] = rd();
build(id[0],1,n);
for(int i=1;i<=m;i++){
int v = rd() , op = rd() , loc = rd() ;
if(op==1){
int value = rd();
update(id[i],id[v],1,n,loc,value);
} else {
printf("%d\n",query(id[v],1,n,loc));
id[i] = id[v] ;
}
}
}
int main()
{
/// open
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
题解：
#include <bits/stdc++.h>
const int mxn = 5e6+7 ;
using namespace std;
typedef long long ll;
int p,t,n,m, si , a[mxn] , b[mxn] , id[mxn] , lc[mxn] , rc[mxn] ,sum[mxn];
bool ans[mxn];
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
void build(int &x,int l,int r)
{
x = ++si ; sum[x] = 0 ;
if(l==r) return;
int mid = (l+r)>>1;
build(lc[x],l,mid); build(rc[x],mid+1,r);
}
int update(int x,int l,int r)
{
int nx = ++si ;
lc[nx] = lc[x] , rc[nx] = rc[x] , sum[nx] = sum[x] + 1 ;
if(l==r) return nx ;
int mid = (l+r)>>1;
if(mid>=p) lc[nx] = update(lc[nx],l,mid);
else rc[nx] = update(rc[nx],mid+1,r);
return nx ;
}
int query(int li,int ri,int l,int r,int k)
{
int mid = (l+r)>>1 , x = sum[ lc[ri] ] - sum[ lc[li] ] ;
if(l==r) return l ;
if(k<=x) return query(lc[li],lc[ri],l,mid,k);
else return query(rc[li],rc[ri],mid+1,r,k-x);
}
int main()
{
rd(n) , rd(m) ;
for(int i=1;i<=n;i++){
rd(a[i]) , b[i] = a[i] ;
}
sort(b+1,b+1+n);
int all = unique(b+1,b+1+n) - b - 1 ;
build(id[0],1,all);
for(int i=1;i<=n;i++){
p = lower_bound(b+1,b+1+all,a[i]) - b ;
id[i] = update(id[i-1],1,all);
}
while(m--){
int l , r , k ;
rd(l) , rd(r) , rd(k) ;
cout<<b[query(id[l-1],id[r],1,all,k)]<<endl;
}
}
#include <iostream>
#include <algorithm>
const int mxn = 5e6+7 ;
using namespace std;
typedef long long ll;
int p,t,n,m, si , a[mxn] , b[mxn] , id[mxn] , lc[mxn] , rc[mxn] ,sum[mxn];
bool ans[mxn];
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
void build(int &x,int l,int r)
{
x = ++si; sum[x] = 0 ;
if(l==r) return ;
int mid = (l+r)>>1;
build(lc[x],l,mid); build(rc[x],mid+1,r);
}
int update(int x,int l,int r)
{
int nx = si++;
lc[nx] = lc[x] , rc[nx] = rc[x] , sum[nx] = sum[x] + 1 ;
if(l==r) return nx;
int mid = (l+r)>>1;
if(mid<p) rc[nx] = update(rc[nx],mid+1,r);
else lc[nx] = update(lc[nx],l,mid);
return nx ;
}
int query(int li,int ri,int l,int r,int k)
{
int x = sum[lc[ri]] - sum[lc[li]] ;
int mid = (l+r)>>1;
if(l==r) return l;
if(x>=k) return query(lc[li],lc[ri],l,mid,k);
else return query(rc[li],rc[ri],mid+1,r,k-x);
}
int main()
{
rd(n) , rd(m) ;
for(int i=1;i<=n;i++)
rd(a[i]) , b[i] = a[i] ;
sort(a+1,a+1+n);
int all = unique(a+1,a+1+n) - a - 1 ;
build(id[0],1,all);
for(int i=1;i<=n;i++){
p = lower_bound(a+1,a+1+all,b[i]) - a ;
id[i] = update(id[i-1],1,all);
}
while(m--){
int l , r , k ;
rd(l) , rd(r) , rd(k) ;
cout<<a[query(id[l-1],id[r],1,all,k)]<<endl;
}
}
