D. Multiset（权值线段树/树状数组/二分）

题目链接传送门

题目大意

       给你$n(n \le 10^6)$n(n≤106)个正整数$a(1\le a \le 10^6)$a(1≤a≤106)，然后有$q$q次操作，对于每一次操作可以插入一个数$k(1\le k\le10^6)$k(1≤k≤106)或者移除掉第$k$k小的数。在全部操作结束后，请输出数组中剩下的任意一个数。

分析过程

Solution 1

       权值线段树模板题，直接莽过去就行，可以刚好卡着空间过。时间复杂度为$O(nlogn)$O(nlogn)，但是常数较大。

Solution 2

       构造树状数组，维护每个数值的前缀，然后当删除一个数的时候二分这个前缀和区间。时间复杂度为$O(nlog^2n)$O(nlog2n)，常数较小。

Solution 3

       这个方法相对来说更加巧妙。注意到题目只需要输出数组剩余元素中的任意一个，那么我们可以直接二分这个答案。对于每一次二分过程，遍历一遍$a[maxn]$a[maxn]以及$q[maxn]$q[maxn]，直接统计出小于等于这个答案的数的个数$cur$cur（$cur=a[maxn]$cur=a[maxn]中小于等于当前答案的元素个数+$q[maxn]$q[maxn]中插入的小于等于当前答案的个数$-q[maxn]$−q[maxn]中删除的$-k\le$−k≤当前统计数的元素个数），如果$cur\gt0$cur>0则继续二分答案的左侧区间，否则继续二分右侧区间。时间复杂度为$O(nlogn)$O(nlogn)，且常数较小。

AC代码（Solution1）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 100;
typedef long long ll;
int n, k, q, a, t[maxn*6];
void insert(int rnode, int left, int right, int v){
	if(left == right){
		if(left == v)
			++t[rnode];
		return;
	}
	if(v < left || v > right) return;
	else{
		++t[rnode];
		int mid = (left + right) >> 1;
		insert(rnode<<1, left, mid, v);
		insert(rnode<<1|1, mid + 1, right, v);
	}
}
void remove(int rnode, int left, int right, int k){
	if(k < 1 || k > t[rnode]) return;
	if(t[rnode] >= k){
		--t[rnode];
	}
	int mid = (left + right) >> 1;
	if(t[rnode<<1] >= k){
		remove(rnode<<1, left, mid, k);
	}else{
		remove(rnode<<1|1, mid + 1, right, k - t[rnode<<1]);	
	}
} 
int query(int rnode, int left, int right){
	if(left == right){
		if(t[rnode])
			return left;
		return 0;
	}
	int mid = (left + right) >> 1;
	if(t[rnode<<1]){
		return query(rnode<<1, left, mid);
	}else{
		return query(rnode<<1|1, mid + 1, right);
	}
} 
int main(){
	int i, j;
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(i=1;i<=n;++i){
		cin>>a;
		insert(1, 1, n, a);
	}
	for(i=1;i<=q;++i){
		cin>>k;
		if(k > 0){
			insert(1, 1, n, k);
		}else{
			remove(1, 1, n, -k);
		}
	}
	cout<<query(1, 1, n);
	return 0;
}

AC代码（Solution3）

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long double T;
typedef long long int LL;
 
#define st first
#define nd second
#define PLL pair <LL, LL>
#define PII pair <int, int>
 
const int N = 1e6 + 7;
const int MX = 1e9 + 7;
const LL INF = 1LL * MX * MX;
 
int n, q;
int in[N];
int query[N];
 
bool check(int val){
	int cur = 0;
	for(int i = 1; i <= n; ++i)
		if(in[i] <= val)
			++cur;
	
	for(int i = 1; i <= q; ++i){
		if(query[i] < 0){
			if(-query[i] <= cur)
				cur--;
		}
		else if(query[i] <= val)
			++cur;
	}
	
	return cur > 0;
}
 
int main(){
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &in[i]);
	
	for(int i = 1; i <= q; ++i)
		scanf("%d", &query[i]);
	
	int s = 1, e = n + 1;
	while(s < e){
		int mid = (s + e) / 2;
		if(check(mid))
			e = mid;
		else
			s = mid + 1;
	}
	
	if(s <= n)
		printf("%d\n", s);
	else
		puts("0");
	return 0;
}