bzoj2122 工作评估

2022-09-19 13:18:15 浏览数 (1)

bzoj2122 工作评估

Description

题目链接：bzoj2122

利用空闲时间，BX希望外出工作，工作开始之前，公司就会给BX一个评估值 X_0，之后每天BX的评估值都是根据上一天的评估值和当天公司的运行状况得出，即 X_i=X_{i-1} D_i,但是每天的评估值有一个上限，也就是说完整的评估公式应该是 X_i=min{X_i-1 D_i,L_i}。现在BX已经知道了该公司对自己的初始评估值 X_0、公司每天的运行状况 D_i、每天的评估上限 L_i，他的空闲时间是从第 A 天到第 B 天，他希望找到一段时间 i,j (A≤i≤j≤B)，使得从第i天开始工作，到第j天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都<初始评估值 X_0，BX可以选择不工作，从而得到最大的评估值。

对于100%数据,满足 N,M<50001,Di<10001,0≤Li<1000000001

Solution

分块好题，令 f(l,r,x_0) 表示区间 [l,r]，初始值为 x_0 得到的最大评估值。

不难发现该式子有两个性质：

性质一：若 x_ige x_j，显然有 f(l,r,x_i)ge f(l,r,x_j)。

性质二：令 g(l,r) 表示 f(l,r,inf)，则 f(l,r,x_0)=min{g(l,r),sum_{i=l}^rd_i x_0}。

根据性质二，我们可以得出一个重要推论：如果两个在 [l,r] 中的子串，满足 g_1ge g_2 且 s_1ge s_2，显然第二个子串是绝对不可能取到的。

所以最后得出的一个区间的子串一定满足 g_i 单调递增，s_i 单调递减。

考虑分块，每个块内的子串个数应该是 O(N) 级别的（未利用推论去重），然后我们可以利用推论，使用单调栈剔除那些绝对不可能造成贡献的子串，最后块内的答案就是 g 与 s x_0 的分界点。

所以块内答案可以直接二分即可，块之间则需要维护 X，代表保留的最大价值，用以作为下一个的初始值 x_0，所以我们还需要维护一个块内的前缀和后缀，分五类讨论：

  1. 从本块之前开始，到本块结束：我们只需要用 X 与本块的前缀更新答案即可。
  2. 在本块内开始，在本块内结束：我们只需要用 x_0 与本块块内答案更新即可。
  3. 从本块开始，到本块之后结束：用 x_0 与本块后缀更新 X。
  4. 从本块之前开始，到本块之后结束：用 X 与本块更新 X。
  5. 跟本块没有任何关系，并没有覆盖到本块任何部分：X=x_0。

然后维护一下就好了，注意块内二分边界。

Code

代码语言：javascript复制
#include<bits/stdc  .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define Cn const
#define CI Cn int&
#define gc getchar
#define DD isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f  ;cerr<<'='<<x<<",";_debug(f 1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!DD) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),DD);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=5e4 10,M=sqrt(N) 50;
int n,m,SZ,top,tot,bl[N],L[M],R[M],S[N];
struct Val{int D,L;}a[N];
struct node{int g,s;}stk[N];
#define M(x,y) ((node){x,y})
I bool cmp(Cn node& x,Cn node& y){return x.g^y.g?x.g<y.g:x.s<y.s;}
struct Block{
    node a[N],pre[M],suf[M];
    int sz,G,S,pt,st;
    I void P(node x){a[  sz]=x;}
    I void Pp(node x){pre[  pt]=x;}
    I void Ps(node x){suf[  st]=x;}
    I void B(){
        RI i;for(top=0,sort(a 1,a sz 1,cmp),i=1;i<=sz;stk[  top]=a[i],i  ) W(top&&a[i].s>=stk[top].s) top--;
        for(i=1;i<=top;i  ) a[i]=stk[i];sz=top;//开单调栈剔除绝不可能造成贡献子串
        for(top=0,sort(pre 1,pre pt 1,cmp),i=1;i<=pt;stk[  top]=pre[i],i  ) W(top&&pre[i].s>=stk[top].s) top--;
        for(i=1;i<=top;i  ) pre[i]=stk[i];pt=top;
        for(top=0,sort(suf 1,suf st 1,cmp),i=1;i<=st;stk[  top]=suf[i],i  ) W(top&&suf[i].s>=stk[top].s) top--;
        for(i=1;i<=top;i  ) suf[i]=stk[i];st=top;//前后缀同理
    }
    I int V(Cn node& v,CI x0){return min(v.g,v.s x0);}//价值计算
    I int Q(node* x,CI x0){
        RI n=x==a?sz:x==pre?pt:x==suf?st:-1,l=1,r=n,p=-1,X=x0;if(!(~n)) return 0;
        #define mid (l r>>1)
        W(l<=r) x[mid].g>=x[mid].s x0?p=mid,r=mid-1:l=mid 1;//二分寻找分界点
        if(~p) return X=V(x[p],x0),p<n&&(X=max(X,V(x[p 1],x0))),p>1&&(X=max(X,V(x[p-1],x0))),X;//注意边界
        else return max(max(V(x[1],x0),V(x[n],x0)),x0);
    }
}b[M];
I void B(){
    RI i,j,k,v;for(i=1;i<=n;i  ) !((i-1)%SZ)&&(R[tot]=i-1,L[  tot]=i),bl[i]=tot;R[tot]=n;
    #define MS M(v,S[k]-S[j-1])
    for(i=1;i<=tot;b[i].B(),i  ) for(b[i].S=S[R[i]]-S[L[i]-1],j=L[i];j<=R[i];j  ) for(v=2e9,k=j;k<=R[i];k  )
    v=min(a[k].L,v a[k].D),b[i].P(MS),j==L[i]&&(b[i].Pp(MS),0),k==R[i]&&(b[i].Ps(MS),0),j==L[i]&&k==R[i]&&(b[i].G=v);//建块
}
I int Q(CI l,CI r,CI x0){
    RI i,A=x0,bL=bl[l],bR=bl[r],X=x0;for(i=l;i<=min(r,R[bL]);i  ) X=min(max(X,x0) a[i].D,a[i].L),A=max(A,X);//散块暴力
    if(X=max(X,x0),bL<bR){for(i=bL 1;i<=bR-1;i  ) A=max(A,b[i].Q(b[i].pre,X)),X=min(S[R[i]]-S[L[i]-1] X,b[i].G),//情况1,4
    A=max(A,b[i].Q(b[i].a,x0)),X=max(X,b[i].Q(b[i].suf,x0)),X=max(X,x0);//情况2,3,5
    for(i=L[bR];i<=r;i  ) X=min(max(X,x0) a[i].D,a[i].L),A=max(A,X);}return A;//散块暴力
}
int main(){
    RI i,l,r,x0;for(read(n,m),SZ=sqrt(N),i=1;i<=n;i  ) read(a[i].D),S[i]=S[i-1] a[i].D;
    for(i=1;i<=n;i  ) read(a[i].L);B();W(m--) read(l,r,x0),writeln(Q(l,r,x0));return 0;
}
min ode sum

0 人点赞