Equilibrium（思维/线段树）

题目 题意：给定两个长度为 n n n的数组 a i , b i a_i,b_i ai​,bi​，q次查询，每次查询区间 [ l , r ] [l,r] [l,r]中，是否存在若干次操作，使得操作后的区间里的每个元素满足 a i = b i a_i=b_i ai​=bi​。每次操作为从区间 [ l , r ] [l,r] [l,r]中选出若干偶数个下标 p o s 1 , p o s 2 , . . . , p o s k pos_1,pos_2,...,pos_k pos1​,pos2​,...,posk​，对于下标 p o s 1 , p o s 3 , . . . pos_1,pos_3,... pos1​,pos3​,...的元素， a i a_i ai​+1；对于下标 p o s 2 , p o s 4 . . . pos_2,pos_4... pos2​,pos4​...， b i b_i bi​+1。 如果存在，输出最少的操作次数；否则输出-1。 参考 思路： 1、做下转换，令 c i = b i − a i c_i=b_i-a_i ci​=bi​−ai​，每次操作相当于对元素 c i c_i ci​做+1、-1操作 2、可以发现，每次操作，区间的权值和没有改变，令 s u m i sum_i sumi​为 c i c_i ci​的前缀和。要使得区间 [ l , r ] [l,r] [l,r]中 a i = b i a_i=b_i ai​=bi​，必要条件为 s u m r − s u m l − 1 = = 0 sum_r-sum_{l-1}==0 sumr​−suml−1​==0 3、对于元素 c i c_i ci​，都是先加后减，为使最终能 a i = b i a_i=b_i ai​=bi​，必须要满足区间 [ l , r ] [l,r] [l,r]上的前缀和非负。 证明：

• 如果 a 1 < b 1 a_1