Blog Post Rating CodeForces - 806E (线段树二分)

题目链接

题目大意: 有一个博客, 初始分数为$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);

     }

 }

巴特西

Blog Post Rating CodeForces - 806E (线段树二分)

最新文章

热门文章