D. Multiset
题意
要求实现一种multiset
可以插入数删除数
现在原来的multiset有n个数每个数为ai
q次操作
每次操作输入一个数x
若x>0 则插入x
若x<0则删除当前set中第|x|个数
问最后set中存在什么数输出其中一个
n q<1e6 ai<1e6
假设我们要找到最后set中第1个数
需要一个函数count能统计出在经过所有操作后set中比某数x小的有几个
可以用树状数组维护前缀和 (若n大于1e8)
二分枚举某数x查询它是否是set中的第k大 若count(x)==k 那么x就是set中第k大的数
为什么二分枚举的数x最后一定会落在set中某一个确定数中,因为二分的依据是判断set中比数x小的数有几个(count函数)
最后二分结果一定是逐渐逼近于“临界点”即在某个point 当x<point, count=m x>=point, count=m+1
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
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
# define endl '\n'
# define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e6+5;
int data[Max],ndata[Max];
int n,q;
int count_arr(int bound){
int cnt=0;
for(int i=0;i<n;i++)if(data[i]<=bound)cnt++;
for(int i=0;i<q;i++){
if(ndata[i]>0){
if(ndata[i]<=bound)cnt++;
}
else {
if(abs(ndata[i])<=cnt)cnt--;
}
}
return cnt;
}
int main(){
Turnoff;
cin>>n>>q;
for(int i=0;i<n;i++)cin>>data[i];
for(int i=0;i<q;i++)cin>>ndata[i];
if(!count_arr(Max))cout<<0<<endl;
else{
int L=0,R=Max,ans=0;
while(L+1<R){
int mid=(L+R)>>1;
if(count_arr(mid)>=1){
ans=mid;
R=mid;
}
else L=mid;
}
cout<<ans<<endl;
}
}
|