#P17941. Sakura no Mahou
Sakura no Mahou
Sakura no Mahou
有两列长度为 的整数 和 ,初始元素均为 或 。
一次操作选择一个连续区间 ,将区间内每个 同时改为本次操作前的区间前缀和:
$$a_i\leftarrow\sum_{j=l}^{i}a_j\qquad(l\le i\le r).$$每天可以执行任意多次操作,但同一天所选区间必须两两不相交。求使所有位置满足 的最少天数,并输出一种达到最少天数的操作方案。如果不可能,报告无解。
输入格式
第一行是测试用例数 ,。
每组用例第一行包含 。第二行和第三行分别包含 个整数,给出 和 。
,;所有用例的 。
输出格式
无解时,对该组用例输出 -1。
否则先输出最少天数 。接下来 行,第 行输出
$$c_i\ l_{i,1}\ r_{i,1}\ l_{i,2}\ r_{i,2}\ \cdots\ l_{i,c_i}\ r_{i,c_i},$$表示第 天的 个操作区间。必须满足 ,且相邻区间满足 。当天不操作时可输出 。
若初始已符合要求,输出 ,不用再输出操作。最优方案不唯一时输出任意一种。
样例 1
3
5
1 0 1 0 1
0 1 0 1 0
3
1 1 0
1 1 1
10
1 0 0 1 0 1 0 0 1 0
1 0 1 0 0 1 0 1 0 0
-1
1
1 2 3
2
2 1 4 6 9
2 1 2 6 7