题解当打卡…
算法1
(整体二分 + 树状数组) $O(n * logn * logn)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
struct node{
int op,x,y,k,id;
}q[M],lq[N],rq[N];
int tr[N];
int lowbit(int x){
return x & -x;
}
void add(int x,int v){
for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += v;
}
int query(int x){
int res = 0;
for(int i = x ; i ; i -= lowbit(i)) res += tr[i];
return res;
}
int ans[N];
void work(int l,int r,int ql,int qr){
if(l > r || ql > qr) return;
if(l == r){
for(int i = ql ; i <= qr ; ++i )
if(q[i].op == 2)
ans[q[i].id] = l;
return;
}
int mid = l + r >> 1;
int nl = 0,nr = 0;
for(int i = ql ; i <= qr ; ++i){
if(q[i].op == 1){
//将数值小于mid的下标添加到树状数组中,并加入到左半边区间
if(q[i].x <= mid) add(q[i].y,1),lq[nl++] = q[i];
//否则加入右半边区间
else rq[nr++] = q[i];
}
else{
int t = query(q[i].y) - query(q[i].x - 1);
//小于mid的数大于等于k,去左半边区间解决
if(q[i].k <= t) lq[nl++] = q[i];
//否则去右半边区间解决,k减去左半边区间的数目
else{
q[i].k -= t;
rq[nr++] = q[i];
}
}
}
//恢复树状数组
for(int i = ql ; i <= qr ; ++i){
if(q[i].op == 1){
if(q[i].x <= mid) add(q[i].y,-1);
}
}
for(int i = 0 ; i < nl ; ++i) q[ql + i] = lq[i];
for(int i = 0 ; i < nr ; ++i) q[ql + nl + i] = rq[i];
work(l,mid,ql,ql + nl - 1);
work(mid + 1,r,ql + nl,qr);
}
void solve(){
cin >> n >> m;
for(int i = 1 ; i <= n ; ++i){
int x;
cin >> x;
//修改操作,数值为x,下标为i
q[i] = {1,x,i};
}
for(int i = 1 ; i <= m ; ++i){
int l,r,x;
cin >> l >> r >> x;
//查询操作,查询l,r区间第x大数,查询编号i
q[i + n] = {2,l,r,x,i};
}
//在-INF,INF,解决1到n+m的询问
work(-INF,INF,1,n + m);
for(int i = 1 ; i <= m ; ++i) cout << ans[i] << endl;
}
signed main(){
IOS;
solve();
return 0;
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/