前言

link

今天的题目还是一如既往地难。可惜的是第一题我本来是写对了的，可惜在测试样例的时候输入的样例和我打开的答案文件不是一个样例的（）。天知道我为什么会把样例都看错，导致我写了一个暴力还爆零了。地山谦呀，还是要更加谦逊，要多多向优秀的人请教问题。

题解

目前改了前三道题，在这里来简单讲解以下思路。

T1

这道题虽然不是很难，但是很难讲。就是已知一个非负矩阵每一行和每一列的最大值，要求满足条件的矩阵个数。会发现每一行每一列的顺序是无关的，就都排个序。然后我们依次从小到大枚举最大值，观察这个让这个最大值满足条件的情况数。会发现这个最大值影响的部分是一个 L 型（左上侧的更小，肯定不能放，右下的又无关了），要这些列、行满足条件。就直接 [[容斥]] 有多少行和多少列一定没有最大值就行。

T2

这道题邓老师的方法不是很理解，正解是 [[分块]]，个人认为比较好理解。对于一个查询，我们能够比较容易地发现，就是找到最近的一个影响这个点的1操作然后看这之间的2操作对其的影响。那么我们怎么分块呢？我们首先用的复杂度用 bitset 求出每个点能够到达的点。然后对于每一个询问我们现在本块内查找是否有它的前一个 1 操作，如果有在本块内直接暴力搞，不然开一个数组来记录每个位置前一个影响的1操作（这个数组在每一个块结束后更新，更新（倒着来，标记一下））。我们考虑中间2操作的影响，如果在一个块内就暴力，我们考虑每一个块的2操作对每个位置的影响。我们直接每个块开一个数组，记录这个块中影响某个位置的最小值。当前一个 1 操作不在同一个块中时就这样搜索。为什么是对的？因为这中间没有其它影响这个点的 1 操作，所以肯定是对的。那么怎么获得这个数组呢？我们将每个块中的2操作按照值从小到大排序，标记以下并且修改就行。一个块中复杂度。

P.S. 最开始块的大小我就开的，后来发现 T 了？然后尝试将每个块的长度开大，直接到 1000 都能过。猜测是每次块结束时要更新，而且询问操作可能比较少的缘故。

T3

通过仔细观察可以发现每一次冒泡排序肯定最多往左移动一格。那么答案就是最大的，也就是位置减去排名。用一个值域[[线段树]]维护即可。要注意，对于一个数，离散化时要带上位置，显然当值相同时，位置越靠前排名越小。这道题的实现有很多，不过写复杂一点更好理解。题解虽然短，但不直观，但是也是很有启发意义的。

T4

改编自 NOI 2018 情报中心。

后记

要继续努力，保持谦逊，积极向上。