「MCOI-Zero / AC6-M14」Gracemeria Patrol

题目背景

「Talisman,一会你能不能和 Avalanche 一起出去而不是我?」 「我今晚想一个人静静。」 「我的妻女都死了。  刚刚确认的……」 「我保护了我的国家,  但我却守护不了我的家庭。」 「什么样的王牌  连自己的家庭都保护不了?」 「Monica……  还有 Jessica……」 **「How could I let this happen!!」** 「这个任务结束之后,  我将离开空军。」 「我受够了。  我没有继续飞行的理由了。」 …… 「一个不明物体正在高速飞行  在东北方。」 「这是战机?在这个时候?!」 「在雷达上确认未知物体,  这不是战机,它的速度太快了!」 「未知物体在雷达上消失了。  等一下……」 「一些物体在相同的方向上飞行。我认为这是……」 「我看到了,这些是导弹!」 「Ghost Eye,  我们遭到巡航导弹袭击了!」 「全机,拦截那些巡航导弹!  保护我们的城市!」 …… 「资料检查……  增援的隐形飞机正在接近。」 「这些人不懂得放弃吗?」 『我们为了你而回来了,Emmeria!』 「这些人到底是怎么了?还觉得死的人不够多吗?!」 $$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 14} \\\Large\text{Gracemeria Patrol}\\\tiny -\textit{ City Lights }-$$ ![](https://cdn.luogu.com.cn/upload/image_hosting/g0d60mgz.png)

题目描述

给定一个 $n\times m$ 的 01 矩阵,每一次操作可以改变一个位置以及其上面、左边、右边的值。如果原值是 $0$,则改变之后变成 $1$;否则变成 $0$。 例如下面矩阵在改变中括号表明的位置之后的形态: $$\begin{bmatrix}0&1&0&1&1\\1&0&[0]&1&0\\0&0&0&0&1\end{bmatrix}\rightarrow \begin{bmatrix}0&1&1&1&1\\1&1&1&0&0\\0&0&0&0&1\end{bmatrix}$$ **特别的,如果操作点在边界上,那么仅改变未超出边界的部分。** 现给定 $q$ 组询问,每组询问一个区间 $[l,r]$ 和一个常数 $k$,请你对行号在 $l,r$ 内的 01 子矩阵求出通过选出一些位置进行一次操作使其变为全 $0$ 的方案中,第 $k$ 行被操作了几次。 特别的,如果没有或者有多种选择操作位置的方法,输出 $-1$。 询问之间相互独立。

输入输出格式

输入格式


第一行三个整数 $n,m,q$。 接下来 $n$ 行,每行 $m$ 个字符,给出 01 矩阵。 接下来 $q$ 行,每行三个整数表示询问的 $l,r,k$。

输出格式


$q$ 行,每行一个整数表示对应询问的答案。

输入输出样例

输入样例 #1

10 4 2
1010
0110
0101
0000
1011
0111
1110
1011
0001
1100
1 10 6
2 5 3

输出样例 #1

2
2

说明

- Subtask 1(10 pts):$n,m\leq 3,q\leq 10$。 - Subtask 2(20 pts):$n,m,q\leq 10$。 - Subtask 3(20 pts):$n,q\leq 50,m\leq 10$。 - Subtask 4(20 pts):$n,q\leq 10^4,m\leq 10$。 - Subtask 5(30 pts):无特殊限制。 对于 $100\%$ 的数据,满足 $1\leq n\leq 5\times 10^4$,$1\leq m\leq 50$,$1\leq q\leq 5\times 10^5$,$1\leq l\leq k\leq r\leq n$。 idea:Sol1,solution:Sol1 & ethan\_zhou,code:Sol1,data:Sol1 --- 「Talisman……」 「一个天使不会交出它的翅膀除非  跳完最后一支舞,对不对?」