A

只需要预处理前后缀 ，然后枚举关键点 ，用前后缀的 再求一次 即可求出剩余关键点的 ，然后比较大小贡献答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
int n;
int read() {
    int f = 0, x = 0;
    char ch = getchar();

    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }

    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return f ? -x : x;
}
struct Tree {
    int fa[N][20], dep[N], a[N];
    vector<int>e[N];
    void dfs(int x, int f) {
        fa[x][0] = f, dep[x] = dep[f] + 1;

        for (int i = 1; i <= 17; i++)
            fa[x][i] = fa[fa[x][i - 1]][i - 1];

        for (int to : e[x])
            if (to != f)
                dfs(to, x);
    }
    int LCA(int x, int y) {
        if (x == 0 || y == 0)
            return x + y;

        if (dep[x] < dep[y])
            swap(x, y);

        for (int i = 17; i >= 0; i--)
            if (dep[x] - (1 << i) >= dep[y])
                x = fa[x][i];

        if (x == y)
            return x;

        for (int i = 17; i >= 0; i--)
            if (fa[x][i]^fa[y][i])
                x = fa[x][i], y = fa[y][i];

        return fa[x][0];
    }
    void init() {
        for (int i = 1; i <= n; i++)
            a[i] = read();

        for (int i = 2; i <= n; i++) {
            int x = read();
            e[i].push_back(x);
            e[x].push_back(i);
        }

        dfs(1, 0);
    }
} T1, T2;
int a[N], L[N][2], R[N][2], k;
int main() {
    n = read(), k = read();

    for (int i = 1; i <= k; i++)
        a[i] = read();

    T1.init(), T2.init();

    for (int i = 1; i <= k; i++) {
        L[i][0] = T1.LCA(L[i - 1][0], a[i]);
        L[i][1] = T2.LCA(L[i - 1][1], a[i]);
    }

    for (int i = k; i; i--) {
        R[i][0] = T1.LCA(R[i + 1][0], a[i]);
        R[i][1] = T2.LCA(R[i + 1][1], a[i]);
    }

    int ans = 0;

    for (int i = 1; i <= k; i++) {
        int x0 = T1.LCA(L[i - 1][0], R[i + 1][0]);
        int x1 = T2.LCA(L[i - 1][1], R[i + 1][1]);

        if (T1.a[x0] > T2.a[x1])
            ans++;
    }

    cout << ans << endl;
    return 0;
}

B

首先有一个做法就是，建图然后跑最小费用最大流。显然过不了。

模拟费用流的过程，每次都是把一些人从某个城市移动到另一个城市。

一个人 若从城市 移动到城市 ，代价就是 。因为增广路只会经过每个点至多一次，所以如果有多个人可以从城市 移动到城市 ，肯定会优先考虑代价最小的人。

那么不妨只建立 个点，城市 到 之间的边就是所有在城市 的人移动到城市 的代价。 显然边的数量还是 级别，但是对于重边只取代价最小的边，所以开 个小根堆来维护所有的边。这样就可以放心跑 了！但是注意每跑一次就要重新更新边集，初始把所有人放在城市 。

因为会跑 次 ，并且每次会移动至多 个人所在城市，所以时间复杂度最坏是

（ 最坏是 ）

#include <bits/stdc++.h>
#define int long long
#define w first
#define se second
#define mk make_pair
using namespace std;
const int inf = 1e9;
const int N = 1e5 + 9;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int n, k;
int dis[12], vis[12], fa[12];
int a[12], c[N][12], in[N];
priority_queue<pair<int, int>> e[12][12];
int SPFA(int rt) {
    queue<int> q;
    q.push(rt);
    for (int i = 1; i <= 10; i++)
        dis[i] = inf, vis[i] = 0, fa[i] = 0;
    dis[rt] = 0, vis[rt] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int y = 1; y < rt; y++) {
            if (!e[x][y].size())
                continue;
            int d = -e[x][y].top().w;
            if (dis[y] > dis[x] + d) {
                dis[y] = dis[x] + d;
                fa[y] = x;
                if (vis[y])
                    continue;
                vis[y] = 1;
                q.push(y);
            }
        }
    }
    vector<int>A;
    int x = 1;
    while (x != rt) {
        A.push_back(e[fa[x]][x].top().se);
        in[e[fa[x]][x].top().se] = fa[x];
        x = fa[x];
    }
    for (auto x : A)
        for (int i = 1; i <= rt; i++)
            if (i != x)
                e[i][in[x]].push(mk(-c[x][i] + c[x][in[x]], x));
    return dis[1];
}
signed main() {
    n = read(), k = read();
    for (int i = 1; i <= k; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; ++j)
            c[i][j] = read();
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += c[i][1], in[i] = 1;
    for (int j = 2; j <= k; ++j) {
        for (int i = 1; i <= n; i++)
            e[j][in[i]].push(mk(c[i][in[i]] - c[i][j], i));
        int k = a[j];
        while (k--) {
            for (int u = 1; u <= j; ++u)
                for (int v = 1; v <= j; ++v)
                    while (e[u][v].size() && in[e[u][v].top().se] != v)
                        e[u][v].pop();
            ans += SPFA(j);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

C

若字符串 在字符串 前面，那么需要满足 。直接 sort 就可以做到 的复杂度。

不妨将 和 画出来观察（这里假设 ）

aaabbbbbb
bbbbbbaaa

这里用 a 来代替 中字符， b 来代替 中字符。同时用 表示字符串 以 开头的后缀。

我们发现，若 不是 的前缀，我们可以直接比较 的大小。这里可以用 比较 序来实现，

否则，把 分成三部分，其中第一部分为开头长为 的字符串，第三部分为末尾长为 的字符串，剩下字符为第二部分。那么就可以依次比较一、二、三部分的字符串从而得到 和 的大小关系。

由于 是 的前缀，所以第一部分是相同的。而第二部分就是 与 本身比较大小。这使我们想到 exkmp ，因为 exkmp 能在线性时间内求出字符串 的每一个后缀与 的 。

若第二部分也相同，我们比较第三部分，也就是 与 比较大小。由于 是 的前缀，所以等价于 和 比较大小。也能用 exkmp 快速找到 并比较下一位字符。

至此，时间复杂度 ，但由于 常数较大，需要进行一些写法上的优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 9;
void chmx(int &x, int y) {
    (x < y) &&(x = y);
}
void chmn(int &x, int y) {
    (x > y) &&(x = y);
}
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
vector<int>z[N];
string s[N];
void get(vector<int> &z, string &s) {
    int n = s.size() - 1;
    z.resize(n + 1);
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        if (i <= r)
            z[i] = min(z[i - l + 1], r - i + 1);
        while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
}
int ed[N], dfn[N * 10], sz[N * 10], b[N];
struct trie {
    int son[N * 10][5];
    int idx, id;
    trie() {
        idx = 1;
    }
    int add(string &s) {
        int x = 1, n = s.size() - 1;
        for(int i = 1;i <= n; i++) {
            int nt = s[i] - '0';
            if (!son[x][nt])
                son[x][nt] = ++idx;
            x = son[x][nt];
        }
        return x;
    }
    void dfs(int x) {
        dfn[x] = ++id;
        sz[x] = 1;
        for(int i = 0;i <= 4; i++)if (son[x][i]) {
            dfs(son[x][i]);
            sz[x] += sz[son[x][i]];
        }
    }
} T;
int a[N], len[N];
bool in(int x, int y) {
    x = ed[x];
    y = ed[y];
    return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + sz[x] ||
           dfn[y] <= dfn[x] && dfn[x] < dfn[y] + sz[y];
}
bool cmp(int x, int y) {
    if (!in(x, y))
        return dfn[ed[x]] < dfn[ed[y]];
    if (ed[x] == ed[y])
        return 0;
    if (len[x] < len[y]) {
        int k = z[y][len[x] + 1];
        if (k == len[y] - len[x]) {
            k = z[y][len[y] - len[x] + 1];
            if (k == len[x])
                return 0;
            return s[y][len[y] - len[x] + k + 1] < s[x][k + 1];
        }
        return s[y][k + 1] < s[y][len[x] + k + 1];
    } else {
        swap(x, y);
        int k = z[y][len[x] + 1];
        if (k == len[y] - len[x]) {
            k = z[y][len[y] - len[x] + 1];
            if (k == len[x])
                return 0;
            return s[y][len[y] - len[x] + k + 1] > s[x][k + 1];
        }
        return s[y][k + 1] > s[y][len[x] + k + 1];
    }
}
signed main() {
    int n = read();
    for(int i = 1;i <= n; i++) {
        cin >> s[i];
        s[i] = "0" + s[i];
        len[i] = s[i].size() - 1;
        get(z[i], s[i]);
        ed[i] = T.add(s[i]);
        a[i] = i;
    }
    T.dfs(1);
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1;i <= n; i++) for(int j = 1;j <= len[a[i]]; j++)putchar(s[a[i]][j]);
    return 0;
}

D

对于 的情况，设 表示从 走到 的期望步数。最终答案就是 到 路径上每条边的期望步数之和。那么有转移式子：
把 移到左边去
可知， 最终等于 。因为子树内每一条边会被计算两次， 到 的边会被计算一次。

考虑一条单向边 的贡献，对于子树内的 没有影响。而对于 ，相比原来的值减少了 ，也就是减少了 ，并且对于所有是 祖先的 值都减少了 。因为这等价于直接砍掉 这棵子树（因为到不了）。

换言之，一个点 对祖先 有贡献当且仅当它们之间不存在单向边。这个贡献可以组合数来求。并且由于产生贡献的距离连续，在 dfs 的时候维护区间左右端点然后区间求和。

具体的，对于距离为 的两个点 ， 对于 的贡献为：

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N = 1e6 + 9;
const int p = 998244353;
bool vis[N];
int n, k, s, fa[N], dep[N], cnt, D;
int  a[N], ans;
vector <int> e[N];
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int inv(int x, int base = p - 2) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = 1ll * res * x % p;

        x = 1ll * x * x % p;
        base >>= 1;
    }
    return res;
}
void dfs(int x, int f) {
    fa[x] = f, dep[x] = dep[f] + 1;
    for (auto v : e[x])
        if (v != f)
            dfs(v, x);
}
int  calc(int x, int y) {
    return y ? (a[x + y - 1] + p - a[y - 1]) % p : a[x + y - 1];
}
void dfs(int x) {
    if (dep[x])
        ans = (ans + calc(cnt, D)) % p;
    for (auto to : e[x])
        if (to != fa[x]) {
            cnt += vis[to];
            D += 1 - vis[to];
            dfs(to);
            cnt -= vis[to];
            D -= 1 - vis[to];
        }
}
signed main() {
    n = read(), k = read(), s = read();
    for (int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        e[x].pb(y);
        e[y].pb(x);
    }
    dep[0] = -1;dfs(1, 0);
    for (int x = s; x; x = fa[x])
        vis[x] = 1;
    a[0] = 1;
    for (int i = 1; i <= n; i++)
        a[i] = a[i - 1] * (n - i - k) % p * inv(n - i, p - 2) % p;
    for (int i = 1; i <= n; i++)
        a[i] = (a[i] + a[i - 1]) % p;
    dfs(1);
    ans = (ans * 2 - dep[s] + p) % p;
    printf("%lld\n", ans);
    return 0;
}

E

如果两个电线相交，我们交换第一个相遇的位置以后的路径，这样就从原本的 变成了 ，也就是交换终点。因为不合法的方案与 两两对应，所以最后答案就是 的方案数减去 的方案数。

考虑如何计算从 到 的方案数（其余同理）。对于一条弦 ，设交点编号按照从 到 的顺序分别为 。 发现贡献这些交点的弦的起点也是从小到大的顺序。并且对于一条从 或 进入的路径，可以从任意 或 出去。那么记录 表示终点在第 条最后一个交点的方案数。 表示终点在圆上第 个顶点的方案数。对于转移，有如下几种：

• 当前点由上一个点走一条圆弧得来，。
• 当前点是一条弦 的终点，。
• 以当前起点新增一条弦 ，按交点顺序遍历弦 。显然 就是所有 的和加上 （ 是这条弦的起点）。由于弦 和弦 的交点肯定是弦 的最后一个交点，所以对所有的 做一遍前缀和再加上 。

时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
const int p = 998244353;
int n, m, L, res1, res2;
int a[N], id[N], f[N], g[N];
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
void work(int S) {
    memset(g, 0, sizeof g);
    memset(f, 0, sizeof f);
    f[S] = 1;
    for (int i = S, j = 1; i <= n; i++) {
        if(i != S)f[i] = f[i - 1];
        if (i == a[j] + L)
            (f[i] += g[j]) %= p, j++;
        if (!id[i])
            continue;
        int sum = f[i];
        for (int k = j; k <= id[i]; k++)
            (g[k] += sum) %= p, sum = g[k];
    }
}
signed main() {
    n = read(), m = read(), L = read();
    for (int i = 1; i <= m; i++)
        a[i] = read();
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= m; i++)
        id[a[i]] = i;
    work(1);
    res1 = f[n] + 1, res2 = f[n - 1];
    work(2);
    res1 = (1ll * res1 * f[n - 1] + p - 1ll * res2 * f[n] % p ) % p;
    cout << res1 << endl;
    return 0;
}

F

对于树上的问题，发现有解当且仅当图是一条链，且询问的两点是链的端点。

对于一般无向图，有解当且仅当建出圆方树后当且仅当方点构成一条链，询问两点分别位于两个方点端点，并且两个点不能是割点。

用 求解点双，时间复杂度 。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 4e5 + 9;
int n, m, q, idx, top;
int dfn[N], sta[N], low[N], color, d[N], w[N];
vector <int> c[N], e[N], E[N];
void chmn(int &x, int y) {
    (x > y) &&(x = y);
}
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
void tarjan(int x) {
    dfn[x] = low[x] = ++ idx;
    sta[++ top] = x;
    for (auto to : e[x]) {
        if (!dfn[to]) {
            tarjan(to), chmn(low[x], low[to]);
            if (low[to] >= dfn[x]) {
                c[++ color].push_back(x);
                int now = 0;
                while (now != to)
                    now = sta[top --], c[color].pb(now);
            }
        } else
            low[x] = min(low[x], dfn[to]);
    }
}
bool flag = 1;
int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        e[x].pb(y), e[y].pb(x);
    }
    tarjan(1);
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) {
            flag = 0;
            break;
        }
    int L = 0, R = 0;
    if (flag) {
        for (int i = 1; i <= color; i++)
            for (auto x : c[i])
                E[n + i].pb(x), E[x].pb(n + i), ++ d[x], ++ d[n + i];
        for (int x = 1; x <= n + color; x++)
            if (d[x] > 1)
                for (auto to : E[x])
                    if (d[to] > 1)
                        ++ w[x];
        for (int i = 1; i <= n + color; i++)
            if (d[i] > 1) {
                if (w[i] > 2) {
                    flag = 0;
                    break;
                }
                if (!w[i]) {
                    L = R = i;
                    break;
                }
                if (w[i] == 1) {
                    L = R;
                    R = i;
                }
            }
    }
    q = read();
    while (q --) {
        int x = read(), y = read();
        if (!flag) {
            puts("NO");
            continue;
        }
        if (E[x].size() != 1 || E[y].size() != 1) {
            puts("NO");
            continue;
        }
        int fx = E[x][0], fy = E[y][0];
        if (fx > fy)
            swap(fx, fy);
        puts((fx == L && fy == R) ? "YES" : "NO");
    }
    return 0;
}

G

若把一个凸包看成相对于另一个凸包在移动，就转化为只有一个凸包在移动的问题了！

首先他们相撞时，一定是其中一个凸包的顶点与另一个凸包有交，这启发我们枚举相交顶点。

问题变成了一个凸包移动多久后会与一个点 相交。求法就是做一条平行于凸包速度，过 的直线 ，标记 和凸包的交点为 ，答案就是 之间的距离除以速度。

但因为这条直线和凸包可能会有两个交点，所以需要按照速度的法向量将凸包切成两半。而对于某一半凸包和一个点 的答案，只需要二分求出交点在凸包哪条线段上即可。

还有一种方法就是二分时间求出移动距离。做闵可夫斯基和求出凸包扫过的区域，然后判断两个凸包是否有交。但是常数略大。

#include <bits/stdc++.h>
#define y1 regrtefbgth
using namespace std;
using point = complex<double>;
#define x real
#define y imag
struct line {
    point a;
    point b;
    line(const point &a, const point &b) : a(a), b(b) {}
};
int sgn(const point &a) {
    if (a.y() > 0 || (a.y() == 0 && a.x() > 0)) {
        return 1;
    } else {
        return 0;
    }
}
double dot(const point &a, const point &b) {
    return (conj(a) * b).x();
}
double cross(const point &a, const point &b) {
    return (conj(a) * b).y();
}
point intersection(const line &l1, const line &l2) {
    return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}
int n, m;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    cin >> n;
    vector<point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = point(x, y);
    }
    cin >> m;
    vector<point> b(m);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        b[i] = point(-x, -y);
    }
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    point v(x2 - x1, y2 - y1);
    point sa = a[0], sb = b[0];
    for (int i = 0; i < n; i++) {
        if (a[i].y() < sa.y() || (a[i].y() == sa.y() && a[i].x() < sa.x())) {
            sa = a[i];
        }
    }
    for (int i = 0; i < m; i++) {
        if (b[i].y() < sb.y() || (b[i].y() == sb.y() && b[i].x() < sb.x())) {
            sb = b[i];
        }
    }
    auto s = sa + sb;
    vector<point> d(n + m);
    for (int i = 0; i < n; i++) {
        d[i] = a[(i + 1) % n] - a[i];
    }
    for (int i = 0; i < m; i++) {
        d[n + i] = b[(i + 1) % m] - b[i];
    }
    sort(d.begin(), d.end(), [&](point a, point b) {
        if (sgn(a) != sgn(b)) {
            return sgn(a) == 1;
        }
        return cross(a, b) > 0;
    });
    vector<point> c(n + m);
    c[0] = s;
    for (int i = 0; i < n + m - 1; i++) {
        c[i + 1] = c[i] + d[i];
    }
    int N = n + m;
    bool in = true;
    for (int i = 0; i < N; i++) {
        if (cross(c[i], c[(i + 1) % N]) < 0) {
            in = false;
        }
    }
    if (in) {
        puts("0");
        return 0;
    }
    if (v == point(0, 0)) {
        puts("-1");
        return 0;
    }
    double ans = -1;
    for (int i = 0; i < N; i++) {
        auto a = c[i], b = c[(i + 1) % N];
        if (cross(b - a, v) == 0) {
            continue;
        }
        auto p = intersection(line(0, v), line(a, b));
        if (dot(v, p) >= 0 && dot(p - a, b - a) >= 0 && dot(p - b, a - b) >= 0) {
            double t = sqrt(dot(p, p) / dot(v, v));

            if (ans < 0 || ans > t) {
                ans = t;
            }
        }
    }
    if (ans < 0) {
        puts("-1");
        return 0;
    }
    cout << ans << endl;
    return 0;
}

H

前置知识：后缀数组

先将所有串连到一起，中间加分隔符，然后后缀排序，并求出 数组。

对于 中以第 个字符为开头的后缀，设它的 为 ，求出 串中 比 小的最大的 值和 比 大的最小的 值，分别设为 和 ，那么该后缀所能贡献的最大的答案（不妨设为 ）即为 。其中 表示 的最大子段和， 求法可以使用线段树维护，具体方法可见 GSS1 的题解。

剩余的问题是如何找到 的前驱后继（即 和 ），只需要枚举 ，用变量记录最后一次出现的 中位置，正反各扫一遍即可，求 区间 也不需要 表，在遇到 中位置时改为该位置 ，否则取 即可。

时间复杂度 。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 1e5 + 10, maxn = 1.2e6 + 10;
std::vector<int> sa_is(const std::vector<int> &s, int upper) {
    int n = int(s.size());
    std::vector<int> sa(n);
    std::vector<bool> ls(n);

    for (int i = n - 2; i >= 0; i--) {
        ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
    }

    std::vector<int> sum_l(upper + 1), sum_s(upper + 1);

    for (int i = 0; i < n; i++) {
        if (!ls[i]) {
            sum_s[s[i]]++;
        } else {
            sum_l[s[i] + 1]++;
        }
    }

    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];

        if (i < upper)
            sum_l[i + 1] += sum_s[i];
    }

    auto induce = [&](const std::vector<int> &lms) {
        std::fill(sa.begin(), sa.end(), -1);
        std::vector<int> buf(upper + 1);
        std::copy(sum_s.begin(), sum_s.end(), buf.begin());

        for (auto d : lms) {
            if (d == n)
                continue;

            sa[buf[s[d]]++] = d;
        }

        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        sa[buf[s[n - 1]]++] = n - 1;

        for (int i = 0; i < n; i++) {
            int v = sa[i];

            if (v >= 1 && !ls[v - 1]) {
                sa[buf[s[v - 1]]++] = v - 1;
            }
        }

        std::copy(sum_l.begin(), sum_l.end(), buf.begin());

        for (int i = n - 1; i >= 0; i--) {
            int v = sa[i];

            if (v >= 1 && ls[v - 1]) {
                sa[--buf[s[v - 1] + 1]] = v - 1;
            }
        }
    };

    std::vector<int> lms_map(n + 1, -1);
    int m = 0;

    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms_map[i] = m++;
        }
    }

    std::vector<int> lms;
    lms.reserve(m);

    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms.push_back(i);
        }
    }

    induce(lms);

    if (m) {
        std::vector<int> sorted_lms;
        sorted_lms.reserve(m);

        for (int v : sa) {
            if (lms_map[v] != -1)
                sorted_lms.push_back(v);
        }

        std::vector<int> rec_s(m);
        int rec_upper = 0;
        rec_s[lms_map[sorted_lms[0]]] = 0;

        for (int i = 1; i < m; i++) {
            int l = sorted_lms[i - 1], r = sorted_lms[i];
            int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
            int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
            bool same = true;

            if (end_l - l != end_r - r) {
                same = false;
            } else {
                while (l < end_l) {
                    if (s[l] != s[r]) {
                        break;
                    }

                    l++;
                    r++;
                }

                if (l == n || s[l] != s[r])
                    same = false;
            }

            if (!same)
                rec_upper++;

            rec_s[lms_map[sorted_lms[i]]] = rec_upper;
        }

        auto rec_sa =
            sa_is(rec_s, rec_upper);

        for (int i = 0; i < m; i++) {
            sorted_lms[i] = lms[rec_sa[i]];
        }

        induce(sorted_lms);
    }

    return sa;
}
int id[maxn], inf = 255, len, mx, n, pos[maxm], rk[maxn];
vector<int>s, sa;
char t[maxm];
inline void suffix_sort() {
    sa = sa_is(s, inf);

    for (int &i : sa)
        ++i;

    sa.insert(sa.begin(), 0);

    for (int i = 0; i < sa.size(); ++i)
        rk[sa[i]] = i;
}
int ht[maxn];
inline void calc_ht() {
    for (int i = 1, h = 0; i <= n; ++i) {
        if (h)
            --h;

        int j = sa[rk[i] - 1];

        while (s[i - 1 + h] == s[j - 1 + h])
            ++h;

        ht[rk[i]] = h;
    }
}
int a[maxm], k, m;
struct node {
    ll l, mx, r, sum;
    inline node(ll v = 0): mx(v) {}
    inline node(ll l_, ll mx_, ll r_, ll sum_): l(l_), mx(mx_), r(r_), sum(sum_) {}
    inline node operator+(const node &k)const {
        if (mx == LLONG_MIN)
            return k;

        return {max(l, sum + k.l), max({mx, r + k.l, k.mx}), max(r + k.sum, k.r), sum + k.sum};
    }
};
struct SGT {
    node v[maxm << 2];
    void build(int p, int l, int r) {
        if (l == r) {
            v[p] = {a[l], a[l], a[l], a[l]};
            return;
        }

        int mid = l + r >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        v[p] = v[p << 1] + v[p << 1 | 1];
    }
    node query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return v[p];

        int mid = l + r >> 1;
        node ret(LLONG_MIN);

        if (ql <= mid)
            ret = ret + query(p << 1, l, mid, ql, qr);

        if (qr > mid)
            ret = ret + query(p << 1 | 1, mid + 1, r, ql, qr);

        return ret;
    }
} T;
ll ans[maxm];
int main() {
    scanf("%d%d%d%s", &n, &m, &k, t + 1);
    len = n;

    for (int i = 1; i <= len; ++i)
        s.push_back(t[i]);

    for (int i = 1; i <= m; ++i)
        scanf("%d", a + i);

    T.build(1, 1, m);

    for (int i = 1; i <= k; ++i) {
        scanf("%s", t + 1);
        pos[i] = ++n, s.push_back(++inf);

        for (int j = 1; j <= m; ++j)
            id[++n] = i, s.push_back(t[j]);
    }

    suffix_sort();
    calc_ht();

    for (int i = 1, h = 0; i <= n; ++i) {
        if (1 <= sa[i] && sa[i] <= len)
            h = ht[i + 1];
        else if (h && id[sa[i]])
            ans[id[sa[i]]] = max(ans[id[sa[i]]], T.query(1, 1, m, sa[i] - pos[id[sa[i]]],
                                 sa[i] - pos[id[sa[i]]] + h - 1).mx);

        h = min(h, ht[i + 1]);
    }

    for (int i = n, h = 0; i; --i) {
        if (1 <= sa[i] && sa[i] <= len)
            h = ht[i];
        else if (h && id[sa[i]])
            ans[id[sa[i]]] = max(ans[id[sa[i]]], T.query(1, 1, m, sa[i] - pos[id[sa[i]]],
                                 sa[i] - pos[id[sa[i]]] + h - 1).mx);

        h = min(h, ht[i]);
    }

    for (int i = 1; i <= k; ++i)
        printf("%lld\n", ans[i]);

    return 0;
}

J

由于到达一个点时具有方向，所以我们把边看成点，在十字路口的时候连边。由于边权只有 两种，所以用 可以做到 。具体实现为，若到下一个点的边权为 ，就塞入队头，否则塞入队尾。每次取队头更新。也可以用优先队列直接跑最短路。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
struct node {
    int x, y, w;
};
int n, sx, sy, tx, ty, ans;
int v[N][4], dis[N][4], p[5];
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int main() {
    deque<node>q;
    n = read();
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 4; j++) {
            v[i][j] = read();
            dis[i][j] = N;
        }
    sx = read();
    sy = read();
    tx = read();
    ty = read();
    q.push_front(node{sx, sy, 0});
    while (q.size()) {
        int x, y, w, nt;
        node now = q.front();
        q.pop_front();
        x = now.x;
        y = now.y;
        w = now.w;
        if (!y)
            continue;
        for (int i = 0; i < 4; i++)
            if (v[x][i] == y)
                nt = i;
        if (dis[x][nt] <= w)
            continue;
        else
            dis[x][nt] = w;
        for (int i = 0; i < 4; i++)
            if (v[y][i] == x)
                nt = (i + 1) % 4;
        for(int i = 0; i < 4; i++){
            if(i == nt) q.push_front(node{y, v[y][i], w});
            else q.push_back(node{ y, v[y][i], w + 1});
        }
    }
    for (int i = 0; i < 4; i++)
        if (v[tx][i] == ty)
            ans = dis[tx][i];
    if (ans == N)
        ans = -1;
    cout << ans << endl;
    return 0;
}