260106 模拟赛

T1

你需要在一张 \((n+1)\times (m+1)\) 的棋盘上放置一些车，满足：

保证 \(n,m\ge 1\)。有一个卒初始在棋盘的第一行，卒只能向左右或者下三个方向移动。称一个格子是安全的当且仅当它可以被某一辆车控制。你需要使得卒不能仅通过安全的格子（也不能和车在一个格子）到达第 \(n+1\) 行。求方案数。

\(n,m\le 3000\)

我没看到一行一列不能有两个车，看到之后恍然大悟。最后 3min AC。

手模一下发现，有以下充要条件：所有棋子必须形成一条上升链或者下降链；若两个棋子在相邻两行，那么它们必须在相邻两列，反之亦然。于是直接 dp 即可。

给定一个序列和常数 \(k\)，有 \(q\) 次询问，每次询问查询一个区间有多少个有序二元组 \((i,j)\) 满足 \(a_i+a_j\le k\)。强制在线。

\(n,q\le 2\times 10^5\)

\(O(n\sqrt n\log n)\) 跟 \(O(n^2)\) 一个分。。。

注意到有一道题叫做 Yuno love sqrt tecnology I，强制在线区间逆序对，跟这道题一样。这是一种将莫队二次离线在线化的科技。注意到莫队二次离线本质上就是用数据结构维护插入删除，而数据结构就是用来高效处理贡献的。这种方法本质上就是在线处理了区间内所有二元组的贡献。

考虑分块，先预处理块内贡献（排个序然后扫一遍），然后预处理每个块和序列中的每个数之间的贡献（这里 \(O(n\sqrt n)\)），然后就可以知道两个块之间的贡献，然后可以 \(O(n\sqrt n)\) 求出一个区间的块的总贡献。

然后处理散块贡献。可以维护整块一个前缀对一个散块的贡献，然后直接差分做完了。题解的做法是维护每个块向一个块内的前缀的贡献（当然另一侧需要维护对应的后缀贡献），也可以 \(O(\sqrt n)\) 做出来。