D. Multiset
Note that the memory limit is unusual.
You are given a multiset consisting of n integers. You have to process queries of two types:
add integer k into the multiset; find the k-th order statistics in the multiset and remove it. k-th order statistics in the multiset is the k-th element in the sorted list of all elements of the multiset. For example, if the multiset contains elements 1, 4, 2, 1, 4, 5, 7, and k=3, then you have to find the 3-rd element in [1,1,2,4,4,5,7], which is 2. If you try to delete an element which occurs multiple times in the multiset, only one occurence is removed.
After processing all queries, print any number belonging to the multiset, or say that it is empty.
Input
The first line contains two integers n and q (1≤n,q≤106) — the number of elements in the initial multiset and the number of queries, respectively.
The second line contains n integers a1, a2, …, an (1≤a1≤a2≤⋯≤an≤n) — the elements of the multiset.
The third line contains q integers k1, k2, …, kq, each representing a query:
if 1≤ki≤n, then the i-th query is “insert ki into the multiset”; if ki<0, then the i-th query is “remove the |ki|-th order statistics from the multiset”. For this query, it is guaranteed that |ki| is not greater than the size of the multiset.
Output
If the multiset is empty after all queries, print 0.
Otherwise, print any integer that belongs to the resulting multiset.
Examples
input
5 5
1 2 3 4 5
-1 -1 -1 -1 -1
output
0
input
5 4
1 2 3 4 5
-5 -1 -3 -1
output
3
input
6 2
1 1 1 2 3 4
5 6
output
6
Note
In the first example, all elements of the multiset are deleted.
In the second example, the elements 5, 1, 4, 2 are deleted (they are listed in chronological order of their removal).
In the third example, 6 is not the only answer.
解题思路：
权值线段树。 查找的时候二分，不是二分区间端点了，而是二分区间和。
内存只有28MB。开结构体就会超内存。所以只能开一个数组存线段树。区间端点体现在函数参数里。
AC代码：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std
;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
typedef pair
<int,int> PII
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double ld
;
const int MOD
= 1e9 + 7;
const ll mod
= 10007;
const double eps
= 1e-9;
const ll INF
= 0x3f3f3f3f3f3f3f3fll;
inline int read(){int ret
= 0, sgn
= 1;char ch
= getchar();
while(ch
< '0' || ch
> '9'){if(ch
== '-')sgn
= -1;ch
= getchar();}
while (ch
>= '0' && ch
<= '9'){ret
= ret
*10 + ch
- '0';ch
= getchar();}
return ret
*sgn
;}
inline void Out(int a
){if(a
>9) Out(a
/10);putchar(a
%10+'0');}
int qpow(int m
, int k
, int mod
){int res
=1%mod
,t
=m
%mod
;while(k
){if(k
&1)res
=res
*t
%mod
;t
=t
*t
%mod
;k
>>=1;}return res
;}
ll
gcd(ll a
,ll b
){if(b
> a
) swap(a
,b
); return b
==0?a
: gcd(b
,a
%b
);}
ll
lcm(ll a
,ll b
){return a
/gcd(a
,b
)*b
;}
ll
inv(ll x
,ll mod
){return qpow(x
,mod
-2,mod
)%mod
;}
int t
= 1,cas
= 1;
int n
,m
;
const int N
= 1e6;
typedef long long ll
;
#define lson rt << 1
#define rson rt << 1 | 1
#define int_mid int mid = (l+r) >> 1
int tree
[N
<<2];
void push_up(int rt
) {
tree
[rt
] = tree
[lson
] + tree
[rson
];
}
void update_point(int rt
, int pos
, ll val
,int l
,int r
) {
if (l
== r
&& pos
== l
) {
tree
[rt
] += val
;
return;
}
int_mid
;
if (pos
<= mid
) update_point(lson
, pos
, val
,l
, mid
);
else update_point(rson
, pos
, val
, mid
+1,r
);
push_up(rt
);
}
ll
query_point(int rt
, int pos
,int l
,int r
) {
if (l
== r
)
return l
;
int_mid
;
if(tree
[lson
] >= pos
) return query_point(lson
, pos
,l
,mid
);
else return query_point(rson
, pos
-tree
[lson
],mid
+1,r
);
}
signed main()
{
while(t
--)
{
scanf("%d",&n
);
scanf("%d",&m
);
for(int i
= 0 ; i
< n
; i
++){
int tmp
; scanf("%d",&tmp
);
update_point(1,tmp
,1,1,n
);
}
for(int i
= 0 ; i
< m
; i
++){
int k
;
scanf("%d",&k
);
if(k
> 0)
update_point(1,k
,1,1,n
);
else{
int ans
= query_point(1,-k
,1,n
);
update_point(1,ans
,-1,1,n
);
}
}
if(tree
[1] == 0){
cout
<<0<<endl
;
break;
}
else{
cout
<<query_point(1,1,1,n
)<<" ";
}
}
}
