Sol 1

我们从左往右扫描离散化出来的线段 $i$（设当前点权为 $v_i$）。维护一个集合 $S$，表示覆盖这条线段的区间的编号。

对于一个询问 $[L,R]$ 若 $f(L,R)$ 包含这条线段，则存在 $x\in S$ 满足 $x\in [L,R]$。

不妨倒过来，对于当前的 $x\in S$，我们让所有满足 $L\le x,R\ge x$ 的二维点 $(L,R)$ 加上点权 $v_i$。

这样显然会算重，因为可能存在  $x,y\in S,x,y\in [L,R]$，这样 $v_i$ 就被算两次以上了。

考虑去重，对于一个询问 $[L,R]$ 让最小的符合条件的 $x$ 产生贡献，即如果同时存在两个 $x,y\in S$ 产生正贡献，就产生一次负贡献。

具体的，我们用 set 来维护 $S$，每次找到 $x$ 的前倾 $y$，让所有满足 $L\le y,R\ge x$ 的二维点 $(L,R)$ 加上点权 $-v_i$。

我们对于每一个线段都要这样做一次，复杂度就爆炸了，考虑对于每一个元素统一算贡献。

考虑第一类正贡献，设 $x$ 在第 $p$ 条线段加入 $x$，第 $q+1$ 条线段离开 $x$。则对所有 $L\le x,R\ge x$ 的点加上 $\sum_{i=p}^q v_i$。

对于第二类负贡献，我们也可以记录每一对前倾后继产生的时间区间 $[p,q]$，然后减去负贡献即可。在加入新的前倾后继关系。

于是我们转化到这样一个问题：

1. 给定若干 $(x,y,v)$，将所有 $L\le x,R\ge y$ 的点 $(L,R)$ 加上 $v$。（这一类操作的数量是 $O(n)$ 的）。

2. 查询满足 $A\le L\le R\le B$ 的所有点权之和。

不妨考虑一个操作 $(x,y,v)$ 对 $[A,B]$ 的贡献，为 $(x-A+1)(B-y+1)v$，令 $A'\gets A+1,B'\gets B+1$，则 $(x-A)(B-y)v=(Ay+Bx-AB-xy)v$。

因为 $A',B'$ 可以看作常数，所以我们做离线二维数点，同时维护 $\sum v,\sum xv,\sum yv,\sum xyv$ 即可。

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

Sol 2

将 $[l_i,r_i]$ 称为区间，$[A,B]$ 称为询问。扫描区间的下标。

设当前扫到了 $R$，则当前数组 $v_i$ 表示 $f(i,R)$。则当 $R=B$ 时查询 $[A,B]$ 就是询问所有 $i\in [A,B],v_i$ 的历史和。

考虑如何维护扫描过程中 $v_i$，设 $1\sim R$ 的所有区间中最后一个覆盖线段 $i$ 个编号是 $p_i$，则当前线段 $i$ 会对 $v_{1\sim p_i}$ 做贡献。

每次扫描线的右端点移动，新加入一个区间，会改变一些 $p_i$，设原来 $p_i=x$，后来 $p_i=y$，则这次移动会对 $v_{x+1\sim y}$ 新产生贡献。

每次都是覆盖一段区间，可以用珂朵莉树维护，改变一个颜色段的 $p_i$ 可以用一次区间加完成，而这样的区间加只有 $O(n)$ 次。

然后选择心怡的维护历史和的方法即可，例如维护当前完成的操作数 $T$，当前数组 $A$，设历史和数组为 $B$，再维护一个 $C_i=B_i-A_iT$，则只维护 $A,C$ 即可维护 $B$。

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

设往左走的获胜的概率为 $A$，往右走的获胜的概率为 $B$

不难发现，最终的方案里，一定存在一个分界点，分界点左侧的点往左走，右侧点往右走。

特判掉 $a=0,b=0$ 的情况，两侧的问题可以对称为一个子问题。以左侧问题为例。

先枚举一个前缀 $n'$。考虑一个贡献延后计算的东西，维护一个栈，从后往前 dp，每次遇到 $L$ 就塞进栈，遇到 $R$ 就随机栈顶的几个 $L$。最后希望栈里有 $a$ 个 $L$。

设 $f_{i,j}$ 表示考虑了 $i\sim n'$，其中还剩下 $j$ 个 $L$ 在栈里，不难列出转移式：

$$f_{i,j}=\begin{cases}f_{i+1,j-1} & s_{i}=L \\ f_{i+1,j+x}\times B^x\times A & s_{i}=R\end{cases}$$

第二个转移式子表示一个 $R$ 连续击败了 $k$ 个 $L$ 后被一个 $L$ 击败，注意转移中间 $j=0$ 的情况是非法的，需要特判掉。

但是因为我们最终计算答案要枚举分界点，而我们目前的 dp 是确定了一个前缀后再从后往前 dp，考虑到过来，确定了一个前缀后再从前往后 dp。

倒过来后，不难发现我们是让一些 $R$ 和后面的 $L$ 去匹配，但是有 $a$ 个 $L$ 没有匹配，我们把这些没有匹配的 $L$ 放在一边。

设 $f_{i,j}$ 表示考虑了 $1\sim i$ 还有 $j$ 个 $L$ 能放在一边。然后转移都反过来即可。

最后发现转移的这个 $k$ 很没用，用前缀和优化掉即可，时间复杂度为 $O(n^2)$。

# 1 冒泡排序(bubble)

相信大家做过今年的 NOI（2018）。  

众所周知，排列合法当且仅当最长下降子序列不超过 $2$。  

为了方便我们将最长下降子序列的限制变成最长上升子序列的限制。  

特别地 $( a+b=n-1)$ 的情况。  

当 $( a+b<n-1)$ 时，可以将序列和值域都反转，$( a' = n - a - 1, b' = n - b - 1 )$。  

将 \((i, p_i)\) 在平面上画出来，(a, b) 将平面分成了四个区域，不难发现左下和右上不能同时有点。  

假设左没有点，那么左上有 \( a \) 个点，右下有 \( b \) 个点，右上有 \( n - 1 - a - b < 0 \) 个点，不合法。  

不难发现左下的点一定是单调递减的，可以将问题划分成下方和左方两个子问题，相当于要解决 \( b = n - 1 \) 的情况。  

一个合法的序列可以唯一对应一条从 \((0, n)\) 到 \((n, 0)\) 的路径，满足任意时刻 \( x + y \leq n \)，路径长成 \( f(x) = \min_{x \leq y} p_x \) 的形式。  

那么 \( b = n - 1 \) 的情况相当于一个长度为 \( b \) 的合法序列，前 \( a \) 个位置都是前缀最小值。  

前 \( a \) 个位置假设往下走了 \( t(t \geq a) \) 步，  

前面就是方程 \( x_1 + x_2 + x_3 + \cdots + x_a = t \) 的正整数解的个数，就是 $C_{t-1}^{a-1}$。  

后面是从 \((a, b - t)\) 走到 \((b, 0)\) 的方案数，是 $(C_{2b-a-t}^{b-a} - C_{2b-a-t}^{b-a+1})$。  

组合解是相当于从 \( 2b - a \) 个数里面选 \( b \) 个，以第 \( a \) 个数为分界线，枚举左右各有多少个数。  

同理 \(\sum_t C_{t-1}^{a-1} C^{2b-a-t}_{b-a+1} = C_{2b-a}^{b+1}\)。  

对于左方的子问题，将值和值域倒过来就变成下方的子问题了。  

但是这是 NOIP 模拟，所以肯定有更简单的做法。  

我们算左下没有点的情况，那么注意到 \((a, b)\) 这个位置是前缀最小值，那么考虑统计前缀最小值序列个数。  

还是用路径来刻画这个东西，可以发现这个限制等价于 \((a, b)\) 这里的路径是这样走的：\((a, b + 1) \to (a, b) \to (a + 1, b)\)。  

那么两边分开了，用折线法算方案数就行了。

[CSP 2024 J & COGS 4052] 接龙

  注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题却受到伤害！！！）

 引入

  有 \(n\) 个人，每个人手里有一个数字序列（词库）。玩一个接龙游戏：

- 第 \(1\) 轮：可以从任意一个人的序列中，选一个长度在 \([2, k]\) 之间的连续子序列，且子序列的第一个数必须是 \(1\)

- 第 \(2\) 轮及以后：选的子序列的第一个数，必须等于上一轮子序列的最后一个数，且不能连续两轮用同一个人的序列

有 \(q\) 个询问，每个询问给两个数 \(r\) 和 \(c\)，问能否恰好用 \(r\) 轮接龙，让最后一轮的最后一个数字是 \(c\)

分析

  这道题如果直接模拟，复杂度会非常高。需要一种高效的方法来判断“可行性”。

正解采用动态规划加滑动窗口的思路：

  状态定义：\(dp[r][x]\) 表示能否在 \(r\) 轮内，以数字 \(x\) 作为结尾

- \(dp[r][x] = -1\)：不可行

- \(dp[r][x] = i\)：可行，且最后一轮是由第 \(i\) 个人完成的

- \(dp[r][x] = 0\)：可行，且有多个人都能完成（用于后续判断）

  状态转移：从 \(dp[r-1][y]\) 到 \(dp[r][x]\)

- 如果存在某个人 \(i\)，他的序列中有以 \(y\) 开头、长度在 \([2,k]\) 内的子序列，且以 \(x\) 结尾

- 且 \(dp[r-1][y]\) 不是由 \(i\) 完成的（不能连续两轮用同一个人）

- 那么 \(dp[r][x]\) 就是可行的

  优化方法：

- 用滑动窗口在每个序列中快速找到所有可能的（开头，结尾）对

- 用 \(cnt\) 记录当前正在构建的子序列长度

后记

 1. 为什么 \(cnt\) 这样工作？

当遇到一个可以作为开头的数字时，我们允许它后面最多接 \(k-1\) 个数。\(cnt\) 就是“还能接几个数”的计数器。每遍历一个数，如果 \(cnt>0\)，说明当前数可以作为某个子序列的结尾，然后 \(cnt\) 减一。

 2. \(dp[r][x]\) 的三个值含义

- \(-1\)：不可行

- \(i\)：可行，且最后一轮是第 \(i\) 个人完成的（唯一）

- \(0\)：可行，但有多个人都能完成（用于判断不能连续两轮同一个人）

 3. 为什么最后要取 \(tot\) 的最大值？

因为数字的范围可能很大（\(10^9\)），但实际出现的数字有限。只开 \(tot+2\) 的数组，避免内存过大。

 复杂度分析

轮数 \(\leq 100\)，总序列长度 \(\leq 2\times 10^5\)，总复杂度 \(O(100 \times \text{总长度})\)，可以接受。

 注意事项

1. 读入要用 \(ios::sync\_with\_stdio(0);cin.tie(0);\) 加速

2. 文件输入输出不要忘：\(freopen\)

3. dp 数组要用 vector 动态分配，避免内存过大

更新日志：

2026.3.20 创建题解

[Nescafé 18&COGS 1045] 七夕祭 题目解析

    注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题却受到伤害！！！）

  引入

       你有一个 \(N \times M\) 的矩形网格，其中 \(T\) 个格点是“感兴趣的”。你可以交换相邻的格点（左右相邻或上下相邻，且每行/列的首尾也算相邻，即环形）。目标是用最少的交换次数，同时满足两个条件：

1. 行均等：每一行感兴趣的格点数相同。

2. 列均等：每一列感兴趣的格点数相同。

这是一个典型的环形均分问题。核心思想是：行列独立，可以分别求解。

分析

第 1 步：数据统计与可行性预判

统计行和：设第 \(i\) 行有 \(R_i\) 个感兴趣的格点，则 \(\sum_{i=1}^{N} R_i = T\)。

统计列和：设第 \(j\) 列有 \(C_j\) 个感兴趣的格点，则 \(\sum_{j=1}^{M} C_j = T\)。

 预判可行性：

行方向可行的条件是 \(T\) 能被 \(N\) 整除。此时每行的目标数为 \(\text{avg}_R = \frac{T}{N}\)。

列方向可行的条件是 \(T\) 能被 \(M\) 整除。此时每列的目标数为 \(\text{avg}_C = \frac{T}{M}\)。

第 2 步：将行/列问题转化为一维环形均分问题

以行方向为例，我们得到了一个环形排列的数列 \([R_1, R_2, ..., R_N]\)，需要通过相邻交换（环形），使每个数都变成目标值 \(\text{avg}_R\)。这本质上是一个货物搬运问题。

转化：

我们定义一个“偏差”数组 \(A_i = R_i - \text{avg}_R\)。问题变成了：通过相邻搬运，使所有 \(A_i\) 变为 0。最终答案是所有搬运的“工作量”之和。

第 3 步：求解一维环形均分问题（数学推导）

设从第 \(i\) 个位置搬运到第 \(i+1\) 个位置的货物量为 \(x_i\)（可正可负，正表示向右搬，负表示向左搬）。那么，对于每个位置，经过搬运后，其偏差应该被消除：\(A_i + x_{i-1} - x_i = 0\)

其中 \(x_0\) 表示从第 \(N\) 个位置到第 \(1\) 个位置的搬运量（因为是环形）。整理得：\(x_i = A_i + x_{i-1}\)

这是一个递推关系。令 \(x_0 = k\)，则可以推出：

\(x_1 = A_1 + k\)

\(x_2 = A_2 + x_1 = A_1 + A_2 + k\)

\(x_3 = A_1 + A_2 + A_3 + k\)

...

 \(x_i = S_i + k\)

其中 \(S_i = \sum_{j=1}^{i} A_j\) 是前 \(i\) 个偏差的前缀和（注意，这里的 \(A_j\) 已经减去平均值，所以整个数列的总和为0，即 \(S_N = 0\)）。

我们的目标是最小化总运输量 \(\sum_{i=1}^{N} |x_i| = \sum_{i=1}^{N} |S_i + k|\)。

问题的几何意义：我们需要找到一个实数 \(k\)，使得数轴上的一系列点 \([-S_1, -S_2, ..., -S_N]\) 到点 \(k\) 的距离之和最小。

数学结论：使距离和最小的点 \(k\) 是这些点坐标的中位数。

第4步：计算最小交换次数

1.  根据第 2 步得到偏差数组 \(A_i\)。

2.  计算其前缀和 \(S_i = A_1 + A_2 + ... + A_i\)，得到一个长度为 \(N\) 的数组 \([S_1, S_2, ..., S_N]\)。

3.  对这个前缀和数组进行排序，找到它的中位数 \(m\)。

4.  最小交换次数即为 \(\sum_{i=1}^{N} |S_i - m|\)。

Ps：这个计算出的次数，实际上是“货物搬运的总量”。因为每次交换（相邻位置）只能搬运“1个单位”的货物，所以这个总量就等于最少的交换次数。

列方向的处理方法与行方向完全相同，只是将 \(N\) 换成 \(M\)，将 \(R_i\) 换成 \(C_j\)。

最终答案

1. 如果两个方向都可行，输出 both 和行与列次数之和。

2. 如果只有行可行，输出 row 和行的次数。

3. 如果只有列可行，输出 column 和列的次数。

4. 如果都不可行，输出 impossible。

代码如下

#include<bits/stdc++.h>
#define MAXN 100010
#define ll long long
using namespace std;

ll n1,m,t;
ll r[MAXN],c[MAXN],s[MAXN];

ll calc(ll n,ll a[],ll ta)
{
	for(int i=1;i<=n;++i) s[i]=s[i-1]+(a[i]-ta);
	sort(s+1,s+n+1);
	ll mid=s[(n+1)/2];
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=abs(s[i]-mid);
	return ans;
}

int main()
{
	freopen("tanabata.in","r",stdin);
	freopen("tanabata.out","w",stdout);
	cin>>n1>>m>>t;
	memset(r,0,sizeof(r));
	memset(c,0,sizeof(c));
	for(int i=1;i<=t;++i)
	{
		int x,y;
		cin>>x>>y;
		r[x]++; c[y]++;
	}
	bool okr=!(t%n1),okc=!(t%m);
	if(okr&&okc)
	{
		ll rans=calc(n1,r,t/n1);
		ll cans=calc(m,c,t/m);
		cout<<"both "<<rans+cans<<endl;
	}
	else if(okr)
	{
		ll rans=calc(n1,r,t/n1);
		cout<<"row "<<rans<<endl;
	}
	else if(okc)
	{
		ll cans=calc(m,c,t/m);
		cout<<"column "<<cans<<endl;
	}
	else cout<<"impossible"<<endl;
	return 0;
}

更新日志：

2026.3.14 创建题解

2026.3.16 格式修改