‹ 返回突击教材 ｜ 预备知识 ｜ 门户首页

算法大全（附录 · 可检索）

本教材涉及的全部算法：一句话 + 完整模板 + 复杂度 + 易错点，即查即用

A · 贪心与双指针

A1. 反悔贪心 · 带截止时间的任务调度 #

贪心堆反悔复杂度 O(n log n) ｜ 例题 P2949 ｜ 详解页

按截止时间升序，报酬先入小根堆；已选数量超过当前截止 d 就弹出最小报酬（反悔）。

完整代码（P2949 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<pair<long long, long long>> a(n);  // (d, p)
    for (int i = 0; i < n; i++) scanf("%lld %lld", &a[i].first, &a[i].second);
    sort(a.begin(), a.end());
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long d = a[i].first, p = a[i].second;
        pq.push(p); ans += p;
        if ((long long)pq.size() > d) { ans -= pq.top(); pq.pop(); }
    }
    printf("%lld\n", ans);
    return 0;
}

易错：比较条件是 size() > d（不是 ≥）；ans 用 long long。

A2. 反悔贪心 · 链表 + 堆（不相邻选取） #

贪心堆双向链表复杂度 O(k log n) ｜ 例题 P1484 ｜ 详解页

大根堆选最大 a[i]；选后将 i 与邻居合并为权值 a[l]+a[r]−a[i] 的"悔棋子"重新入堆；堆顶 ≤ 0 停止（至多 k 个）。

完整代码（P1484 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005;
ll a[N]; int L[N], R[N]; bool del[N];
int main() {
    int n, k; scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    priority_queue<pair<ll, int>> pq;
    for (int i = 1; i <= n; i++) { L[i] = i - 1; R[i] = i + 1; pq.push({a[i], i}); }
    a[0] = a[n + 1] = LLONG_MIN / 2;             // 两端哨兵
    ll ans = 0;
    for (int t = 0; t < k; t++) {
        auto [v, i] = pq.top(); pq.pop();
        if (del[i]) { t--; continue; }           // 懒删除
        if (v <= 0) break;                       // 至多 k 棵：再选不赚
        ans += v;
        int l = L[i], r = R[i];
        a[i] = a[l] + a[r] - a[i];               // 悔棋子
        del[l] = del[r] = true;
        L[i] = L[l]; R[i] = R[r];
        R[L[i]] = i; L[R[i]] = i;
        pq.push({a[i], i});
    }
    printf("%lld\n", ans);
    return 0;
}

易错：被合并的旧节点要懒删除跳过；哨兵权值取 −∞。

A3. 区间贪心（选点 / 覆盖 / 调度） #

贪心区间复杂度 O(n log n) ｜ 例题 P1514、2024 超速检测 ｜ 详解页

选点：按右端点排序，未覆盖就在右端点放点；覆盖：左端点 ≤ 当前位置中选右端点最远的；调度：按右端点排序能选就选。

完整代码（区间选点骨架） 
#include <bits/stdc++.h>
using namespace std;
struct Seg { long long l, r; } seg[200005];
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &seg[i].l, &seg[i].r);
    sort(seg + 1, seg + n + 1, [](Seg a, Seg b){ return a.r < b.r; });
    int ans = 0; long long last = LLONG_MIN;
    for (int i = 1; i <= n; i++)
        if (seg[i].l > last) { ans++; last = seg[i].r; }
    printf("%d\n", ans);
    return 0;
}

易错：排序关键字几乎都是右端点；last 初值用 LLONG_MIN。

A4. 双指针配对（决斗模型） #

双指针排序复杂度 O(n log n) ｜ 例题 P11231 ｜ 详解页

严格大者淘汰对方、各限一次 → 最大配对数：排序后双指针，最弱者配"能赢它的最弱者"。答案 = n − 配对数。

完整代码（决斗配对骨架） 
#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    int match = 0;
    for (int i = 0, j = n / 2; i < n / 2 && j < n; j++)
        if (a[j] > a[i]) { match++; i++; }     // a[j] 淘汰 a[i]
    printf("%d\n", n - match);
    return 0;
}

易错：必须严格大于；i 只在配对成功时前进。

B · 字符串

B1. Manacher（最长回文子串 / 回文计数） #

字符串回文Manacher复杂度 O(n) ｜ 例题 P3805 ｜ 详解页

插 # 统一奇偶；臂长 p[i] = min(p[2c−i], R−i) 镜像继承后扩展；原串回文长度 = p[i]，回文总数 = Σ(p[i]+1)/2。

完整代码（P3805 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s; cin >> s;
    string t = "^#";
    for (char c : s) { t += c; t += '#'; }
    t += '$';
    int n = t.size(), C = 0, R = 0, ans = 0;
    vector<int> p(n, 0);
    for (int i = 1; i < n - 1; i++) {
        p[i] = (i < R) ? min(R - i, p[2 * C - i]) : 0;
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;
        if (i + p[i] > R) { C = i; R = i + p[i]; }
        ans = max(ans, p[i]);
    }
    cout << ans << "\n";
    return 0;
}

易错：哨兵 ^、$ 互不相同；大输入必须关 cin 同步。

B2. 字符串哈希（子串相等 / 判回文 / LCP） #

字符串哈希预处理 O(n)、查询 O(1) ｜ 例题 P3370 ｜ 详解页

B 进制前缀哈希；子串哈希 = h[r] − h[l−1]·B^(r−l+1)；字符映射 +1 防前导零；判回文用正反对称两份哈希。

完整代码（模板） 
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 1000005;
const ull B = 131;
ull h[N], p[N]; char s[N];
ull get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }  // 1-based
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * B;
        h[i] = h[i - 1] * B + (s[i] - 'a' + 1);
    }
    // 判 s[l..r] 回文：再对反串建一份哈希 revh，比较 get(l,r) 与 revh.get(n-r+1, n-l+1)
    return 0;
}

易错：字符 +1；反串下标 [n−r+1, n−l+1]；担心被卡换双模。

B3. KMP（单模式匹配 / next 数组） #

字符串KMP复杂度 O(n + m) ｜ 例题 P3375 ｜ 详解页

next[j] = 前缀的最长公共真前后缀；失配时模式右滑、文本指针永不回退。是 AC 自动机 fail 指针的一维原型。

完整代码（模板） 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int nxt[N]; char s[N], p[N];
int main() {
    scanf("%s %s", s, p);                        // 文本 s、模式 p
    int n = strlen(s), m = strlen(p);
    nxt[0] = -1;
    for (int i = 1, j = -1; i < m; i++) {
        while (j >= 0 && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
    for (int i = 0, j = -1; i < n; i++) {
        while (j >= 0 && s[i] != p[j + 1]) j = nxt[j];
        if (s[i] == p[j + 1]) j++;
        if (j == m - 1) { printf("%d\n", i - m + 2); j = nxt[j]; }
    }
    return 0;
}

易错：nxt[0] = −1 的 −1 约定；匹配成功后 j = nxt[j] 继续找重叠匹配。

B4. AC 自动机（多模式匹配 + fail 树统计） #

字符串AC自动机Triefail树复杂度 O(模式总长 × 字符集 + 文本长) ｜ 例题 P5357 ｜ 详解页

Trie + BFS 建 fail（顺带转移压缩）；扫描只打标记，逆 BFS 序做 fail 树子树和统计出现次数。

完整代码（P5357 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int ch[N][26], fail[N], idx = 0;
int pos[N]; long long cnt[N]; int q[N];
int insert_(const char *s, int id) {
    int u = 0;
    for (; *s; s++) {
        int v = *s - 'a';
        if (!ch[u][v]) ch[u][v] = ++idx;
        u = ch[u][v];
    }
    return pos[id] = u;
}
void build() {
    int h = 0, t = 0;
    for (int c = 0; c < 26; c++) if (ch[0][c]) q[t++] = ch[0][c];
    while (h < t) {
        int u = q[h++];
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) { fail[v] = ch[fail[u]][c]; q[t++] = v; }
            else    ch[u][c]  = ch[fail[u]][c];
        }
    }
}
int main() {
    int n; scanf("%d", &n);
    static char buf[200006];
    for (int i = 0; i < n; i++) { scanf("%s", buf); insert_(buf, i); }
    build();
    static char text[2000006]; scanf("%s", text);
    int u = 0;
    for (char *p = text; *p; p++) { u = ch[u][*p - 'a']; cnt[u]++; }
    for (int i = idx - 1; i >= 0; i--) cnt[fail[q[i]]] += cnt[q[i]];
    for (int i = 0; i < n; i++) printf("%lld\n", cnt[pos[i]]);
    return 0;
}

易错：累加必须逆 BFS 序；cnt 开 long long；多组数据整体清空。

C · 动态规划

C1. 状压 DP · TSP 旅行商 #

DP状压TSP复杂度 O(2ⁿ·n²) ｜ 例题 P1171 ｜ 详解页

f[S][i] = 已走集合 S、停在 i 的最短路；答案要 +d[i][0] 回起点。n ≤ 20 的识别信号。

完整代码（P1171 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
int n, w[20][20], dp[1 << 20][20];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int S = 1; S < (1 << n); S++)
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1) || dp[S][i] == 0x3f3f3f3f) continue;
            for (int j = 0; j < n; j++)
                if (!(S >> j & 1))
                    dp[S | 1 << j][j] = min(dp[S | 1 << j][j], dp[S][i] + w[i][j]);
        }
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i] + w[i][0]);
    printf("%d\n", ans);
    return 0;
}

易错：dp 数组约 84 MB 必须开全局；答案别漏回起点。

C2. 完全背包计数 + 容斥（上限约束） #

DP背包容斥预处理 O(种类 × 上限)、每询问 O(2⁴) ｜ 例题 P1450 ｜ 详解页

无上限方案先完全背包预处理；"第 i 种超限"= 强制用 di+1 枚扣减，16 个越界集合容斥。

完整代码（P1450 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[100005]; int c[4], d[4];
int main() {
    for (int i = 0; i < 4; i++) scanf("%d", &c[i]);
    f[0] = 1;
    for (int i = 0; i < 4; i++)
        for (int x = c[i]; x <= 100000; x++) f[x] += f[x - c[i]];
    int q; scanf("%d", &q);
    while (q--) {
        for (int i = 0; i < 4; i++) scanf("%d", &d[i]);
        ll s, ans = 0; scanf("%lld", &s);
        for (int S = 0; S < 16; S++) {
            ll t = s; int bits = 0;
            for (int i = 0; i < 4; i++)
                if (S >> i & 1) { t -= (ll)(d[i] + 1) * c[i]; bits++; }
            if (t >= 0) ans += (bits & 1 ? -1 : 1) * f[t];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

易错：完全背包正序遍历（0/1 背包才倒序）；符号 (−1)^|S| 奇负偶正。

C3. 区间 DP · 计数防重框架 #

DP区间DP复杂度 O(n³) ｜ 例题 P7914 ｜ 详解页

计数类区间 DP 的核心是防重：f（两端匹配）/ g（可拆并列）分类，规定"最后一段是完整匹配段"唯一切分。

框架代码（括号序列型骨架） 
// f[l][r]：两端恰好匹配的合法序列数；g[l][r]：合法但可拆并列
for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        if (match(l, r)) {                     // 两端可配对
            f[l][r] = (g[l + 1][r - 1] + 内部星号方案) % mod;
        }
        // 规定最后一段是完整匹配段，保证不重不漏
        for (int k = l; k < r; k++)
            g[l][r] = (g[l][r] + (ll)g[l][k] * f[k + 1][r]) % mod;
        g[l][r] = (g[l][r] + f[l][r]) % mod;
    }

易错：按区间长度递增枚举；写完用 n ≤ 5 暴力对拍。

C4. 树形 DP / 换根 / 树的重心 #

DP树形DP换根重心复杂度 O(n) ｜ 例题 P1395、P3047 ｜ 详解页

两遍 dfs：自底向上求 sz 与 f[1]，自顶向下 f[v] = f[u] + n − 2·sz[v]。重心：max(子树大小, n−sz[u]) 最小者。

完整代码（P1395 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
long long sz[N], f[N];
int n;
void dfs1(int u, int fa, long long d) {
    sz[u] = 1; f[1] += d;
    for (int v : g[u]) if (v != fa) { dfs1(v, u, d + 1); sz[u] += sz[v]; }
}
void dfs2(int u, int fa) {
    for (int v : g[u]) if (v != fa) {
        f[v] = f[u] + (long long)(n - sz[v]) - sz[v];
        dfs2(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) { scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x); }
    dfs1(1, 0, 0); dfs2(1, 0);
    long long best = LLONG_MAX; int id = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] < best) { best = f[i]; id = i; }
    printf("%d %lld\n", id, best);
    return 0;
}

易错：距离和用 long long；链形树递归深，n 大时改迭代。

D · 图论

D1. BFS（可达性 / 最少步数） #

图论BFS复杂度 O(n + m) ｜ 例题 P1514 ｜ 详解页

队列按层扩展，入队即打标记；第一次到达即最少步数。

完整代码（模板） 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int vis[N], dist[N];
int main() {
    int n, m, s; scanf("%d%d%d", &n, &m, &s);
    for (int i = 0, u, v; i < m; i++) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); }
    queue<int> q;
    q.push(s); vis[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (!vis[v]) {
            vis[v] = 1; dist[v] = dist[u] + 1; q.push(v);
        }
    }
    return 0;
}

易错：入队时就打 vis，否则同一节点重复入队。

D2. Dijkstra（堆优化，非负权单源最短路） #

图论最短路Dijkstra复杂度 O(m log n) ｜ 例题 P4779 ｜ 详解页

小根堆每次锁定 dist 最小的未确定点并松弛出边；过期堆顶用 d ≠ dist[u] 懒删除。

完整代码（P4779 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
vector<pair<int, ll>> g[N];
ll dist[N];
int main() {
    int n, m, s; scanf("%d%d%d", &n, &m, &s);
    for (int i = 0, u, v; i < m; i++) { ll w; scanf("%d%d%lld", &u, &v, &w); g[u].push_back({v, w}); }
    memset(dist, 0x3f, sizeof dist); dist[s] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    q.push({0, s});
    while (!q.empty()) {
        auto [d, u] = q.top(); q.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
    }
    for (int i = 1; i <= n; i++) printf("%lld ", dist[i]);
    return 0;
}

易错：负权不能用；dist 用 long long。

D3. Floyd（多点对最短路） #

图论最短路Floyd复杂度 O(n³)，n ≤ 400 ｜ 详解页

k 必须最外层："只允许经过前 k 个点"的阶段递进。常作为关键点两两距离的预处理工具。

完整代码（模板） 
#include <bits/stdc++.h>
using namespace std;
int f[405][405];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    for (int i = 0, u, v, w; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        f[u][v] = f[v][u] = min(f[u][v], w);   // 重边取小
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    return 0;
}

易错：k 放最外层；f[i][i] = 0；无边为 INF 且不参与加法。

D4. Kruskal 最小生成树 + 并查集 #

图论MST并查集复杂度 O(m log m) ｜ 例题 P3366 ｜ 详解页

边按权排序，并查集逐条合并未连通两端；选满 n−1 条边即最小生成树。

完整代码（P3366 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
struct Edge { int u, v, w; } e[N];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    sort(e, e + m, [](Edge a, Edge b){ return a.w < b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;
    long long ans = 0; int cnt = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        int x = find(e[i].u), y = find(e[i].v);
        if (x == y) continue;
        fa[x] = y; ans += e[i].w; cnt++;
    }
    if (cnt < n - 1) printf("orz\n");
    else printf("%lld\n", ans);
    return 0;
}

易错：不连通要特判；次小生成树已出考纲，不必准备。

D5. bitset 加速（背包可行性 / 可达性传递） #

bitset位运算复杂度除以 64 ｜ 例题 P2709（配合莫队）｜ 详解页

0/1 背包：f |= f << w；可达性：reach[v] |= reach[u]；交集计数：(a & b).count()。

完整代码（bitset 背包模板） 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
bitset<N> f;
int main() {
    int n, m; scanf("%d%d", &n, &m);          // n 件物品，问能否凑出 m
    f[0] = 1;
    for (int i = 0, w; i < n; i++) { scanf("%d", &w); f |= (f << w); }
    puts(f[m] ? "YES" : "NO");
    return 0;
}

易错：bitset 长度必须编译期常量；移位量 ≥ 位宽是未定义行为。

E · 数据结构与其他

E1. 莫队（离线区间查询） #

莫队分块离线复杂度 O((n+q)√n) ｜ 例题 P2709 ｜ 详解页

询问按 (l 块号, r 奇偶交替) 排序，双指针滑动，add/remove O(1) 增量维护答案。

完整代码（P2709 骨架） 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50005;
int a[N], cnt[N], n, m, B;
ll ans[N], cur = 0;
struct Q { int l, r, id, blk; } q[N];
void add(int x) { cur += 2 * cnt[x] + 1; cnt[x]++; }   // (k+1)²−k² = 2k+1
void del(int x) { cnt[x]--; cur -= 2 * cnt[x] + 1; }
int main() {
    scanf("%d%d", &n, &m); B = sqrt(n) + 1;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i; q[i].blk = (q[i].l - 1) / B;
    }
    sort(q, q + m, [](Q x, Q y){
        if (x.blk != y.blk) return x.blk < y.blk;
        return (x.blk & 1) ? x.r < y.r : x.r > y.r;
    });
    for (int i = 0, L = 1, R = 0; i < m; i++) {
        while (L > q[i].l) add(a[--L]);
        while (R < q[i].r) add(a[++R]);
        while (L < q[i].l) del(a[L++]);
        while (R > q[i].r) del(a[R--]);
        ans[q[i].id] = cur;
    }
    for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);
    return 0;
}

易错：闭区间 [l,r]，初值 L=1、R=0；add/del 公式与 cnt 修改顺序自洽。

E2. 扫描线 + 离散化（矩形面积并） #

扫描线线段树离散化复杂度 O(n log n) ｜ 例题 P5490、P1856 ｜ 详解页

矩形拆左右边缘 ±1 事件按 x 排序；y 离散化，线段树维护覆盖长度（叶子是"段"，不下传）；先算贡献再处理事件。

完整代码（P5490 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
struct Node { int cnt; ll len; } t[8 * N];
struct Ev { ll x, y1, y2; int v; };
vector<Ev> ev; vector<ll> ys;
void pushup(int u, int l, int r) {
    if (t[u].cnt) t[u].len = ys[r + 1] - ys[l];
    else t[u].len = (l == r) ? 0 : t[u * 2].len + t[u * 2 + 1].len;
}
void update(int u, int l, int r, int ql, int qr, int v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { t[u].cnt += v; pushup(u, l, r); return; }
    int m = (l + r) / 2;
    update(u * 2, l, m, ql, qr, v); update(u * 2 + 1, m + 1, r, ql, qr, v);
    pushup(u, l, r);
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        ll x1, y1, x2, y2; scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        ev.push_back({x1, y1, y2, 1}); ev.push_back({x2, y1, y2, -1});
        ys.push_back(y1); ys.push_back(y2);
    }
    sort(ev.begin(), ev.end(), [](auto& a, auto& b){ return a.x < b.x; });
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
    int m = ys.size() - 1;
    ll ans = 0, lastX = ev[0].x;
    for (auto& e : ev) {
        ans += t[1].len * (e.x - lastX);
        int l = lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin();
        int r = lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin() - 1;
        if (l <= r) update(1, 0, m - 1, l, r, e.v);
        lastX = e.x;
    }
    printf("%lld\n", ans);
    return 0;
}

易错：右端点排名 −1；坐标 10⁹ 全程 long long；面积用旧 len 乘 Δx。

E3. 大模拟与环形同余 #

模拟同余复杂度 O(n + m) ｜ 例题 P1563、P7075 ｜ 详解页

规则清单 + struct + 分函数；环形位置 (pos + step % n + n) % n；face == dir 下标减，否则加。

完整代码（P1563 可直接提交） 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<int> face(n); vector<string> name(n);
    for (int i = 0; i < n; i++) {
        char s[12]; scanf("%d %s", &face[i], s); name[i] = s;
    }
    int pos = 0;
    while (m--) {
        int dir; long long s; scanf("%d%lld", &dir, &s);
        if (dir == face[pos]) pos = ((pos - s % n) % n + n) % n;
        else                  pos = (pos + s) % n;
    }
    printf("%s\n", name[pos].c_str());
    return 0;
}

易错：减法后 +n 防负；方向规则用样例验证，别靠背。