bzoj2122 工作评估

(Updated: )
oi
,

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_i\ge 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_1\ge g_2$ 且 $s_1\ge s_2$，显然第二个子串是绝对不可能取到的。

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

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

g 和 s+x0 的图像，红色代表 f

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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%10+'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;
}