【Codeforces 773E】Blog Post Rating
线段树。
题目大意：
给定一个空的数组，每次加入一个数。
你有一个变量 $x$，初始为 $0$，你需要依次遍历数组里的每个元素。如果当前遍历到的 $a_i\lt x$，则 $x$ 减 $1$。如果 $a_i\gt x$，则 $x$ 加 $1$。如果 $a_i=x$，则 $x$ 不变。
每次加完一个数之后，你需要重新安排这个数组的元素的顺序，然后使得遍历完后的 $x$ 最大。
每次输出能够得到的最大的 $x$。
题解：
最优方案中，$a_i$ 都是从小到大排好序的。
如果剩下的 $a_i$ 都大于等于 $x$，则有方案使得 $x$ 不会变小，此时先用掉小的 $a_i$ 肯定更好。
如果剩下的 $a_i$ 都小于 $x$，则先用掉小的 $a_i$ 也更好，这样 $x$ 会在变小到某个值的时候，转化为“剩下的 $a_i$ 都大于等于 $x$”的状态，那么原来对 $x$ 贡献为负的数，现在对其贡献就会变为 $0$ 或者正。
如果两者都有，那么先让它变小，再变大，也是优的。
于是我们考虑用权值线段树维护数组中的元素的出现情况，然后想办法快速模拟这个过程。
由上述算法我们知道，$x$ 一开始是不断减小的，当到某个值的时候，就会单调不降。我们考虑先求出这个临界值。
也就是说，我们要求出一个最小的 $k$，满足 $[-\infty,k]$ 的出现次数大于等于 $-k$。这个可以在权值线段树上二分。
然后我们考虑增大的过程。
假设当前的数是 $a_i$，后面有 $k_i$ 个数，那么一路畅通无阻，可能得到的值就是 $a_i+k_i$。
所以我们的答案就是 $\min\{x+k_0,a_1+k_1,a_2+k_2,\ldots,a_n+k_n\}$。
对于权值线段树的一段区间，我们维护这个区间里的 $k_i$ 以及 $\min\{a_i+k_i\}$ 即可。
时间复杂度 $O(m\log n)$。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
const int N=1e6+5,M=5e5;
int d[N<<2],mn[N<<2],n;
void add(int l,int r,int o,const int&x){
if(l==r)++d[o],mn[o]=l;else{
const int mid=l+(r-l)/2;
if(x<=mid)add(l,mid,o<<1,x);else add(mid+1,r,o<<1|1,x);
d[o]=d[o<<1]+d[o<<1|1];
mn[o]=min(mn[o<<1]+d[o<<1|1],mn[o<<1|1]);
}
}
int find(int l,int r,int o,int k=0){
if(l==r)return l;
const int mid=l+(r-l)/2;
if(d[o<<1]+k>=-mid)return find(l,mid,o<<1,k);return find(mid+1,r,o<<1|1,k+d[o<<1]);
}
int query(int l,int r,int o,const int&L,const int&R){
if(L<=l&&r<=R)return d[o];
const int mid=l+(r-l)/2;
if(L<=mid&&mid<R)return query(l,mid,o<<1,L,R)+query(mid+1,r,o<<1|1,L,R);
if(L<=mid)return query(l,mid,o<<1,L,R);return query(mid+1,r,o<<1|1,L,R);
}
void solve(int l,int r,int o,const int&L,const int&R,int&nw){
if(L<=l&&r<=R)nw=min(nw+d[o],mn[o]);else{
const int mid=l+(r-l)/2;
if(L<=mid)solve(l,mid,o<<1,L,R,nw);
if(mid<R)solve(mid+1,r,o<<1|1,L,R,nw);
}
}
int solve(){
int x=find(-M,M,1);
int tot=query(-M,M,1,-M,x),nw=-tot;
if(nw<x)nw=x;
return solve(-M,M,1,x+1,M,nw),nw;
}
int main(){
scanf("%d",&n);
memset(mn,0x3f,sizeof mn);
while(n--){
int x;
scanf("%d",&x);
add(-M,M,1,x);
printf("%d\n",solve());
}
return 0;
}