分析

见注释。

代码(Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <algorithm>
const int maxn=200005;//因为同时存两种操作,这里应该开两倍内存
int n;
namespace BIT {
int bit[maxn];
static inline int lowbit(int x) {return x&-x;}
inline void add(int x,int d) {
while(x<=n) {
bit[x]+=d;
x+=lowbit(x);
}
}
inline int query(int x) {
int ans=0;
while(x>0) {
ans+=bit[x];
x-=lowbit(x);
}
return ans;
}
}
struct opt {//操作结构体
int type,x,y,k,s,cur;
//type表示操作类型
//当type为1时表示修改,x为修改位置,y为修改的值
//当type为2时表示查询,x为左端点,y为右端点,k为第k大,s为原来询问位置
//cur为偏移量
} q[maxn],q1[maxn],q2[maxn];int idx=0;
int ans[maxn],rem[maxn];
void solve(int head,int tail,int l,int r) {//整体二分
//head和tail表示处理操作的下标起始,l和r表示二分答案范围的起始。
int mid=(l+r)>>1;
if(l==r) {//处理值为mid
for(int i=head;i<=tail;++i) {//结果等于mid的查询给出结果
if(q[i].type==2) {
ans[q[i].s]=mid;
}
}
return;
}
if(head>tail) return;//越界退出
for(int i=head;i<=tail;++i) {//遍历结果在[l~r]的操作下标区间
if(q[i].type==1) {//赋值
if(q[i].y<=mid) {//此时y表示修改的值,表明值在左半边
BIT::add(q[i].x,1);//位置q[i].x加一
}
}
else if(q[i].type==2) {//查询
rem[i]=BIT::query(q[i].y)-BIT::query(q[i].x-1);
//在数组区间[q[i].x~q[i].y]内,其值在[l,mid]的个数
//如果个数比较少,那么第k大在[mid+1,r]中
}
}
for(int i=head;i<=tail;++i) {//树状数组清空
if(q[i].type==1) {
if(q[i].y<=mid) {
BIT::add(q[i].x,-1);
}
}
}
int t1=0,t2=0;
for(int i=head;i<=tail;++i) {//遍历结果在[l~r]的操作下标区间
if(q[i].type==2) {//查询
if(q[i].k<=q[i].cur+rem[i]) {//本查询结果应在左半边
q1[++t1]=q[i];
}
else {//本查询结果应在右半边
q[i].cur+=rem[i];//修改偏移
q2[++t2]=q[i];
}
}
else if(q[i].type==1) {//修改操作
if(q[i].y<=mid) {//修改的值在左半边
q1[++t1]=q[i];
}
else {//修改的值在右半边
q2[++t2]=q[i];
}
}
}
for(int i=1;i<=t1;++i) {//将q1中元素加入q[head~t1-1]
q[head+i-1]=q1[i];
}
for(int i=1;i<=t2;++i) {//将q2中元素加入q[head+t1~tail]
q[head+t1+i-1]=q2[i];
}
solve(head,head+t1-1,l,mid);
solve(head+t1,tail,mid+1,r);
}
//总结:整体二分的思想是二分答案,将所有答案在左半区间的操作和答案在右半区间的操作分离,二分答案左右区间求解。
int main() {
freopen("kth.in","r",stdin);
freopen("kth.out","w",stdout);
int m;
scanf("%d%d",&n,&m);
int val,max=0;
for(int i=1;i<=n;++i) {
scanf("%d",&val);
max=std::max(max,val);
q[++idx]=(opt){1,i,val,0,0,0};
}
int x,y,k;
for(int i=1;i<=m;++i) {
scanf("%d%d%d",&x,&y,&k);
q[++idx]=(opt){2,x,y,k,i,0};
}
solve(1,idx,0,max);
for(int i=1;i<=m;++i) {
printf("%d\n",ans[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}