bzoj2122 工作评估
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_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 的分界点。
所以块内答案可以直接二分即可，块之间则需要维护 X，代表保留的最大价值，用以作为下一个的初始值 x_0，所以我们还需要维护一个块内的前缀和后缀，分五类讨论：
- 从本块之前开始，到本块结束：我们只需要用 X 与本块的前缀更新答案即可。
- 在本块内开始，在本块内结束：我们只需要用 x_0 与本块块内答案更新即可。
- 从本块开始，到本块之后结束：用 x_0 与本块后缀更新 X。
- 从本块之前开始，到本块之后结束：用 X 与本块更新 X。
- 跟本块没有任何关系，并没有覆盖到本块任何部分：X=x_0。
然后维护一下就好了，注意块内二分边界。
Code
#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;
}