题解 CF1556E 【Equilibrium】

题目意思：

有 \(n\) 组数 \(a_1,a_2,\cdots,a_n\) 和 \(b_1,b_2,\cdots,b_n\)，\(q\) 次独立的询问，每次询问区间 \(l\sim r\)，求多少次“平衡操作”使得每个满足 \(l\le i\le r\) 的 \(i\) 都有 \(a_i=b_i\)，无法完成输出 -1。

平衡操作指的是给出一个长度为偶数位置序列 \(l\le pos_1，进行操作：\(a_{pos_1},a_{pos_3},a_{pos_5},\cdots\) 加上 1，\(b_{pos_2}\) 加上 1。

我们发现如果 \(a_i\) 减去 1，那么就相当于是 \(a_i-b_i\) 减去 \(1\)。我们发现如果 \(b_i\) 减去 1，那么就相当于是 \(a_i-b_i\) 加上 \(1\)，最终要让每个满足 \(l\le i\le r\) 的 \(i\) 都有 \(a_i-b_i=0\)。

我们去观察它的操作序列，实际上这些元素是分成了若干个组，比如 \(po s_1\) 和 \(pos_2\)。

我们把 \(a_i-b_i\) 这个东西前缀和一下，\(s_i\) 表示 \((a_1-b_1)+(a_2-b_2)+\cdots+(a_i-b_i)\)，就会发现每组操作 \(pos_1,pos_2\)，相当于是在前缀和上区间加 \(s_{pos_1}\sim s_{pos_2-1}\) 区间加 1。

判 -1 就是 2 种情况：

1. \(s_r\ne s_{l-1}\)
2. \(\max\limits_{i=l}^{r}\{s_i\}>s_{l-1}\) （因为是区间加 1）

答案是 \(s_{l-1}-\min\limits_{i=l}^{r}\{s_i\}\)，都不是很困难。

区间查询 \(\max\) 和 \(\min\)，用 ST 表实现即可。

#include
#define int long long
#define log(a) cerr<<"[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<void chkmax(T&x,T y){x=max(x,y);}
templatevoid chkmin(T&x,T y){x=min(x,y);}
templateinline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
const int N=1e5+10,M=25;
int a[N],f[N],lg[N],mxn[M][N],mnn[M][N];
pairquery(int l,int r){
	int len=lg[r-l+1];
	return make_pair(max(mxn[len][l],mxn[len][r-(1<>1]+1;
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1,x;i<=n;i++){
		read(x);
		a[i]-=x;
		f[i]=f[i-1]+a[i];
	}
	// cout<<"->f";for(int i=1;i<=n;i++)cout<a=query(l,r);
		// log(a.first);log(a.second);
		if(f[r]!=f[l-1]||a.first>f[l-1])puts("-1");
		else cout<