题目 题意：给定两个长度为 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
关注打赏
1688896170
查看更多评论
