题解：P11587 [KTSC 2022 R2] 编程测试
dengchengyu · · 题解
考虑 Hall 定理，显然只需要判定限制更加严格的区间，答案
拆成前缀和的形式变成判定
考虑把询问挂在猫树上，分成以下答案的最小值：
-
- 考虑
[l,r] 在一边的情况，不妨考虑右边，我们预处理出所有前缀的答案。每次往前缀[MID+1,i-1] 后再加一个点i ，查询l\in [MID+1,i-1],r=i 的答案。由于斜率是递减的，限制可以看做求[MID+1,i-1] 中的 B 类直线与i 的 A 类直线的交点横坐标最小值，再向下取整就是答案。不难发现交点一定在这些直线组成的凸壳上，单调栈维护凸壳，查询在凸壳上二分即可，这部分复杂度是O(n\log ^2n) 。另一边是对称的但是在代码上细节上基本一致。
最后复杂度就是
const int N=1e5+5,M=4e6,V=3e8;
int a[N],b[N],ql[N],qr[N],n,Q;
long long s[N],t[N];
int ans[N];
vector<tuple<int,int,int>> q[N*4];
void insert(int x,int l,int r,int L,int R,int num) {
int mid=(l+r)>>1;
if(L<=mid && R>mid) {
q[x].emplace_back(L,R,num);
return;
}
if(R<=mid) insert(x*2,l,mid,L,R,num);
else insert(x*2+1,mid+1,r,L,R,num);
}
struct tree {
int ls[M],rs[M],tot;
long long K[M],B[M];
long long calc(int x,long long k,long long b) {
return x*k+b;
}
void insert(int &x,int y,int l,int r,long long k,long long b,auto &&cmp) {
x=++tot;
K[x]=K[y],B[x]=B[y],ls[x]=ls[y],rs[x]=rs[y];
if(!y) {K[x]=k,B[x]=b; return;}
int mid=(l+r)>>1;
if(cmp(calc(mid,k,b),calc(mid,K[x],B[x]))) swap(K[x],k),swap(B[x],b);
if(l<mid && cmp(calc(l,k,b),calc(l,K[x],B[x]))) insert(ls[x],ls[y],l,mid-1,k,b,cmp);
if(mid<r && cmp(calc(r,k,b),calc(r,K[x],B[x]))) insert(rs[x],rs[y],mid+1,r,k,b,cmp);
}
long long query(int x,int l,int r,int p,auto &&cmp) {
int mid=(l+r)>>1;
if(p<mid && ls[x]) return cmp(query(ls[x],l,mid-1,p,cmp),calc(p,K[x],B[x]));
if(p>mid && rs[x]) return cmp(query(rs[x],mid+1,r,p,cmp),calc(p,K[x],B[x]));
return calc(p,K[x],B[x]);
}
};
tree t1,t2;
int pre[N],suf[N];
int stk[N],top;
long double cross(long long k1,long long b1,long long k2,long long b2) {
return (long double)(b2-b1)/(k1-k2);
}
int rt[N];
void solve(int x,int l,int r) {
int mid=(l+r)>>1;
if(l<r) solve(x*2,l,mid),solve(x*2+1,mid+1,r);
if(q[x].empty()) return;
pre[mid]=suf[mid+1]=2e9;
top=0;
for(int i=mid;i>=l;--i) { // 最左 M 使得 cross(q,M)>=cross(M+1,M)，没有则为 top
if(top) {
int L=1,R=top-1,res=top;
while(L<=R) {
int m=(L+R)>>1;
if(cross(-i,t[i],-stk[m],s[stk[m]])>=cross(-stk[m+1],s[stk[m+1]],-stk[m],s[stk[m]])) res=m,R=m-1;
else L=m+1;
}
pre[i]=min(pre[i+1],(int)floor(cross(-i,t[i],-stk[res],s[stk[res]])));
}
while(top>1 && cross(-i,s[i],-stk[top],s[stk[top]])>=cross(-i,s[i],-stk[top-1],s[stk[top-1]])) --top;
stk[++top]=i;
}
top=0;
for(int i=mid+1;i<=r;++i) {
if(top) {
int L=1,R=top-1,res=top;
while(L<=R) {
int m=(L+R)>>1;
if(cross(-i,s[i],-stk[m],t[stk[m]])>=cross(-stk[m+1],t[stk[m+1]],-stk[m],t[stk[m]])) res=m,R=m-1;
else L=m+1;
}
suf[i]=min(suf[i-1],(int)floor(cross(-i,s[i],-stk[res],t[stk[res]])));
}
while(top>1 && cross(-i,t[i],-stk[top],t[stk[top]])>=cross(-i,t[i],-stk[top-1],t[stk[top-1]])) --top;
stk[++top]=i;
}
int lst=0;
t1.tot=0;
for(int i=mid;i>=l;--i) {
t1.insert(rt[i],lst,0,V,-i,t[i],[](long long x,long long y) {return x>y;});
lst=rt[i];
}
t2.tot=0;
lst=0;
for(int i=mid+1;i<=r;++i) {
t2.insert(rt[i],lst,0,V,-i,s[i],[](long long x,long long y) {return x<y;});
lst=rt[i];
}
for(auto [L,R,num]:q[x]) {
int u=0,v=V,res=0;
while(u<=v) {
int mid=(u+v)>>1;
// int v1=t1.query(rt[L],0,V,mid,[](long long x,long long y) {return max(x,y);});
// int v2=t2.query(rt[R],0,V,mid,[](long long x,long long y) {return min(x,y);});
if(t1.query(rt[L],0,V,mid,[](long long x,long long y) {return max(x,y);})
<=t2.query(rt[R],0,V,mid,[](long long x,long long y) {return min(x,y);}))
res=mid,u=mid+1;
else v=mid-1;
}
ans[num]=min(min(pre[L],suf[R]),res);
}
}
vector<int> testset(vector<int> A,vector<int> B,vector<int> L,vector<int> R) {
Q=L.size(),n=A.size();
for(int i=1;i<=n;++i) a[i]=A[i-1];
for(int i=1;i<=n-1;++i) b[i]=B[i-1];
b[n]=0;
for(int i=1;i<=Q;++i) ql[i]=L[i-1]+1,qr[i]=R[i-1]+1;
for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i]+b[i],t[i]=t[i-1]+a[i]+b[i-1];
for(int i=1;i<=Q;++i) {
insert(1,0,n,ql[i]-1,qr[i],i);
}
solve(1,0,n);
return vector<int>(ans+1,ans+1+Q);
}
// int main() {
// freopen("code.in","r",stdin);
// freopen("code.out","w",stdout);
// ios::sync_with_stdio(0); cin.tie(0);
// int n,m;
// cin>>n>>m;
// vector<int> A(n),B(n-1),L(m),R(m);
// for(int i=0;i<n;++i) cin>>A[i];
// for(int i=0;i<n-1;++i) cin>>B[i];
// for(int i=0;i<m;++i) cin>>L[i]>>R[i];
// auto ans=testset(A,B,L,R);
// for(auto i:ans) cout<<i<<'\n';
// }