写代码，也写下代码之外的事。

首先不同的地图最多只有16种了，每张地图可以组合的格式是 $2^{16}$ ,因为同一种地图变成全 $1$ 的步骤是一样的，那么我们可以这么抽象，把一种不同的地图状态看成二进制的某一位,把一些地图的组合看成是一个点，要求的是最小花费，我们可以用全 $1$ 的地图作为起点，向外拓展可以到达的点，那么就可以使用最短路求解。 具体的：令 $dis[x]$ 表示到达 $x$ 这个地图状态的最小花费 , $x$ 在第 $i$ 位是 $1$ 代表的就是代表有第 $i$ 张地图。我们可以定义 $trans[bit][S]$ 表示 当前有的地图集合是 $S$ 进行 $bit$ 操作时变成的状态集合 $S^{\prime }$ . $bit$ 是题目给的一行，一列等等的操作，具体是把 $2\times 2$ 的格子从左到右，从上到下设为 $1,2,4,8$ ，那么比如说对上面一行操作，那就是一张地图的二进制表示异或上 $3$

考虑一个序列最中间的左括号和右括号，如果这两个交换那么序列是不合法的，由此可以猜测确定操作序列唯一确定的条件。利用一种抽象的前缀和，把左括号看成 $1$ ,右括号看成 $-1$ ,对于一个左括号，如果和一个右括号中间的有一个前缀和是 $<2$ 的,那么操作序列就可以唯一确定，每次枚举左括号位置，计算合法方案数求和即可.

传送门：https://codeforces.com/gym/105851

总得来说，思路就是先找到，$L[i]$ 和 $R[i]$ ,左右第一个满足偏序条件的索引，即 $L[i]=j,s.t.j<i\&\&x[j]>=x[i]\&\&y[j]>=y[i]$ , $R[i]$ 同理。找到之后，考虑每个位置$i$ 能为区间 $[l,r]$ 产生的贡献，我们发现把询问 $[l,r]$ 看成二维平面的点，那么 对于 $i$ ,产生的贡献的区域就是 $[L[i]+1,i]\times [i,R[i]-1]$ ,贡献为1。

一个经典的套路，二分答案+check,检查是否可行也是经典的转化，把符合条件的变成1，不符合条件的置0，现在问题就变成了一个01序列可以用中位数代替3个数,让0尽量消去，1尽量多。