近年 NOI 题目选做

· · 个人记录

洛谷博客好丑

总是在本地写做题记录没意思，放上来造福社会（不会真有人看你的题解吧？）。

清单

NOI 2016

优秀的拆分

问题即为对每个位置求出向左/右边有多少个形如 AA 的后/前缀。

如果枚举 A 的长度 l，每隔 l 个位置设置一个关键点，则一个 A 恰好包含一个关键点。

枚举左边的 A 包含的关键点位置 i ，容易发现这样的AA的最左侧的合法位置是一段区间。左右端点通过求前后缀 lcp 得到，使用 st 表+后缀数组刻画即可。

时间复杂度 O(Tn\log n)。

网格

显然答案小于等于 2 。答案为 -1 或 0 容易判断，问题转化为求是否存在割点。

将每个障碍周围的八连通的点，存在障碍的行列的首尾点，以及四个角的点拿出来当关键点建图，如果两个点同行同列且之间不存在障碍就连边，直接跑 tarjan。

循环之美

将第一个中括号莫反，得到 $\sum\limits_{d} \mu (d)[d\bot k] \lfloor \frac{n}{d} \rfloor \sum\limits_{i=1}^{\lfloor \frac{m}{d} \rfloor} [i \bot k]$。 第二个求和符号右边的部分仅和 $\lfloor \frac{m}{d} \rfloor$ 有关，且容易 $O(k)-O(1)$ 计算，设为 $g(m)$。 对 $d$ 数论分块，问题形如对于 $\forall n'\mid n$，求 $f(n')=\sum\limits_{i=1}^{n'} \mu(i)[i\bot k]$。 考虑添项（枚举 $i$ 的因数）配莫反式子，同时得到递归式： $f(n')=\sum\limits_{j=1}^{n'}[j\bot k]\sum\limits_{i = 1}^{\lfloor \frac{n'}{j} \rfloor}\mu(i)[i\bot k]-\sum\limits_{j=2}^{n'}[j\bot k] f(\lfloor \frac{n'}{j} \rfloor)

整理右式前一项，枚举 i\times j=t ：

\sum\limits_{j=1}^{n'}[j\bot k]\sum\limits_{i = 1}^{\lfloor \frac{n'}{j} \rfloor}\mu(i)[i\bot k]=\sum\limits_{t=1}^{n'}[t\bot k]\sum\limits_{i \mid t }\mu(i) = \sum\limits_{t=1}^{n'}[t\bot k][t=1] = 1

原递推式即为 f(n')=1-\sum\limits_{j=2}^{n'}[j\bot k] f(\lfloor \frac{n'}{j} \rfloor)，杜教筛即可。

时间复杂度 O(n^{\frac{2}{3}} + k)。

区间

考虑枚举最大区间的长度，暴力可以二分最小区间长度并判断是否合法。

将二分改为双指针，区间修改，全局最值，时间 O(n \log n)。

国王饮水记

首先将 h_2...h_n 排序并去掉小于 h_1 的。

最优策略形如将 h_2...h_n 的一个后缀分为小于等于 k 个区间，每次操作 1 和最靠前未操作的区间。

直接 dp， 设 f_{i,j} 表示前 i 个位置分为 j 段的最大价值，转移 f_{i,j} = \max \limits_{k<i} \frac{f_{k, j - 1} + sum_i - sum_k}{i - k + 1}。

容易发现转移的几何意义是坐标系上两点 (i,sum_i) 到 (k - 1, sum_k - f_{k,j-1}) 的斜率的最大值，考虑维护下凸壳。容易猜到转移具有决策单调性，因此类似斜率优化那样线性维护即可。

时间复杂度 O(nkp)。

引理：长度超过 1 的区间个数的数量级低于 O(\log nk)。

时间复杂度 O(np\log nk)。也可以考虑先用 double 判断大小，得到答案后再用高精度小数还原。

NOI 2017

整数

对修改操作的加减法分开考虑，维护两个大整数，在查询时只需比较两个后缀的大小关系即可。

注意单次修改可能会近很多位，但均摊是 O(n) 的，可以暴力实现。

查询操作需要支持找左边第一个不等的位置，用 set 维护即可。

复杂度 O(n\log n)。

蚯蚓排队

假设我们可以对每个 k 分别开一个哈希表，维护所有串的长为 k 的子串的哈希值。查询时只需要取对应的桶里找就可以了，是 O(\sum |s|) 的。

容易发现分裂和合并操作的总数是 O(c) 的。每次只需要考虑包含连接点（断点）的子串即可，这只有 O(k^2) 种子串。

复杂度 O(nk+ck^2+\sum |s|)。

泳池

下文中称选一个格子表示钦定它是不安全的。

容斥，将“恰好为 k ”转为“不超过 k ”。

考虑最下面一行的选法，我们从选的位置断开，分成若干小矩形。假设它们的宽分别为 w_1...w_t，那么我们将一个 (n,k) 的问题拆解为了 (w_1,k-w_1)...(w_t,k-w_t) 的问题。可以 dp 计算。

由于需要保证 k-w_1\ge 0，我们钦定完最后一行后，小矩形的宽都是 O(k) 的，我们可以提前把答案通过上述 dp 预处理出来。这部分是 O(k^2) 的。

现在只需要考虑最下面一行的 dp，形如 f_n=\sum\limits_{i=1}^{k+1}a_if_{n-i}。这是一个常系数齐次线性递推，暴力多项式取模即可做到 O(k^2\log n)。

游戏

若 d=0，每个地图的选择只有两种，直接跑 2-sat 即可。

注意到 d 很小，枚举所有 x 地图是否选赛车 A，若不选择等价于一张 a 地图。

时间复杂度 O(2^d(n+m))。

蔬菜

时光倒流后变为经典反悔贪心模型。

另一种做法是按价值从大到小考虑，每次找到第一个能卖出这个菜的位置卖出去，也是经典的用并查集维护的模型。

NOI 2018

归程

每次询问相当于保留 a 值大于 p 的边，求和 v 联通的点的最小点权（即到 1 的距离，可以预处理）。

考虑建出 kruskal 重构树，询问的一个联通块是一个子树，倍增找到最高的祖先仍联通即可。

冒泡排序

排列取到上界的充要条件：不存在一个数既向前换又向后换。

再转化一下：序列不存在长度大于3的等差数列。

再转化一下：将前缀最大值去掉后剩下的数递增。

因而从左到右扫维护两个值 a,b，a 表示扫到的下标， b 表示最大值。每扫一个数相当于 a 加 1， b 加非负整数，需满足 a\le b\le n。那么相当于网格左上角走到右下角，且不走到一条折线下方，无限制时折线法即可。

有限制时相当于固定一个前缀，前缀后一个数大于某个数。容易发现因为这个前缀是合法的，前缀后一个数一定是前缀最大值。套上折线法的式子相当于求 \sum\limits_{i=0}^n\tbinom{x+n}{x}=\tbinom{x+n+1}{x+1}。

你的名字

先把所有串拼在一起后缀排序一下。

现在一次询问需要对于每个后缀算出来其最长前缀是 S[l,r] 的子串。

直接二分并倍增找到 SA 上的左右端点。然后相当于二维平面上有一些标记，每次查一个矩形内是否存在标记。

对一维扫描线并对另一维线段树维护即可。

实际上，height 数组每次降 1 的结论在这里仍然适用，因为相当于求一个字符串所有后缀的最长前缀在另一个字符串出现，每次删掉第 1 个字符后面都相等。这样检查次数是均摊线性的。

时间复杂度 O((|S|+\sum|T|)\log)。

屠龙勇士

CRT 裸题。注意考虑同余方程的解前最好将 gcd 除掉。

情报中心

设两条路径为 (u_1,v_1,w_1),(u_2,v_2,w_2)，不妨设 dis(u_1,u_2)+dis(v_1,v_2)\le dis(u_1,v_2)+dis(v_1,u_2)，则答案的两倍可以表示为

dis(u_1,v_1)+dis(u_2,v_2)+dis(u_1,u_2)+dis(v_1,v_2)-2w_1-2w_2

枚举 t=lca(u_1,v_1)，把上式中的 dis(u_1,v_1) 替换为 dep_{u_1}+dep_{v_1}-2dep_t。记 f_1=dep_{u_1}+dis(u_1,v_1)-2w_1，f_2 同理，整理得 f_1+f_2+dis(v_1+v_2)。

现在问题变为，每条路径 (u,v,w) 会对一些 t 贡献 (u,f) 或者 (v,f')，最后我们在每个 t 处计算一个带权直径问题。

记 L=lca(u,v)。t\in \text{path}(u,L)-\{L\} 会被贡献 (v,f)，t\in\text{path}(v,L)-\{L\} 会被贡献 (u,f')。使用树上差分和线段树合并，我们可以在每个点维护出它被贡献的所有二元组。树上带权直径有经典做法，也可以被线段树维护吗，由于每次 pushup 都需要求 lca，需要 O(1) LCA。

复杂度 (n+m)\log m。

NOI 2019

回家路线

将路线按 p 从小到大 dp，设为 f_i，每次求值前将 q_j\le p_i 的 j ”激活“。

容易发现转移式是类似于斜率优化的式子，每个点维护凸包即可。

时间线性或一只 \log。

机器人

考虑所有柱子中最高的，如有多个选最靠右的，设为 m。 容易发现 m 能走到最左最右。

每次确定 m 的位置，不断递归，等价于一个区间dp的过程。爆搜发现可能转移到的区间个数只有 2000 个。

设 f_{l,r,i} 表示 [l,r] 所有数小于等于 i 的情况数，f_{l,r,i}\leftarrow \sum\limits_{a_m\le j\le \min(b_m,i)} f_{l,m-1,j}\times f_{m + 1, r, j - 1}。

用 a_i,b_i+1 将值域分为若干段，不难发现每段内 f_{l,r,i} 是 i 的 n 次多项式。

因而对于每个 [l,r]，只需要求出 n^2 个位置的值，总时间 O(2000n^2)。

序列

考虑反悔贪心。反悔贪心的本质是先不管限制选尽量优的，然后为了一点点满足限制且每次调整最优的一步。

本题可以先不考虑至少有 L 个下标都被指定，分别选出两个序列中最大的 k 个。

希望设计调整策略使得每调整一步恰好多一个都被指定的下标。

下设 (0/1,0/1) 表示一个下标在两个序列里分别是否选择。

分别用优先队列维护下标选择为某情况下两值的线性组合的最小，最大值。

时间复杂度 O(n\log n)

弹跳

考虑线段树套平衡树优化建图。

询问边不实际建出来，每次 pop 堆顶时直接查即可。

由于 dijk 每次访问更新一个点 dis 后那个点就可以被删掉。因而在平衡树上暴力查即可。

时间复杂度 O(n\log^2n+m\log^2n)，空间复杂度 O(m+n\log n)

斗主地

不难发现一次洗牌即为所有保持两堆牌内部顺序不变的方式中随机一种，我们可以改为求所有方案的和。

设第 i 个位置所有方案之和为 f_i，观察样例或打表猜测任意时刻 f 是二阶等差数列。

我们只需存储第一项，第一个差以及第一个差的差即可。

因而转移只需要算出前三项，是 O(1) 的。

I 君的探险

考虑特殊性质 B （除 0 外每个点恰有一条边连向编号比它小的点）怎么做。

对于单个点，它的父亲是可以二分计算的，然而每次都需要对一个前缀进行 modify，复杂度较高。

不难想到整体二分。假设已知集合 s 的父亲属于 [l,r]，对 [l,mid] 中的点进行 modify：如果一个点属于 [l,mid] 或者状态为 1，递归到左边；否则递归到右边。操作次数 O(n\log n) 且不需要四操作。

如何将这个做法扩展到任意图的情况？随机排列点集，如果一个点向编号比它小的点连出了奇数条边，则我们可以通过上述做法确定其中一条边。当确定一条边时，查看两端点是否仍有邻边未知，如没有则从点集删去。不断重复此流程直到点集为空。注意已知边对点的状态的影响。

复杂度不会证。

NOI 2020

美食家

设 f_{i,j} 表示走了 i 天到 j 的最大收益。转移点只有 f_{i-5...i-1,1...n}，因此可以将状态记为长度为 5n 的向量，转移看成 5n\times 5n 的矩阵 M。

现在只需要能快速处理两次美食节之间的转移就行了，也就是 k 次查询 M 的若干次幂。提前倍增预处理所有 M^{2^i}，查询时用向量乘矩阵即可。

复杂度 O((5n)^3\log T+k(5n)^2\log T)。

命运

容斥，钦定集合 S\subseteq Q 不满足条件。记 t 为没有被 S 中的路径覆盖到的边数，这次钦定的贡献为 (-1)^{|S|}2^t。

考虑通过树形 dp 快速实现容斥的过程。我们让每一条路径在较深的端点处被考虑，设 f_{i,j} 表示以 i 为根的子树已经被考虑了，被钦定不满足条件的路径中，覆盖到的最浅的深度是 j，这样的方案的贡献和。

我们将每个 f_i 用一棵动态开点线段树维护。钦定新路径时只需单点修改单点查询；合并子树时的转移形如 f_{j}g_{k}\rightarrow h_{\max(j,k)}，可以用线段树合并实现。

具体来说，我们需要在线段树上每个节点维护区间和。线段树合并递归到左右儿子之前，先考虑两儿子之间的转移，这只需要打乘法标记即可实现，标记的内容就是另一边的区间和。

时间复杂度 O(n\log n)。

时代的眼泪

查询等价于给定 l,r,x,y，求 \sum\limits_{l\le i\le j\le r}[x\le p_i\le p_j\le y]。

对序列分块，设块长为 B。记 id(i) 表示 i 所在块的编号。

考虑 l,r 在同一个块内的情况。枚举 j，计算 \sum\limits_{l\le i\le j}[x\le p_i\le p_j]。这是一个二维数点，但注意到每块内只有 B 个点，可以对每块预处理所有二维前缀和，时间复杂度 O(nB)\sim O(B)。

对于其它情况，我们可以将 [l,r] 拆成两个散块和若干整块。下面根据 i,j 所在位置讨论。

散块内部：同 l,r 在同一个块内的情况。

散块 - 散块：如果我们能将两个散块分别排序，归并即可求出答案。排序可以通过预处理块内排名后桶排实现。

整块 - 散块：枚举散块中的每个点，对另一个点的限制形如 id(i)\le a,p_i\le b。这个 2-side 数点的第一维是 O(\frac{n}{B}) 的，可以提前预处理。

整块内部：枚举每个整块，注意到在只考虑这块时，x,y 可以被离散化为 O(B) 种信息。那么可能的查询数量就只有 O(B^2) 种，对每块都预处理出来即可。离散化也可以被预处理。

整块-整块：枚举 j 所在整块 b，限制形如 id(i)\le a,id(j)=b,p_i\le p_j\le c。注意到 c 可以被离散化为 O(B) 种信息，而 a,b 都是 O(\frac{n}{B}) 的，可以预处理。

令 B=\sqrt n，总复杂度 O(n\sqrt n+q\sqrt n)。

制作菜品

从 m=n-1 入手，有 d_1...d_{n}=(n-1)k。

反证法易得 $\max d+\min d>k,\min d\le k$。因此我们先用完整的 $\min d$，剩下的用 $\max d$ 的一部分凑。这样恰好用完 $\min d$ 一个原材料。 对 $m\ge n$ 的部分，显然 $\max d\ge k$，用 $\max d$ 做出一道菜品后 $m-n$ 不会增加，可以归纳下去。 对 $m=n-2$，有解的充要条件是可以将 $d$ 划分为两个集合 $f_1,f_2$，且两集合均满足 $\sum\limits_{x\in f} x=(|f|-1)k$，也就是划分为了两个 $m=n-1$ 的子问题。使用 bitset 优化，复杂度 $O(\frac{n^2k}{w})$。 ### 超现实树 考虑四种特殊情况：根没有左儿子，根没有右儿子，根的左儿子是叶子，根的右儿子是叶子。 若想几乎完备，四种树内部必须能几乎完备，也就是只有有限棵这种树不能通过已有的这种树生长得到。如果这个条件满足，其它情况一定只有有限棵不能被生长出来，也就是说这是充要的。 而这四种情况的根总有一个子树是已经确定的了，我们向另一棵子树递归做同样的问题即可。 复杂度和总点数同阶。 ## NOI 2021 ### 轻重边 对于修改操作，新建一个时间戳 $t$，将 $a$ 到 $b$ 路径上每个点的访问时间都设为 $t$。任意时刻，一条边是重边当且仅当两端点时间戳相同。树剖维护即可。 ### 路径交点 若 $k=2$，相当于且邻接矩阵的行列式。 当 $k$ 较大时，可以证明答案是所有矩阵乘起来的行列式。 首先，题目有一个限制是任意两条路径不交。上述结论通过 LGV 引理将有交路径两两抵消，从而保证了这个限制。 现在我们只需证明逆序对数正确，相当于给定三个排列，证明两两逆序对数之和是偶数。归纳或调整易证。 ### 庆典 由于是可达性问题，考虑将图缩点。下文均在缩点后的图上考虑 观察缩点后的图，由题目所给性质，连向同一个点 $z$ 的任意两个点 $x,y$ 之间有边。也就是说，假设连向 $z$ 的点是 $x_1...x_t$，那么 $x_1...x_t$ 的导出子图是一张竞赛图。 因为已经缩点过了，这张竞赛图一定是一条链，不妨设为 $x_1\rightarrow x_2\rightarrow...\rightarrow x_t$。我们只关心可达性，因此可以只保留 $x_t$ 连向 $z$ 的边，将其它边删去。 现在每个点只有一个入度，因此构成外向树森林。 对于新加进来的边，注意到图上的大部分性质都可以原封不动的保留，因此我们将新边的端点作为关键点，建出虚树，虚树上的点也是关键点。 现在我们可以图缩为一张只有 $O(k)$ 个点的新图，每条边表示原来的一条祖孙链，边权为这些 scc 的大小和（新边边权为 $0$）。一条边可以被经过，当且仅当起点可以到达入点，出点可以到达终点。从起点正向 bfs，出点反向 bfs 即可。 复杂度 $O(n+kq\log n)$。 ### 量子通信 注意到 $k_i\le 15$ ，将 $256$ 位的 $01$ 串分为 $16$ 段，每段长度为 $16$。根据鸽巢原理，如果没有受到干扰，原单词至少有一段和收到的串完全相同。 考虑枚举和收到的串完全相同的段，再枚举所有这段完全相同的单词。注意到数据随机，这样的单词期望有 $\frac{n}{2^{16}}$ 个。判断两个单词之间翻转了多少位，需要手写bitset。 复杂度大概是 $O(256n+\frac{nm}{2^{16}}16^2)$。 ### 密码箱 手玩操作二可以发现，若数列的最后一项为 $1$ ，也执行否则的操作，不会改变 $f$ 的值。 观察 $f$ 函数可以发现，在变换的过程中分子分母总是互质的，不需要考虑约分的问题。 $f$ 函数相当于从后向前考虑，维护一个分数 $\frac{x}{y}$，每个操作相当于一个变换，也就是令 $\frac{x}{y}:=\frac{ax+by}{cx+dy}$。将其写成矩阵的形式，我们维护的东西就变为了若干矩阵的乘积。 由于有 reverse 操作，我们需要用平衡树维护整个矩阵序列。 append 操作直接插入即可。对 flip 操作和 reverse 操作，我们需要分别维护一个懒标记。并且，在平衡树上的每个节点，我们不只需要维护其子树内矩阵的乘积，还要维护反转的乘积，翻转的乘积，以及同时反转和翻转的乘积。这样在打标记时直接交换维护好的东西就行了。 ### 机器人游戏 每个机器人的操作序列可以简化为：向右边走 $c_i$ 步，在走 $0...c_i$ 步的每个位置会进行不变 / 反转 / 赋 $0$ / 赋 $1$ 四种操作之一。 考虑容斥，枚举可能的 $p$ 构成的集合 $S$ 。对于每张纸条上的每个位置，它不同的起点出发会得到不同结果。但可能结果只有上述四种。知道了每种结果是否存在一个起点能生成它，就可以快速算这个位置的方案数了。 由于爆炸的机器人需要特殊处理，枚举 $r=\max S$， 现在我们只用考虑 $c_i\le n-r$ 的机器人了。 考虑 dp，设 $f_{i,st,0/1}$ 表示考虑了前 $i$ 个位置，$\max(1,i-(n-r))...i$ 的每个位置是否加入 $S$，以及 $i-(n-r)$ 之前是否有位置被加入 $S$。最后一维状态是因为，如果 $i-(n-r)$ 之前存在位置被加入 $S$ ，那对于这些起点来说这个位置必然不会变。大于 $i$ 的同理，但由于我们已经枚举了 $\max S$，所以并不用担心这个问题。 注意到 $st$ 可以被不超过 $\frac{n}{2}$ 位的二进制数表示，且对所有 $r$，$st$ 总共的可能取值是 $O(2^{\frac{n}{2}})$ 的。瓶颈在计算 $i$ 位置的填法，内层的问题大概是对一个集合的每个子集求内部元素的信息和，容易 $O(1)$ 转移，做到 $O(nm2^{\frac{n}{2}})$。 对于 $i< r$ 的部分，枚举一个机器人， $i$ 位置的填法只和 $r,st$ 有关，可以通过预处理做到 $O((n^2+m)2^{\frac{n}{2}})$。 对于 $i=r$，暴力。 对于 $i>r$ 的部分， $i$ 的填法与 $i$ 有关，不能简单预处理。考虑在 $r$ 从大到小改变的过程中，对每个 $(i,st)$ 维护转移的系数，在 $r:=r-1$ 时只用新考虑 $c_i=n-r$ 的那些机器人。另外，由于 $st$ 可以被不超过 $\min(r,n-i+1)$ 位的二进制数表示，可以证明合法的 $(i,st)$ 的数量也是 $O(2^{\frac{n}{2}})$ 的。 总时间复杂度 $O((n^2+m)2^{\frac{n}{2}})$。 ## NOI 2022 ### 众数 求绝对众数的数据结构题的常见做法是投票法，即每次从整个序列中选两个不同的删掉，绝对众数一定会被剩下，但被剩下的不一定是绝对众数。 本题可以效仿这个做法，对每个序列维护投票法后的结果，但为了检查结果是否是绝对众数我们需要支持查询序列中某个元素出现的次数。不难想到用线段树维护，因为要支持合并因此需要线段树合并。其余操作用链表维护。 时间复杂度 $O(n\log n)$。 ### 移除石子 先考虑 $k=0,l_i=r_i$ 的部分。 我们可以从左到右 dp，将二操作记录进状态里。 设 $f_{i,j,k}$ 表示考虑完 $1...i-1$，左端点在 $i-1$ 前面且右端点在 $i$ 及其后面的二操作有 $j$ 个，左端点在 $i-1$ 且右端点在 $i$ 及其后面的二操作有 $k$ 个。 分析一下状态的上界，不难发现可以做到 $0\le j,k\le 2$，共 $9$ 种。 对于原问题，我们发现恰好 $k$ 个比较难处理。注意到恰好 $k$ 个几乎与至多 $k$ 个等价，唯二的反例是 $k=1,\forall a_i=0$ 和 $k=1,n=3,\forall a_i=1$。 因此我们考虑 dp of dp，每个状态是一个长度为 $9$ 的数组，数组中的每个位置分别记录达到这个状态所需添加的最少石子数。 尽管这个状态的上界是 $102^9$，但搜出来只有 $S=8765$ 种。另一个优化是 $a_i>8$ 与 $a_i=8$ 等价。 我们可以预处理自动机，瓶颈在dp，时间复杂度 $O(9nS)$。 ### 挑战 NPC Ⅱ 考虑一个不断匹配子树并递归的过程。 如果 $G$ 和 $H$ 存在两棵子树相同，我们一定可以直接消掉。因为如果把 $x$ 和 $y$，$y$ 和 $z$ 匹配，一定不如直接把 $y$ 和 $y$ 匹配， $x$ 和 $z$ 匹配。 剩下的情况，如果递归出的子问题 $>1$，一定会让每个子问题中的 $k$ 减小，复杂度也就不证自明了。 关于树哈希，可以考虑先处理子节点的子树的哈希，然后用集合哈希把他们的信息合并。 ### 冒泡排序 容易发现冒泡排序的交换次数就是逆序对数。 对于 “ $a_l...a_r$ 的最小值为 $v$ ” 这样的限制，我们考虑将其拆成两部分：$a_l...a_r\ge v$ 且 $\exist i\in[l,r],a_i=v$。 对于前者，我们可以用 set 维护出每个位置的 $a_i$ 的下界 $lim_i$。 对于后者，我们希望寻找出一种贪心策略使得可以钦定 $v$ 的出现位置。 贪心策略是这样的，我们先将所有区间按照 $v$ 从小到大，若 $v$ 相同按照左端点从右到左排序。依次考虑这个顺序下的每一个区间，将 $v$ 填入 $\min\limits_{i=l...r,lim_i\le v} i$ 的位置。 接下来的问题是没确定的位置的策略。猜一个贪心结论： - 从左到右扫，每个位置填的数是使得当前填好的数的逆序对最小化的值。 事实证明，这个结论是成立的。假设在第 $i$ 个位置，这个填的最优值一定是不小于 $lim_i$ 的数中所有“前面比他小-后面比他小”最大的值。对于这个东西，我们只需维护一个值域线段树，支持单点加减，区间最值。 时间复杂度 $O(n\log n)$。 ### 二次整数规划问题 只考虑 $k=5$ 的情况。 先用第二类约束收紧第一类约束。现在有一些变量已经可以唯一确定了。对于剩下的变量，容易证明它们一定不会取到 $1$ 或 $5$。那么范围就只有 $[2,3],[3,4],[2,4]$ 了。 现在只剩下这样的变量间的第二类约束。$b=0$ 表示两个变量相等；$b=1$ 只有在两个变量的约束都是 $[2,4]$ 时表示不能一个取 $2$ 一个取 $4$；$b\ge 2$ 没有影响。 用 $c_2,c_4$ 表示序列权值，可以得到 $-10^6(c_2-t_1)(c_4-t_2)+t_3$，其中 $t_1,t_2,t_3$ 对一次询问来说是确定的常数。那么也就是要最小化 $(c_2-t_1)(c_4-t_2)$。 将合法的 $(c_2,c_4)$ 看成平面上的点，现在的问题就是整体平移所有点，求 $(c_2-t_1)(c_4-t_2)$ 的最小值。 设 $mn_2,mn_4,mx_2,mx_4$ 分别表示 $c_2,c_4$ 的最小值和最大值，也就是所有没有被唯一确定的变量尽量不取和尽量取的情况。容易证明，$(mn_2,mn_4),(mn_2,mx_4),(mx_2,mn_4)$ 一定是合法的点。 如果存在点出现在第二象限或者第四象限，最小值一定被 $(mn_2,mx_4)$ 或 $(mx_2,mn_4)$ 取到；如果所有点都在第一象限，最小值一定被 $(mn_2,mn_4)$ 取到。 否则，所有点都在第三象限，此时取到最小值的点一定在右上的凸包里。有结论：凸包点数上界是 $O(n^{\frac{2}{3}})$。我们只需要求出这个凸包，暴力查看其中的每个点即可。 考虑分治求凸包，假设我们现在只希望找到凸包上处于 $L,R$ 之间的点（ $L,R$ 也是凸包上的点）。容易证明叉积最大的点是凸包上的点，我们只需要找到他然后分治下去即可。 问题变为，每个变量选 $2,3,4$ 分别有一个代价，还有一些约束，形如两个变量之差不超过某个值，最小化代价和。这是经典的切糕模型，转最大流即可。 据 Itst 的题解，复杂度貌似是 $O(n^{\frac{2}{3}}(n^2\log n+nm+q))$。