E. Equilibrium

题目

对两个长度相同的数组的区间发起q次询问，最少多少次操作可使它们ai = bi
给定操作为选择一段偶数子区间，其中第一个数组的奇数个自增一，第二个数组的偶数位自增一。

思路

从总体上考虑

• 因为是选偶数区间，每次两数组的区间和的差总不变，所以询问区间的区间和一定要相等。

考虑每个子区间

• 因为a只操作奇数位，b只操作偶数位
  1. aL > bL 肯定无解
  2. 又因为虽然每次操作区间差值不变，但如果把修改区间右移一位，可以使修改后，sumb-suma将减小1，所以在局部上 ，sumb>suma 是允许的，反之 suma>sumb 一定无解
• 对于最小操作数的获取，因为每次操作独立并且最大可以使差值前缀和减少1 ，
  那么差值区间和最大值就是最少的操作次数。

---

由上可发现判断总和a，b差值的区间和得出，可以大致写出代码实现思路：

• 获取a，b的差值的前缀和
• 由于要获取区间最值，建立一个线段树解决
• 得到的最值是前缀最值，转化到区间最值进行判断即可解决本题

PS:因为不涉及修改，所以没必要打lazy_tag。

AC代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define endl '\n'
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =10 + 1e5, mod = 1e9 + 7;
ll a[N],b[N];
ll sum[N];
ll mn,mx;
int n,q;
struct Tree
{
	ll mn,mx;
}tr[N*4];
void push_up(int p ,int l,int r)
{
	tr[p].mn = min(tr[l].mn,tr[r].mn);
	tr[p].mx = max(tr[l].mx,tr[r].mx);
}
void build(int p = 1 ,int l =1,int r = n)
{
	if(l == r)
	{
		tr[p].mn = tr[p].mx = sum[l];
		return ;
	}
	int mid = l + r >> 1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p,p<<1,p<<1|1);
}

void query(int L,int R,int l=1,int r=n,int p=1)
{
	if(L<=l&&r<=R)
	{
		mn = min(mn,tr[p].mn);
		mx = max(mx,tr[p].mx);
		return;
	}
	int mid = l + r >> 1;
	if(L<=mid) query(L,R,l,mid,p<<1);
	if(R>=mid+1) query(L,R,mid+1,r,p<<1|1);
}
void solve()
{    
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)sum[i] = sum[i-1] +(b[i]-a[i]);

	build();

	while(q--)
	{
		int l,r;
		cin>>l>>r;
		mn = linf , mx = -linf;
		query(l,r);
		mn -= sum[l-1] , mx -= sum[l-1];
		if(mn < 0 || sum[r] - sum[l-1] !=0)
			cout << -1 <<endl;
		else cout << mx << endl;
	} 
}
signed main()
{
	ios::sync_with_stdio();cin.tie();cout.tie();

	solve();

	return 0;
}