#1509. 「Diligent-OI R1 B」DlgtArray

「Diligent-OI R1 B」DlgtArray

题目描述

现给定一个长为 nn 的序列 a1∼ana_1\sim a_n,其中 ai∈{0,1}a_i\in\{0,1\}。

qq 次询问,每次给定 l,r,kl,r,k,要你更改一些位置上的数值(只能改为 00 或 11)使得 ∑i=lrai=k+∏i=lrai\sum\limits_{i=l}^ra_i=k+\prod\limits_{i=l}^ra_i。也就是说要让 al∼ara_l\sim a_r 的和要恰好等于 al∼ara_l\sim a_r 的乘积再加上 kk。你需要求出最少的修改次数。如果无解,输出 −1-1。

请注意每次的更改不会对后续询问产生影响。

输入格式

第一行输入 n,qn,q。

接下来一行 nn 个整数 a1∼ana_1\sim a_n。

接下来 qq 行,每行三个整数 l,r,kl,r,k。

输出格式

输出 qq 行,每行一个整数表示最少的修改次数。如果无解请输出 -1。

样例

5 4
0 0 1 0 1
1 3 2
2 4 0
3 5 2
1 1 1
1
1
0 
-1
8 3
1 1 1 1 1 1 1 1
2 6 2
5 8 2
1 8 7
3
2
0

题目来源:洛谷 P11272