链接
http://acm.hdu.edu.cn/showproblem.php?pid=2852
题意
现在需要你对一个空序列做
n
n
n次操作，操作分三种
0
x
0\ \ x
0 x ：向序列中加入一个
x
x
x；
1
x
1\ \ x
1 x ：删除序列中的数
x
x
x，如果
x
x
x不存在，输出No Elment!；
2
x
k
2\ \ x\ \ k
2 x k ：查找大于
x
x
x的第
k
k
k大元素，输出它，如果不存在输出Not Find!
分析
线段树或者树状数组； 这里使用树状数组，首先将所有
x
x
x读入并离散化（所以下面说的
x
x
x，都是离散化后的
x
x
x，其实不离散应该也可以，数据不大），之后对于插入操作
(
0
,
x
)
(0,\ x)
(0, x)直接在
x
x
x位置插入一个
1
1
1即可，对于删除操作
(
1
,
x
)
(1,\ x)
(1, x)，判断
x
x
x是否存在只需要判断
s
u
m
(
x
)
−
s
u
m
(
x
−
1
)
sum(x)\ -\ sum(x\ -1)
sum(x) − sum(x −1)是否等于0，等于0说明不存在，否则存在； 对于
(
2
,
x
,
k
)
(2,\ x,\ k)
(2, x, k)操作，我们先判断是否存在大于
x
x
x的第
k
k
k大元素，实际上这就是需要我们判断大于
x
x
x的元素是否有
k
k
k个，如果大于
x
x
x的数的个数小于
k
k
k，那显然不存在第
k
k
k大元素，而判断大于
x
x
x的元素是否有
k
k
k个，只需判断
s
u
m
(
l
e
n
)
−
s
u
m
(
x
)
sum(len)\ -\ sum(x)
sum(len) − sum(x)是否小于
k
k
k，
l
e
n
len
len为树状数组的最大长度或者是一个很大的数也可以（当然不能越界），若大于等于说明存在大于
x
x
x的第
k
k
k大元素，之后根据
s
u
m
sum
sum的取值二分即可，最后可以找到一个满足
s
u
m
(
p
o
s
)
−
s
u
m
(
x
)
sum(pos)\ -\ sum(x)
sum(pos) − sum(x) ==
k
k
k的
p
o
s
pos
pos值，这个
p
o
s
pos
pos值即为答案（没离散即答案为
p
o
s
pos
pos，否则还需要反向查找原来的数）；
代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991
typedef long long ll
;
namespace fastIO
{
inline int read() {
char c
= getchar(); int x
= 0, f
= 1;
while (c
< '0' || c
> '9') { if (c
== '-') f
= -1; c
= getchar(); }
while (c
>= '0' && c
<= '9') x
= x
* 10 + c
- '0', c
= getchar();
return x
* f
;
}
}
using namespace fastIO
;
using namespace std
;
struct Op
{
int ope
, a
, k
;
}o
[MAXN
];
int n
, t
[MAXN
], b
[MAXN
], len
;
inline void insert(int x
, int val
) {
for (int i
= x
; i
<= len
+ 2; i
+= i
& -i
)
t
[i
] += val
;
}
inline int sum(int x
) {
if (x
<= 0)return 0;
int res
= 0;
for (int i
= x
; i
> 0; i
-= i
& -i
)
res
+= t
[i
];
return res
;
}
int main() {
while (scanf("%d", &n
)!=EOF) {
int cnt
= 0;
memset(t
, 0, sizeof(t
));
for (int i
= 1; i
<= n
; i
++) {
o
[i
].ope
= read();
o
[i
].a
= read();
b
[++cnt
] = o
[i
].a
;
if (o
[i
].ope
== 2) o
[i
].k
= read();
}
sort(b
+ 1, b
+ 1 + cnt
);
len
= unique(b
+ 1, b
+ 1 + cnt
) - b
- 1;
for (int i
= 1; i
<= n
; i
++) {
if (o
[i
].ope
== 0) {
int pos
= lower_bound(b
+ 1, b
+ 1 + len
, o
[i
].a
) - b
;
insert(pos
, 1);
}
else if (o
[i
].ope
== 1) {
int pos
= lower_bound(b
+ 1, b
+ 1 + len
, o
[i
].a
) - b
;
if (sum(pos
) - sum(pos
- 1) == 0)cout
<< "No Elment!" << endl
;
else insert(pos
, -1);
}
else {
int pos
= lower_bound(b
+ 1, b
+ 1 + len
, o
[i
].a
) - b
;
int x
= sum(pos
);
if (sum(len
) - sum(pos
) < o
[i
].k
)cout
<< "Not Find!" << endl
;
else {
int l
= 0, r
= len
+ 1;
while (l
< r
- 1) {
int mid
= (l
+ r
) >> 1;
if (sum(mid
) - x
>= o
[i
].k
) r
= mid
;
else l
= mid
;
}
cout
<< b
[r
] << endl
;
}
}
}
}
}
