今天做完POJ2182，突然想起来这道很久以前没补的cf题了，这两个题思路惊人的相似2333.
借用某谷的翻译：
你需要维护一个可重集。初始时里面有n个正整数{A1,A2,⋯An}，它们的值域为[1,n]。现在有q个操作，共有两类：
• 1,若k为负数，则删除排名为∣k∣的数字。若不存在排名为∣k∣的数字，则忽略这次操作。
• 2.若k为正数，则加入数字k，满足k∈[1,n]。
注意空间限制为28MB。
最后输出任意一个数列中存在的数字即可。
注意到很关键的一点就是每个数都在1~n范围之内，这意味着我们可以用一个数组来维护，a[i]的值为i这个数出现的次数。又看到内存限制，就能想到应该用树状数组。插入的话很简单，直接modify(x, 1)即可。删除的话则可以用二分，先查找出删除的位置，然后modify(pos, -1)即可。二分的核心就是用ask函数求出1~mid的前缀和，判断其与排名的关系。输出答案时随便找到一个ask(i) - ask(i-1)>0的i输出即可。
#include <bits/stdc++.h> #define N 1000005 using namespace std; int a[N] = {0}, n, q; void modify(int x, int y) { for(; x <= n; x += x & (-x)) { a[x] += y; } } int ask(int x) { int ans=0; for(; x; x -= x & -x) { ans += a[x]; } return ans; } bool check(int mid, int num) { if(ask(mid) < num) return 0; else return 1; } int find(int num) { int l = 1, r = n, mid; while(l < r) { mid = (l + r) / 2; if(check(mid, num)) r = mid; else l = mid + 1; } return r; } int main() { cin >> n >> q; int i; a[0] = 0; for(i = 1; i <= n; i++) { int temp; scanf("%d", &temp); modify(temp, 1); } for(i = 1; i <= q; i++) { int temp; scanf("%d", &temp); if(temp > 0) { modify(temp, 1); } else { temp = -temp; //删除排名为temp的数字 int pos = find(temp); modify(pos, -1);//pos一开始写成mid了 我是傻逼 } } bool flag = 0; for(i = 1; i <= n; i++) { if(ask(i) - ask(i-1) > 0) { cout << i <<endl; flag = 1; break; } } if(!flag) { cout<<0; } return 0; }