Deltix Round, Summer 2021 E. Equilibrium

洛谷链接：Equilibrium - 洛谷

解法：设一个新数组c满足c[i] = a[i]-b[i]，再对c数组求前缀和，那么c[i]就是sum[i]的差分，那么我们的目标就是让[l, r]区间内所有c[i]都变成0，即sum[l-1] = sum[l] = .... = sum[r-1] = sum[r]，根据题目要求，我们是让c[i]++, c[j]--，其中i<j，那么造成的效果就是sum[i] ~ sum[j-1]都+1，其他不变。

容易发现，这种操作只能让sum增加，而不能减少，并且sum[l-1]和sum[r]都是不能被改变的。

所以得到有解的两个条件：sum[l-1] == sum[r]，以及中间的所有sum值都必须<=0（操作只能加，不能减，要是一开始就>0，那肯定没救了）。有解之后，最少操作次数是多少？显然就是看sum值最小的那个点了，答案就是sum[l-1] - minsum。

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e5+5;
int n,q,a[N],b[N],sum[N],l,r;
int mn[N][40], mx[N][40];

inline void build(){
    for(int i=1; (1<<i)<=n; i++)
    for(int j=1; j+(1<<i)-1 <= n; j++){
        mn[j][i] = min(mn[j][i-1], mn[j+(1<<(i-1))][i-1]);
        mx[j][i] = max(mx[j][i-1], mx[j+(1<<(i-1))][i-1]);
    }
}
inline int mnVal(int l,int r){
    int k=(int)(log(r-l+1)/log(2));
    return min(mn[l][k], mn[r-(1<<k)+1][k]);
}
inline int mxVal(int l,int r){
    int k=(int)(log(r-l+1)/log(2));
    return max(mx[l][k], mx[r-(1<<k)+1][k]);
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>n>>q; FOR(i,1,n) cin>>a[i]; FOR(i,1,n) cin>>b[i]; //input
    FOR(i,1,n) a[i]-=b[i], sum[i]=sum[i-1]+a[i]; //预处理，求前缀和
    FOR(i,1,n) mn[i][0] = mx[i][0] = sum[i]; //mn,mx初始化
    build(); //建立st表
    FOR(i,1,q){
        cin>>l>>r;
        if(sum[r]!=sum[l-1] || mxVal(l,r)>sum[l-1]) {cout<<-1<<'\n'; continue;}
        cout<<sum[l-1]-mnVal(l,r)<<'\n';
    }
}