题目大意: 有一个博客, 初始分数为$0$, 有$n$个人, 第$i$个人有一个期望值$a_i$,
如果第$i$个人浏览博客时,博客赞数高于$a_i$博客分数$-1$, 低于$+1$, 相等不变,
对于每个$i$, 求出$[1,i]$的人按任意顺序浏览博客后最大分数.
题解:
首先, 用贪心可以知道所有人按期望升序排列, 最后得分一定最大
由于期望有负数, 博客分数一定是先减后增的, 然后对这两段分类讨论
对于递减的段, 最后分数为递增递减的临界值
假设临界值为$x$, 设比$x$小的数的个数为$cnt_x$
可以发现$x$是第一个满足 $cnt_x+x>=0$ 的$x$
比方说排序后序列为$-10,-10,-10,-6,-2,-1$ 那么$x$就为$-4$
权值线段树上二分即可求出$x$ (初值设为$x$, 转为二分第一个$>=0$的数)
在考虑递增区间, 假设当前一共有$r$个数
有转移方程 $f_i=min(a_i,f_{i-1}+1),$ $f$为得分, $a$为排序后数组
可以得到$f_r=min(a_r,a_{r-1}+1,a_{r-2}+2,...,a_{l}+r-l,x+(r-x))$, $a_{l}$为第一个比$x$大的数
用权值线段树维护最小值即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
using namespace std; const int N = 5e5+, INF = 0x3f3f3f3f; int n, m, ans;
struct _ {
int mx,tag;
void upd(int x) {
mx+=x,tag+=x;
}
} v1[N<<], v2[N<<]; //v1维护的递减区间
//v2维护递增区间 void pd(_ *v, int o) {
if (v[o].tag) {
v[lc].upd(v[o].tag);
v[rc].upd(v[o].tag);
v[o].tag=;
}
} void add1(int o, int l, int r, int ql, int qr) {
if (ql<=l&&r<=qr) return v1[o].upd();
pd(v1,o);
if (mid>=ql) add1(ls,ql,qr);
if (mid<qr) add1(rs,ql,qr);
v1[o].mx=max(v1[lc].mx,v1[rc].mx);
} void add2(int o, int l, int r, int ql, int qr) {
if (ql<=l&&r<=qr) return v2[o].upd();
pd(v2,o);
if (mid>=ql) add2(ls,ql,qr);
if (mid<qr) add2(rs,ql,qr);
v2[o].mx=min(v2[lc].mx,v2[rc].mx);
} int qry1(int o, int l, int r) {
if (l==r) return l;
pd(v1,o);
if (v1[lc].mx>=) return qry1(ls);
return qry1(rs);
} void qry2(int o, int l, int r, int ql, int qr) {
if (v2[o].mx>=ans) return;
if (ql<=l&&r<=qr) return ans=min(ans,v2[o].mx),void();
pd(v2,o);
if (mid>=ql) qry2(ls,ql,qr);
if (mid<qr) qry2(rs,ql,qr);
} void build1(int o, int l, int r) {
if (l==r) return v1[o].mx=l,void();
build1(ls),build1(rs);
v1[o].mx=max(v1[lc].mx,v1[rc].mx);
} void build2(int o, int l, int r) {
if (l==r) return v2[o].mx=l,void();
build2(ls),build2(rs);
v2[o].mx=min(v2[lc].mx,v2[rc].mx);
} int main() {
scanf("%d", &n);
build1(,-N,);
build2(,-N,N);
REP(i,,n) {
int k;
scanf("%d", &k);
if (k<) add1(,-N,,k,N);
add2(,-N,N,-N,k-);
int x = qry1(,-N,);
ans = INF, qry2(,-N,N,x,N);
printf("%d\n", ans);
}
}