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)\)。  

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

分析

构造方法是：

1.  对于每个点，随机选择一个比其标号小的点作为父亲，生成一棵**递增标号树**。

2. 对上述树的标号打乱。

不难想到，第一步产生的数则种类有 $\prod_{i=2}^{N} (i-1)$ 个，第二步的排列数有 $N!$ 个可能。所以，总方案数为：

$$\prod_{i=2}^{N} (i-1) \times N!$$

关键点来了：有多少种情况可以生成这个树。反向考虑这棵树能怎么生成，也就是存在一种情况得到了一个递增树和一个排列，可以得到这个树。显然，如果一个递增树可以加上某个排列形成这棵树，那么这个排列是唯一确定的。那么，任意一个与输入的树结构相同的递增标号树都可以得到这个树，做一个贡献。如何计算这个贡献？首先，由定义可知 `1` 号节点一定是根，令其 $k$ 个子节点的子树大小分别为 $s_1, s_2, \dots, s_k$，则每个子树分配点集方案树为

$$C_{n-1}^{s_1} \times C_{n-1-s_1}^{s_2} \times \dots \times C_{n-1-\sum_{i=1}^{k-1} s_i}^{s_k}$$

化简可得

$$\frac{N!}{s_1! \times s_2! \times \dots \times s_k!}$$

每个子树同样满足这个标号规则，令 $f(T)$ 为以 $T$ 为根的子树的方案，则：

$$f(T) = \frac{N!}{\prod s_i!} \times \prod f(子树i)$$

展开，化简可得：

$$f(T) = \frac{N!}{\prod sz_u}$$

其中，$sz_u$ 表示树上每个节点的子树大小。这样子我们可以求出来一个节点为根的方案树，接下来我们需要换根。

令 $f_u = \frac{N!}{\prod sz_x},\quad f_v = \frac{N!}{\prod sz'_x}$，从 $u$ 到 $v$ 只会有以下树改变：

$$sz_u = N,\quad sz_v = sz_v$$

$$sz_u' = N-sz_v,\quad sz_v'=N$$

分母产生的变化

$$D_u=(\prod_{x \ne u,v} sz_x) \times N \times sz_v$$

$$D_v = (\prod_{x\ne u,v} sz_x) \times (N-sz_v) \times N$$

比一下，

$$\frac{f_v}{f_u} = \frac{D_u}{D_v} = \frac{N \times sz_v}{(N-sz_v) \times N} = \frac{sz_v}{(N-sz_v)}$$

所以，$f_v = f_u \times \frac{sz_v}{(N-sz_v)}$。

之后我们将其求和，得到总答案数，再逆元除以总情况数即可。

参考代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int hd[N], nxt[N * 2], to[N * 2], num = 1;
void add(int u, int v) {
    num++;
    to[num] = v;
    nxt[num] = hd[u];
    hd[u] = num;
}
int sz[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
long long fpow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
int n;
long long f[N];
void dfs2(int u, int fa) {
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        f[v] = f[u] * sz[v] % mod * fpow(n - sz[v], mod - 2) % mod;
        dfs2(v, u);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        num = 1;
        memset(hd, 0, sizeof(hd));
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs(1, 0);
        long long fz = 1;  // 分子
        for (int i = 1; i <= n; i++) {
            fz = fz * i % mod;
        }
        long long fm = 1;  // 分母
        for (int i = 1; i <= n; i++) {
            fm = fm * sz[i] % mod;
        }
        f[1] = fz * fpow(fm, mod - 2) % mod;
        dfs2(1, 0);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += f[i];
            ans %= mod;
        }
        fm = 1;
        for (int i = 1; i <= n - 1; i++) fm = fm * i % mod;
        for (int i = 1; i <= n; i++) fm = fm * i % mod;
        cout << ans * fpow(fm, mod - 2) % mod << endl;
    }
    return 0;
}

[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 创建题解