四份标程均放在 std/ 下（std/football.cpp、std/sakuzyo.cpp、std/vex.cpp、std/modulo.cpp），并已完整附在每题末尾，可直接复制提交；均已用下发数据验证通过（10/10、20/20、20/20、20/20）。

T1 足球乱斗 football

题意

$2n$ 支队伍两两配成 $n$ 场（每队恰好打一场），第 $i$ 队已有 $p_i$ 分。每场可以平局（双方各 $+1$），也可以分出胜负（胜者 $+3$、负者 $+0$）。比赛结束后，排名 = 1 + 分数严格大于自己的队伍数（同分并列最高名次）。对每支队伍，求它可能取得的最好（最小）名次。

分析

先固定要看的那支队伍 $x$，设它的对手是 $y$。

第一步：$x$ 一定应该赢。 赢下比赛会让 $x$ 拿到最多分 $p_x+3$，同时把对手压在最低分 $p_y$，这两个方向都只会让 $x$ 的名次更好。于是令

$$S=p_x+3 .$$

$x$ 自己的分数确定为 $S$，对手确定为 $p_y$。剩下 $n-1$ 场比赛涉及的都是别的队伍，且彼此不共用队伍，所以它们互相独立：只要让每场"分数超过 $S$ 的队伍数"尽可能小，加起来就是全局最小。

第二步：单场比赛的最小代价。

设一场比赛两队当前分数为 $a\le b$。三种结果为

$$(a+3,\;b),\qquad (a,\;b+3),\qquad (a+1,\;b+1).$$

记

$$M=\min\bigl(\max(a+3,b),\;b+1\bigr),$$

则

$$\boxed{\text{cost}(S)=[a>S]+[M>S]}.$$

证明. $M$ 恰好是"这场比赛两队最终得分的较大值"能取到的最小值（三种结果的较大值分别为 $\max(a+3,b)$、$b+3$、$b+1$，其中 $b+1

$\blacksquare$

第三步：统计。 对每场比赛 $e$（该场两队记为 $u,v$）先记三个数

$$a_e=\min(p_u,p_v),\qquad b_e=\max(p_u,p_v),\qquad M_e=\min\bigl(\max(a_e+3,b_e),\;b_e+1\bigr).$$

令 $\mathrm{cntA}[v]$ 为 $a_e=v$ 的比赛场数、$\mathrm{cntM}[v]$ 为 $M_e=v$ 的比赛场数，对值域作前缀和，得到

$$\mathrm{preA}(S)=\#\{e: a_e\le S\},\qquad \mathrm{preM}(S)=\#\{e: M_e\le S\}$$

（这里 $\#$ 表示集合的基数，即满足条件的比赛场数，而不是队伍数）。因为单场有

$$[a_e>S]+[M_e>S]=\bigl(1-[a_e\le S]\bigr)+\bigl(1-[M_e\le S]\bigr)=2-[a_e\le S]-[M_e\le S],$$

把 $n$ 场加起来，即得所有比赛的最小代价之和

$$\boxed{F(S)=\sum_{e}\bigl([a_e>S]+[M_e>S]\bigr)=2n-\#\{e: a_e\le S\}-\#\{e: M_e\le S\}}$$

其中 $2n$ 是基数（$n$ 场比赛共 $2n$ 支队）；减去的两项分别数的是满足 $a_e\le S$ 的场数、满足 $M_e\le S$ 的场数。

例（样例 1）：两场比赛的 $(a_e,M_e)$ 分别为 $(0,5)$、$(2,3)$。取 $S=3$ 时 $\#\{e:a_e\le 3\}=2$、$\#\{e:M_e\le 3\}=1$， 故 $F(3)=4-2-1=1$，与逐场计算 $([0>3]+[5>3])+([2>3]+[3>3])=1$ 一致。

对队伍 $x$：把"自己那场"从 $F(S)$ 里减掉，换成强制获胜的代价 $[p_y>S]$，答案即

$$\text{ans}_x=F(p_x+3)-\bigl([a_e>S]+[M_e>S]\bigr)+[p_{\text{opp}(x)}>S]+1,$$

其中 $e$ 是 $x$ 参加的那场比赛。减掉的 $[a_e>S]+[M_e>S]$ 是"这场可以自由选择结果"时的最优代价；加上的 $[p_{\text{opp}(x)}>S]$ 是强制 $x$ 获胜后、只有对手可能超过 $S$ 的代价。代入样例 1 的队伍 $3$：$F(3)=1$，减去自己那场的 $1$，加上 $[p_2=5>3]=1$，再加 $1$，得 $2$，与样例输出一致。

复杂度

$O(n+\max p_i)$ 时间、$O(n+\max p_i)$ 空间。数据范围 $p_i\le 5\times10^5$，前缀和数组完全开得下。

实现要点

• 同分取最高名次，也就是"排名 = 1 + 严格大于自己的队伍数"，不需要再做任何并列处理。
• $S$ 恒有 $S\le \max p_i+3$，注意前缀和数组开到 $\max p_i+10$。

标程

完整代码（同时见 std/football.cpp）：

/* 足球乱斗 football
 *
 * 共 n 场比赛、2n 支队伍，每队恰好打一场（比赛构成一个完美匹配）。
 * 胜 +3、平 +1。排名 = 1 + 分数严格大于自己的队伍数。
 *
 * 对固定的队伍 x，最优策略显然是赢下自己那场：这样 x 最终得
 * S = p[x] + 3，对手停在 p[y]，既让 x 的分最高，也让 y 的分最低。
 *
 * 其余比赛互不相交，因此对阈值 S，记
 *      cost(某场比赛) = 该场两队中最终分数 > S 的队数的最小可能值，
 * 则 x 的答案为 1 + 其余各场 cost 之和 + [p[y] > S]。
 *
 * 对一场初始分为 a <= b 的比赛，三种结果是
 *      (a+3, b) , (a, b+3) , (a+1, b+1)
 * 逐情况讨论可知
 *      cost = [a > S] + [M > S],   M = min(max(a+3,b), b+1)
 * 其中 M 是“该场两队最终得分的较大值”能取到的最小值。
 *
 * 于是令 cntA[v] = a == v 的比赛数、cntM[v] = M == v 的比赛数，则
 *      F(S) = 所有比赛 cost 之和 = 2n - cntA(<=S) - cntM(<=S)
 * 对队伍 x：
 *      ans = F(S) - cost_own(S) + [p[opp[x]] > S] + 1 .
 *
 * 复杂度 O(n + max p)。
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("football.in", "r", stdin);
    freopen("football.out", "w", stdout);

    int n;
    if (scanf("%d", &n) != 1) return 0;
    int m = 2 * n;
    vector<int> p(m);
    int maxp = 0;
    for (int i = 0; i < m; ++i) {
        scanf("%d", &p[i]);
        if (p[i] > maxp) maxp = p[i];
    }

    vector<int> opp(m), eid(m);
    vector<int> ea(n), em(n);
    for (int i = 0; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        opp[u] = v; opp[v] = u;
        eid[u] = i; eid[v] = i;
        int a = min(p[u], p[v]), b = max(p[u], p[v]);
        ea[i] = a;                              // 该场比赛的 a
        em[i] = min(max(a + 3, b), b + 1);      // 该场比赛的 M
    }

    int MAXV = maxp + 10;
    vector<int> cntA(MAXV + 1, 0), cntM(MAXV + 1, 0);
    for (int i = 0; i < n; ++i) { cntA[ea[i]]++; cntM[em[i]]++; }
    vector<int> preA(MAXV + 1), preM(MAXV + 1);     // 值域前缀和
    preA[0] = cntA[0]; preM[0] = cntM[0];
    for (int v = 1; v <= MAXV; ++v) {
        preA[v] = preA[v - 1] + cntA[v];
        preM[v] = preM[v - 1] + cntM[v];
    }

    for (int x = 0; x < m; ++x) {
        int y = opp[x], e = eid[x];
        int S = p[x] + 3;                       // x 获胜后的最终分数
        int costOwn = (ea[e] > S ? 1 : 0) + (em[e] > S ? 1 : 0);
        int F = 0;
        if (S <= MAXV) F = 2 * n - preA[S] - preM[S];
        int over = F - costOwn + (p[y] > S ? 1 : 0);
        printf("%d%c", over + 1, x + 1 == m ? '\n' : ' ');
    }
    return 0;
}

T2 削除射线 sakuzyo

题意

给定只含 y l q 的串 $s$。只要存在子串 ylq 就可以对它发射一次射线：设这个 y 当前下标为 $p$（$0$ 开始），

• $p$ 为偶数（y 前面有偶数个字符）：删掉中间的 l；
• $p$ 为奇数：删掉 y 和 q。

删除后两端拼起来。求最多能发射多少次。

分析

1. 块分解

操作永远不会让两个 l 相邻（A 类操作把左右两块拼接，而触发它的前提是两侧恰好是 y、q，两块都非空），也不会在 l 之间插入字符。因此可以一直把串看成

$$B_0\;l_1\;B_1\;l_2\;B_2\;\cdots\;l_k\;B_k,\qquad B_i\in\{y,q\}^* .$$

（原本就相邻的两个 l 中间那块为空，这两个 l 永远无法参与操作，当成"墙"即可，下面的式子会自动给出 $0$ 预算。）

2. 每个 l 的"私有预算"

对 $l_i$ 定义

• $Y_i$：$l_i$ 左边紧挨着的连续 y 的个数（即 $B_{i-1}$ 的 y 后缀长度）；
• $Q_i$：$l_i$ 右边紧挨着的连续 q 的个数（即 $B_i$ 的 q 前缀长度）。

一次 B 类操作（删 y 和 q）会吃掉 $l_i$ 左边的一个 y 和右边的一个 q；一次 A 类操作（删 l）什么都不吃，但 $l_i$ 就此消失。

关键事实：

• $B_{i-1}$ 的右端只可能被 $l_i$ 自己的 B 操作吃掉，$B_i$ 的左端只可能被 $l_i$ 自己的 B 操作吃掉，别的 l 碰不到；
• A 操作把两块拼起来时，是把 $B_{i-1}$ 接到 $B_i$ 左边，$B_{i-1}$ 的右端和 $B_i$ 的左端都不会改变；
• $B_i$ 的 q 前缀和 y 后缀不会重叠（一个位置不可能既是 q 又是 y）。

于是每个 $l_i$ 拥有互不干扰的预算 $(Y_i,Q_i)$，并且

$$\text{对 }l_i\text{ 的 B 操作数 }b_i\le \mathrm{cap}_i:=\min(Y_i,Q_i);\qquad \text{若还要做一次 A 操作，则 } b_i<\mathrm{cap}_i .$$

3. 位置奇偶：A 操作是"解锁定"的货币

设 $\mathrm{pos}(l_i)$ 为 $l_i$ 的当前下标。触发它的 y 在 $\mathrm{pos}(l_i)-1$：

• $\mathrm{pos}(l_i)$ 为奇数 $\Rightarrow$ 只能做 A；
• $\mathrm{pos}(l_i)$ 为偶数 $\Rightarrow$ 只能做 B。

$\mathrm{pos}$ 的奇偶只在两种情况下翻转：

• 在 $l_i$ 左边做了一次 A 操作（删掉一个 l，后面的字符整体左移 $1$）；
• 在 $l_i$ 自己身上做了一次 B 操作（删掉左边那个 y，自己左移 $1$）。

其余操作（左边的 B 操作删掉 $2$ 个字符、右边的一切操作）都不影响 $\mathrm{pos}(l_i)$ 的奇偶。

记 $t_i$ 为 $l_i$ 原下标的奇偶。设左边一共已做过 $c$ 次 A、自己身上已做过 $b$ 次 B，则当前 $\mathrm{pos}$ 为奇数当且仅当

$$t_i\oplus(c\bmod 2)\oplus(b\bmod 2)=1 .$$

由此：

• 第 $r\ (r=1,2,\dots)$ 次 B 操作要求 $c\equiv t_i+(r-1)\pmod 2$；
• 最后那次 A 操作要求 $c\equiv t_i+b_i+1\pmod 2$。

推论：若 $l_i$ 左边一共做了 $C$ 次 A 操作，可以把这 $C$ 次 A 操作当成 $C$ 个"把奇偶翻转一次"的名额，逐个穿插到 $l_i$ 的 B 操作之间，从而把 B 操作一个个"解锁"。于是

（特殊情况：$t_i=0,b_i=0$ 的 A 操作要求 $C\ge 1$，即必须先有左边的 A 操作把奇偶翻过来。）

4. 贪心：从左往右，能消 l 就消 l

按 $l$ 在原串中从左到右的顺序处理，维护 $C=$ 已经做过的 A 操作总数。对每个 $l_i$（$\mathrm{cap}_i=\min(Y_i,Q_i)$）：

• $\mathrm{cap}_i=0$：永远用不了，跳过。
• $t_i=1$：取 $b=\min(\mathrm{cap}_i-1,\,C)$，做 $b$ 次 B 和 $1$ 次 A，答案 $+=b+1$，$C\mathrel{+}=1$。
• $t_i=0$：
  • $\mathrm{cap}_i\ge 2$：取 $b=\min(\mathrm{cap}_i-1,\,C+1)$，答案 $+=b+1$，$C\mathrel{+}=1$；
  • $\mathrm{cap}_i=1$：若 $C\ge 1$ 就做那一次 A（答案 $+=1$，$C\mathrel{+}=1$）；若 $C=0$ 只能做一次 B（答案 $+=1$，$C$ 不变）。

为什么"能做 A 就做 A"最优？ 比较两种选择能拿到的操作数：

• $t_i=1$：做 A 得 $\min(\mathrm{cap}_i,C+1)$，不做 A 得 $\min(\mathrm{cap}_i,C)$；
• $t_i=0$：做 A 得 $\min(\mathrm{cap}_i,C+2)$，不做 A 得 $\min(\mathrm{cap}_i,C+1)$。

做 A 从不比不做 A 差，而且会把 $C$ 变大，而 $C$ 越大，后面每个 $l$ 的上限只会更松。因此"只要 A 合法就做 A"是全局最优的贪心。

反例：为什么"先尽量消 yq"是错的

一个很自然的贪心是优先做 B 操作（消 y、q），做不动了再消 l。它看起来很划算（B 操作不吃掉 l，还顺手删掉两个字符），但是错的。例如

ylqylqyyylqqq     正确答案 5，该贪心得 4

一组最优操作序列：

ylqylqyyylqqq  --在下标0的 ylq 上做 A，删掉下标1的 l-->  yqylqyyylqqq
              --在下标7的 ylq 上做 B，删掉下标7的 y 和下标9的 q-->  yqylqyylqq
              --在下标2的 ylq 上做 A，删掉下标3的 l-->  yqyqyylqq
              --在下标5的 ylq 上做 B，删掉下标5的 y 和下标7的 q-->  yqyqylq
              --在下标4的 ylq 上做 A，删掉下标5的 l-->  yqyqyq

一共 $5$ 次。而优先做 B 会先消掉下标 $3$ 的 ylq，把后面能用的 y 提前耗掉，只能得到 $4$ 次。用这种"优先消 yq"的贪心实测会在第 $10$、$13\sim17$ 号点挂掉（共 $30$ 分），这也是本题大部分"模拟 + 贪心"做法拿不到满分的原因。

复杂度

每个 l 扫一次、O(1) 转移，总复杂度 $O(|s|)$。

实现要点

• $Y_i,Q_i$ 用两个后缀/前缀数组预处理："以 $i$ 结尾的连续 y 长度"和"以 $i$ 开头的连续 q 长度"。
• $t_i$ 一定要用 原串下标 的奇偶，不是当前下标；当前下标的奇偶变化已经全部折算进 $C$ 里了。
• 答案最大只有 $|s|$ 量级，但中途 $C$ 会到 $O(|s|)$，用 long long 更稳。

标程

完整代码（同时见 std/sakuzyo.cpp）：

/* 削除射线 sakuzyo
 *
 * 标准程序：O(n)
 *
 * 关键观察
 * ========
 * 两种操作都只会删除「当前处于奇数位置」的字符，因此可以始终把串看成
 *
 *        B0 l1 B1 l2 B2 ... lk Bk        （Bi 是由 {y,q} 组成的块）
 *
 * 对 l_i 而言，只有 B_i 的 q 前缀（被 l_i 从右边吃掉）和 B_{i-1} 的
 * y 后缀（被 l_i 从左边吃掉）是可达的：两段互不重叠，也不会被其它
 * l 碰到。于是每个 l_i 拥有两个私有预算
 *
 *        Q_i = l_i 右边紧挨着的连续 q 的个数，
 *        Y_i = l_i 左边紧挨着的连续 y 的个数。
 *
 * B 类操作（y 在奇数位）同时各消耗 1 个单位；
 * A 类操作（y 在偶数位）不消耗预算，但会删掉 l_i。
 *
 * 任意时刻 l_i 的位置奇偶等于
 *      （l_i 原下标的奇偶）异或（它左边已经做过的 A 类操作次数）
 * 所以「在 l_i 左边做一次 A」恰好就是「给 l_i 再解锁一次 B 类操作」的
 * 凭证。从左往右处理各个 l，令 C = 已经做过的 A 类操作次数，则每个 l
 * 只需 O(1) 转移；而「只要 A 合法就做 A」的贪心是最优的（做 A 不会让
 * 当前收益变小，并且会让 C 变大，C 越大对后面的 l 越有利）。
 */
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200005;
static char s[MAXN];
static int yrun[MAXN], qrun[MAXN];   // yrun[i]:以 i 结尾的连续 y 长度；qrun[i]:以 i 开头的连续 q 长度

int main() {
    freopen("sakuzyo.in", "r", stdin);
    freopen("sakuzyo.out", "w", stdout);

    if (scanf("%s", s) != 1) { puts("0"); return 0; }
    int n = (int)strlen(s);

    for (int i = 0; i < n; ++i)
        yrun[i] = (s[i] == 'y') ? ((i ? yrun[i - 1] : 0) + 1) : 0;
    for (int i = n - 1; i >= 0; --i)
        qrun[i] = (s[i] == 'q') ? ((i + 1 < n ? qrun[i + 1] : 0) + 1) : 0;

    long long ans = 0;
    long long C = 0;                 // 到目前为止做过的 A 类操作次数

    for (int i = 0; i < n; ++i) {
        if (s[i] != 'l') continue;
        int Y = (i > 0 ? yrun[i - 1] : 0);
        int Q = (i + 1 < n ? qrun[i + 1] : 0);
        int cap = min(Y, Q);
        if (cap == 0) continue;       // 永远用不了
        int t = i & 1;                // 原下标的奇偶

        if (t == 1) {                 // 奇数位：一开始就能做 A
            long long b = min<long long>(cap - 1, C);
            ans += b + 1;             // 先做 b 次 B 类操作，再做一次 A 类操作
            ++C;
        } else {                      // 偶数位：先做 B
            if (cap >= 2) {
                long long b = min<long long>(cap - 1, C + 1);
                ans += b + 1;
                ++C;
            } else {                  // 此时 cap == 1
                if (C >= 1) { ans += 1; ++C; }   // 只做那一次 A 类操作
                else        { ans += 1; }        // 只做一次 B 类操作，C 不变
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

T3 恼鬼偷袭 vex

题意

$n\times m$ 的网格，第 $(i,j)$ 格从地面往上摞了 $h_{i,j}$ 个方块，其余是空气。恼鬼只能待在方块里，可以上下左右移动：左右前后移动不耗体力，上下移动每格耗 $1$ 点体力。$q$ 次询问，每次从 $(ax,ay)$ 的最高方块到 $(bx,by)$ 的最高方块，求最小体力。

转化：最大瓶颈路

记起点 $s$、终点 $t$，$H_s=h_s,\ H_t=h_t$。

恼鬼能穿过一条路径，当且仅当它始终待在方块内。一条路径"能用的最高高度"就是路径上所有格子的高度最小值，记作

$$\mathrm{bottleneck}(P)=\min_{(i,j)\in P} h_{i,j}.$$

沿路径 $P$ 走，至少要先从 $H_s$ 降到 $\mathrm{bottleneck}$，再升到 $H_t$，代价

$$(H_s-\mathrm{bottleneck})+(H_t-\mathrm{bottleneck})=H_s+H_t-2\cdot \mathrm{bottleneck}.$$

所以要最大化瓶颈：

$$W=\max_{P:s\to t}\ \mathrm{bottleneck}(P),\qquad \boxed{\text{ans}=H_s+H_t-2W}.$$

这就是经典的最大瓶颈路 / 最大生成树上的最小边（也叫最小生成树的对偶问题）。它满足"最大值的最小"形式，可以用 Kruskal 思想一遍扫出来。

计算 $W$：按高度降序并查集（Kruskal 重构树的思想）

把所有格子按 $h$ 从大到小排序，依次"激活"（可理解为水面从高到低下降，格子逐渐露出）：

1. 激活当前格子，把它自己作为一个新集合；
2. 与所有已经激活的相邻格子合并；
3. 每次合并发生在当前高度 $H$ 上，于是此时合并的两个集合里任意两点之间的 $W$ 恰好是 $H$。

因此"$s$ 与 $t$ 第一次连通时的高度"就是 $W$，这等价于 Kruskal 重构树上 $s,t$ 的 LCA 的权值。

离线处理询问：启发式合并

所有询问离线。每个并查集集合维护一个链表，存"落在该集合内的询问端点"，每个询问在两端各出现一次。

合并两个集合时（按大小合并，把小的并进大的）：

• 扫描较小集合的链表，对每个端点所属的询问，如果它的另一个端点已经和当前集合在同一连通块里，说明这条询问刚刚连通，$W=$ 当前高度，直接记录答案；
• 然后把小链表整体拼到大链表上（$O(1)$）。

每个端点每次所在的集合至少翻倍，所以总扫描量 $O(q\log q)$。

最后对每个询问输出 $H_s+H_t-2W$。

复杂度

排序 $O(nm\log(nm))$，并查集 $O(nm\,\alpha)$，询问合并 $O(q\log q)$；空间 $O(nm+q)$。在 $nm\le 10^6,\ q\le 5\times10^5$ 下轻松通过（实测最慢点约 $0.6$ s）。

实现要点

• 询问的 $s=t$ 要单独处理：直接 $W=h_s$，答案 $0$。
• 高度可能相同：按任意顺序激活即可，因为合并时用的都是"当前高度"，同高度格子互相连通时 $W$ 仍是该高度。
• 并查集按大小合并（不能按秩），因为要让"小集合链表"真的小。
• 输入输出量很大（最大测试点输入约 $18$ MB），标程使用了 fread 快读和缓冲区输出。

标程

完整代码（同时见 std/vex.cpp）：

/* 恼鬼偷袭 vex
 *
 * 第 (i,j) 格在高度 1..h[i][j] 上是方块。只要高度不超过相邻两格高度的较小值，
 * 恼鬼就能在相邻两格之间移动，因此一条路径「可用」的最高高度就是
 *
 *      bottleneck(path) = 路径上所有格子高度的最小值。
 *
 * 沿一条瓶颈为 H 的路径从 s 走到 t，代价为 (h[s]-H) + (h[t]-H)，于是需要
 *
 *      W = 所有 s->t 路径的 bottleneck 的最大值      （即「最大瓶颈路」）
 *      answer = h[s] + h[t] - 2*W。
 *
 * W 用 Kruskal 式并查集求：把格子按高度从大到小排序，依次激活（可以理解
 * 为水面从高到低下降，格子逐渐露出），并与已经激活的相邻格合并。s 与 t
 * 第一次落入同一集合时的高度，就是最大可能的瓶颈。
 *
 * 询问离线处理：每个集合维护一条「落在该集合内的询问端点」链表。合并两个
 * 集合时只扫描较小的那一条；若某询问的另一个端点已经在大集合里，说明它
 * 刚刚连通，记下 W = 当前高度。每个端点至多被搬入更大的集合 O(log q) 次
 * -> O((nm + q) log)。
 *
 * 复杂度 O(nm log(nm) + (nm + q) log q) 时间，O(nm + q) 空间。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const int MAXN = 1000005;
static const int MAXQ = 500005;

/* ---------------- 快速读入 ---------------- */
static char *ib;
static size_t ipos, isz;
static inline bool readInt(int &out) {
    while (ipos < isz && (ib[ipos] < '0' || ib[ipos] > '9')) ++ipos;
    if (ipos >= isz) return false;
    int v = 0;
    while (ipos < isz && ib[ipos] >= '0' && ib[ipos] <= '9') {
        v = v * 10 + (ib[ipos] - '0');
        ++ipos;
    }
    out = v;
    return true;
}

int n, m, N, q;
static int h[MAXN];
static int par_[MAXN], sz_[MAXN];
static bool active_[MAXN];
static int listHead[MAXN];
static int order_[MAXN];

static int qs[MAXQ], qt[MAXQ], qhs[MAXQ], qht[MAXQ], qw[MAXQ];

struct Ev { int qid, other, nxt; };   // 询问端点链表的一个结点
static Ev ev[2 * MAXQ];
static int ecnt = 0;

/* ---------------- 并查集 ---------------- */
static int find_(int x) {
    int r = x;
    while (par_[r] != r) r = par_[r];
    while (x != r) { int p = par_[x]; par_[x] = r; x = p; }
    return r;
}

/* 在高度 H 处把集合 b 合并进集合 a（保证 sz_[a] >= sz_[b]） */
static void merge_(int a, int b, int H) {
    int cur = listHead[b], tail = -1;
    while (cur != -1) {
        int id = ev[cur].qid, other = ev[cur].other;
        if (qw[id] == -1 && find_(other) == a) qw[id] = H;   // 这条询问刚刚连通
        tail = cur;
        cur = ev[cur].nxt;
    }
    if (tail != -1) { ev[tail].nxt = listHead[a]; listHead[a] = listHead[b]; }
    par_[b] = a;
    sz_[a] += sz_[b];
}

int main() {
    freopen("vex.in", "r", stdin);
    freopen("vex.out", "w", stdout);

    static char inbuf[1 << 26];   /* 最大的测试点输入不到 20 MB */
    isz = fread(inbuf, 1, sizeof(inbuf), stdin);
    ib = inbuf; ipos = 0;

    if (!readInt(n)) return 0;
    readInt(m);
    N = n * m;
    for (int i = 0; i < N; ++i) readInt(h[i]);
    readInt(q);
    for (int i = 0; i < N; ++i) listHead[i] = -1;

    for (int i = 0; i < q; ++i) {
        int ax = 0, ay = 0, bx = 0, by = 0;
        readInt(ax); readInt(ay); readInt(bx); readInt(by);
        --ax; --ay; --bx; --by;
        int s = ax * m + ay, t = bx * m + by;
        qs[i] = s; qt[i] = t;
        qhs[i] = h[s]; qht[i] = h[t];
        qw[i] = -1;
        if (s == t) qw[i] = h[s];      // 起点即终点，直接为 0
        else {
            ev[ecnt] = {i, t, listHead[s]}; listHead[s] = ecnt++;
            ev[ecnt] = {i, s, listHead[t]}; listHead[t] = ecnt++;
        }
    }

    for (int i = 0; i < N; ++i) {
        par_[i] = i; sz_[i] = 1; active_[i] = false;
        order_[i] = i;
    }
    /* 按高度从大到小排序 */
    sort(order_, order_ + N, [](int a, int b) { return h[a] > h[b]; });

    for (int k = 0; k < N; ++k) {
        int idx = order_[k];
        int H = h[idx];
        active_[idx] = true;
        /* listHead[idx] 已经是该格自己的询问端点链表 */
        int i = idx / m, j = idx % m;

        int nb[4], cnt = 0;
        if (i > 0)     nb[cnt++] = idx - m;
        if (i < n - 1) nb[cnt++] = idx + m;
        if (j > 0)     nb[cnt++] = idx - 1;
        if (j < m - 1) nb[cnt++] = idx + 1;
        for (int t = 0; t < cnt; ++t) {
            int u = nb[t];
            if (!active_[u]) continue;
            int ra = find_(idx), rb = find_(u);
            if (ra == rb) continue;
            if (sz_[ra] < sz_[rb]) swap(ra, rb);
            merge_(ra, rb, H);
        }
    }

    /* 快速输出 */
    string out;
    out.reserve((size_t)q * 12);
    char tmp[24];
    for (int i = 0; i < q; ++i) {
        ll ans = (ll)qhs[i] + qht[i] - 2LL * qw[i];
        int L = 0;
        if (ans == 0) tmp[L++] = '0';
        else {
            char rev[24]; int r = 0;
            while (ans > 0) { rev[r++] = char('0' + ans % 10); ans /= 10; }
            while (r > 0) tmp[L++] = rev[--r];
        }
        tmp[L++] = '\n';
        out.append(tmp, L);
    }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

T4 模刀削面 modulo

题意

给定 $a_1..a_n$，定义 $f(x)=x \bmod a_1 \bmod a_2 \cdots \bmod a_n$。求

$$\sum_{i=l}^{r}f(i)\pmod{10^9+7},\qquad 0\le l\le r\le 10^{18},\ a_i\le 10^{18}.$$

记 $S(N)=\sum_{x=0}^{N}f(x)$，答案即 $S(r)-S(l-1)$。

第一步：约化成严格递减的模数序列

核心性质：$x\bmod m < m$。所以如果 $a_i\ge \min(a_1,\dots,a_{i-1})$，那么任何数在经过前面的取模后都已经 $<\min\le a_i$，这一步取模什么也不做。

只保留严格递减的前缀最小值（$b$ 就是所有满足"比前面所有 $a_i$ 都小"的位置上的 $a_i$，其中 $b_0=a_1$）：

$$b_0>b_1>\cdots>b_{k-1},\qquad b_0=a_1,$$

之后 $f(x)=x\bmod b_0\bmod b_1\cdots\bmod b_{k-1}$。注意 $k$ 最大可以到 $n$（例如 $a$ 本身就是严格递减的），所以后面只能做到 $O(k\log A)$ 而不能假设 $k$ 很小。

第二步：周期性

定义

$$f_i(x)=x\bmod b_i\bmod b_{i+1}\cdots\bmod b_{k-1},\qquad f_k(x)=x .$$

因为 $(x+b_i)\bmod b_i=x\bmod b_i$，所以 $f_i$ 以 $b_i$ 为周期；并且当 $0 \le x

于是令

$$T_i=\sum_{x=0}^{b_i-1}f_{i+1}(x)\qquad(\text{即 }f_i\text{ 的一个完整周期和}),$$

就有

$$\mathrm{Calc}(i,N)=\sum_{x=0}^{N}f_i(x)=\begin{cases} q\,T_i+\mathrm{Calc}(i+1,\;rem-1), & b_i\le N,\\[2pt] \mathrm{Calc}(i+1,N), & b_i>N, \end{cases}$$

其中 $q=(N+1)/b_i,\ rem=(N+1)\bmod b_i$；若 $rem=0$ 则第二项为 $0$。

$T_i$ 用同一个递推从后往前算：

$$T_{k-1}=\sum_{x=0}^{b_{k-1}-1}x=\frac{b_{k-1}(b_{k-1}-1)}2,\qquad T_i=\frac{b_i}{b_{i+1}}T_{i+1}+\mathrm{Calc}\Bigl(i+2,\;b_i\bmod b_{i+1}-1\Bigr).$$

第三步：复杂度

在 $\mathrm{Calc}$ 中，跳过所有 $>N$ 的模数后用第一个 $\le N$ 的 $b_j$ 取模：

• 若 $b_j\le N/2$，则新参数 $
• 若 $b_j>N/2$，则 $N\bmod b_j=N-b_j

所以每层至少减半，一次 $\mathrm{Calc}$ 只有 $O(\log A)\le 60$ 步。预处理 $T_i$ 要做 $O(k)$ 次 $\mathrm{Calc}$，总复杂度

$$O\bigl(n+(k+1)\log A\log k\bigr),$$

其中 $k\le n$，即最坏约 $2\times 10^5\times 60$ 次基本操作，实测最慢点 $40$ ms 以内。

易错点

• 找"第一个 $\le N$ 的模数"时不能用 "第一个 $。$b_j=N$ 时这一步是有效的：$\sum_{x=0}^{N}f_i(x)$ 中 $x=N$ 会变成 $0$，而少算一个 $b_j$ 会多算一截。本题部分分点 $3\sim 5$（$n\le 1000,r\le 1000$）就会因为这个 $O(1)$ 的 off-by-one 挂掉。
• 计算 $\sum_{x=0}^{N}x$ 时 $N$ 可能到 $10^{18}$，必须先取模再用 $\mathrm{inv}2=500000004$。
• $l=0$ 时 $l-1=-1$，$S(-1)=0$。
• $a_i$ 可能为 $1$：此时所有 $f(x)=0$，代码自然处理正确。

标程

完整代码（同时见 std/modulo.cpp）：

/* 模刀削面 modulo
 *
 * 记  f(x) = x mod a1 mod a2 ... mod an，S(N) = sum_{x=0}^{N} f(x)，
 * 则答案为 S(r) - S(l-1) （对 1e9+7 取模）。
 *
 * 约化
 * ----
 * 只保留 a 中严格递减的前缀最小值  b[0] > b[1] > ... > b[k-1]。
 * 若 a[i] 不小于 min(a[0..i-1])，则它不可能改变数值（x mod m < m <= a[i]），
 * 可以直接丢掉。
 *
 * 定义 f_i(x) = x mod b[i] mod b[i+1] ... mod b[k-1]（f_k 为恒等映射）。
 * f_i 以 b[i] 为周期，且当 0 <= x < b[i] 时 f_i(x) = f_{i+1}(x)。
 * 于是令
 *      T[i] = sum_{x=0}^{b[i]-1} f_{i+1}(x)        （f_i 的一个完整周期和）
 * 就有
 *      Calc(i,N) = q*T[i] + Calc(i+1, rem-1),
 *      q = (N+1)/b[i], rem = (N+1)%b[i],     （当 b[i] <= N）
 *      Calc(i,N) = Calc(i+1,N)               （当 b[i] >  N）。
 *
 * T[i] 用完全相同的递推从后往前计算。每一步的新参数都 < b[i] <= N，
 * 而且一定 < N/2，因此一次询问只需 O(log(max a)) 步，
 * 总复杂度 O(n + k log A log k)。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
static const ll MOD = 1000000007LL;
static const ll INV2 = 500000004LL;

static int k;
static vector<ll> b;
static vector<ll> T;              // T[i] = f_{i+1}(0) + ... + f_{i+1}(b[i]-1)，即一个完整周期和

/* ---------- 快速读入 ---------- */
static char *ibuf;
static size_t ipos, isz;
static inline void initInput() {
    static char buf[1 << 25];
    ibuf = buf;
    isz = fread(buf, 1, sizeof(buf), stdin);
    ipos = 0;
}
static inline bool readLL(ll &out) {
    while (ipos < isz && (ibuf[ipos] < '0' || ibuf[ipos] > '9')) ++ipos;
    if (ipos >= isz) return false;
    ll v = 0;
    while (ipos < isz && ibuf[ipos] >= '0' && ibuf[ipos] <= '9') {
        v = v * 10 + (ibuf[ipos] - '0');
        ++ipos;
    }
    out = v;
    return true;
}

/* 求 sum_{x=0}^{N} f_start(x) */
static ll calc(int start, ll N) {
    ll res = 0;
    int i = start;
    while (N >= 0) {
        /* 找到第一个 j >= i 且 b[j] <= N（b 严格递减） */
        int j = (int)(lower_bound(b.begin() + i, b.end(), N, greater<ll>()) - b.begin());
        if (j >= k) {
            /* 剩下的模数都 > N：在 [0,N] 上 f 就是恒等映射，直接等差数列求和 */
            ll n = N % MOD;
            res = (res + n * ((N + 1) % MOD) % MOD * INV2) % MOD;
            break;
        }
        ll m = b[j];
        ll q = (N + 1) / m;
        ll rem = (N + 1) % m;
        res = (res + (q % MOD) * T[j]) % MOD;   // 完整的 q 个周期
        if (rem == 0) break;
        N = rem - 1;                            // 剩余部分继续向下递归
        i = j + 1;
    }
    return res;
}

int main() {
    freopen("modulo.in", "r", stdin);
    freopen("modulo.out", "w", stdout);
    initInput();

    ll n, l, r;
    if (!readLL(n)) return 0;
    readLL(l);
    readLL(r);

    b.reserve((size_t)n);
    ll mn = LLONG_MAX;
    for (ll i = 0; i < n; ++i) {
        ll x;
        readLL(x);
        if (x < mn) { mn = x; b.push_back(x); }  // 只留严格递减的前缀最小值
    }
    k = (int)b.size();

    T.assign(k, 0);
    for (int i = k - 1; i >= 0; --i) {          // 从后往前算周期和
        if (i == k - 1) {
            ll m = b[i] % MOD;
            T[i] = m * ((b[i] - 1) % MOD) % MOD * INV2 % MOD;   // 0+1+...+(b[i]-1)
        } else {
            ll m = b[i];
            ll q = m / b[i + 1];
            ll rem = m % b[i + 1];
            ll val = (q % MOD) * T[i + 1] % MOD;
            if (rem > 0) val = (val + calc(i + 2, rem - 1)) % MOD;
            T[i] = val;
        }
    }

    ll sr = calc(0, r);
    ll sl = (l == 0) ? 0 : calc(0, l - 1);
    ll ans = (sr - sl) % MOD;
    if (ans < 0) ans += MOD;
    printf("%lld\n", ans);
    return 0;
}