A

发现随着时间的增加，凸包的每个顶点都是沿着角平分线移动。当两个相邻的顶点相交时，整个凸包的形状就会改变。

每次找到最近发生变化的顶点，可以通过距离计算出移动的时间。同样就能求出其他所有点移动距离从而求得新的凸包。

对于凸包形状不变的一段时间，面积是关于时间的一个二次函数，求出这个二次函数输出答案即可。

#include <bits/stdc++.h>
#define P pair<double,int>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 9;
const double eps = 1e-8;
int n, m;
double ans[N];
struct node {
    double x, y;
    node() {}
    node(double a, double b) {
        x = a, y = b;
    }
    node operator+(const node &a)const {
        return node(x + a.x, y + a.y);
    }
    node operator-(const node &a)const {
        return node(x - a.x, y - a.y);
    }
    double operator*(const node &a)const {
        return x * a.y - y * a.x;
    }
    node operator*(const double &a)const {
        return (node) {
            x *a, y *a
        };
    }
    node operator/(const double &a)const {
        return (node) {
            x / a, y / a
        };
    }
    double len() {
        return sqrt(x * x + y * y);
    }
} p[N];
struct Line {
    node a, b;
    Line swap() {
        return (Line) {
            b, a
        };
    }
    double getarea() {
        return a * b;
    }
    double len() {
        return (a - b).len();
    }
} L[N];
P q[N];
vector<int>v;
node getinp(Line x, Line y) {
    node a = x.a - y.a, b = x.a - x.b, c = y.b - y.a;
    double t = -(c * a) / (c * b);
    return  node(x.a.x + b.x * t, x.a.y + b.y * t);
}
Line getabd(Line l1, Line l2) {
    swap(l2.a, l2.b);
    node x = getinp(l1, l2);
    node a = x;
    node b = x + ((l1.b - l1.a) / l1.len() + (l2.b - l2.a) / l2.len());
    return (Line) {
        a, b
    };
}
double getdist(node a, Line b) {
    node c = b.b - b.a;

    if (abs(c.x) <= eps)
        return abs(a.x - b.a.x);

    double A = c.y / c.x;
    double C = b.a.y - b.a.x * A;
    double B = -1.0;
    return abs((A * a.x + B * a.y + C) / sqrt(A * A + B * B));
}
int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &p[i].x, &p[i].y), v.push_back(i);

    p[n + 1] = p[1];

    for (int i = 1; i <= n; ++i)
        L[i] = (Line) {
        p[i], p[i + 1]
    };

    scanf("%d", &m);

    for (int i = 1; i <= m; ++i)
        scanf("%lf", &q[i].fi), q[i].se = i;

    sort(q + 1, q + m + 1);
    int l = 1;

    while ((int)v.size() > 2) {
        int s = (int)v.size();
        int pos = 0;
        double S = 0;
        double t = 1e6;
        double A = 0, B = 0, C = 0;

        for (int i = 0; i < s; ++i) {
            Line pre = L[v[(i - 1 + s) % s]], suf = L[v[(i + 1) % s]], now = L[v[i]];
            Line now1 = (Line) {
                getinp(pre, now.swap()), getinp(now, suf.swap())
            };
            S += now1.getarea();
            Line line1 = getabd(now, pre);
            Line line2 = getabd(suf, now);
            node inp = getinp(line1, line2);
            double tt = getdist(inp, now);
            node a = now1.a - inp, b = now1.b - inp;
            double S1 = a * b / 2.0;
            A += S1;
            B += -2.0 / tt * S1;
            C += 1.0 / tt / tt * S1;

            if (tt < t)
                pos = i, t = tt;
        }

        S /= 2.0;

        for (; l <= m && (abs(q[l].fi - t) <= eps || q[l].fi <= t); ++l)
            ans[q[l].se] = S + (q[l].fi * B + q[l].fi * q[l].fi * C);

        v.erase(v.begin() + pos);
    }

    for (int i = 1; i <= m; ++i)
        printf("%.10f\n", ans[i]);

    return 0;
}

B

若 ，把概率看成边权，直接矩阵树定理求解。时间复杂度

用 表示第 条边在时间 的概率，用 代替 ，每个 形如 的形式，然后带入到原来的行列式 里。

根据行列式的一些基本操作，可以把行列式 看成 ，其中 只由 组成， 只由 组成。

把 变换成单位矩阵，即满足 ，同时 也应该做相同变换。（因为本质同一个行列式拆分成两个），得到 。现在考虑如何求解

这个形式等价于求 的特征多项式。一般解法就是化为上海森堡矩阵在 时间内求出多项式，然后乘回 就变成答案关于 ，即 的多项式。

每一项单独等比数列求和得到答案，最终复杂度 。注意， 答案为 。

#include <bits/stdc++.h>
using namespace std;
const int N = 6e2 + 9;
const int p = 998244353;
int a[N][N], b[N][N];
int n, m, t, A;
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 gauss(int n) {

    for (int i = 1; i <= n; i++) {

        if (a[i + 1][i] == 0) {
            bool flag = 0;

            for (int j = i + 2; j <= n; j++) {
                if (a[j][i] != 0) {
                    for (int k = i ; k <= n; k++)
                        swap(a[i + 1][k], a[j][k]);

                    for (int k = i ; k <= n; k++)
                        swap(a[k][i + 1], a[k][j]);

                    flag = 1;
                    break;
                }
            }

            if (!flag)
                continue;
        }

        int t = inv(a[i + 1][i]), tmp;

        for (int j = i + 2; j <= n; j++) {
            tmp = 1ll * t * a[j][i] % p;

            for (int k = i ; k <= n; k++)
                a[j][k] = (a[j][k] - 1ll * tmp * a[i + 1][k] % p + p) % p;

            for (int k = 1 ; k <= n; k++)
                a[k][i + 1] = (a[k][i + 1] + 1ll * tmp * a[k][j]) % p;
        }

    }

}
void poly(int n) {
    int tmp, t;
    b[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (j)
                b[i][j] = (0ll + p - b[i - 1][j - 1] + 1ll * b[i - 1][j] * a[i][i] % p) % p;
            else
                b[i][j] = 1ll * b[i - 1][j] * a[i][i] % p;
        }

        t = p - a[i][i - 1];

        for (int j = i - 1; j >= 1; j--) {
            tmp = 1ll * t % p * a[j][i] % p;

            for (int k = 0; k <= n; k++)
                b[i][k] = (b[i][k] + 1ll * tmp * b[j - 1][k]) % p;

            t = 1ll * t * (p - a[j][j - 1]) % p;
        }
    }
}
int B[N][N], K[N][N], C = 1;
void Inv(int n) {
    int tmp;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            K[i][j + n] = B[i][j];

    for (int i = 1; i < n; i++) {
        if (K[i][i] == 0) {
            for (int j = i + 1; j <= n; j++) {
                if (K[j][i]) {
                    swap(K[j], K[i]);
                    C = -C;
                    break;
                }
            }
        }

        C = 1ll * K[i][i] * C % p;
        tmp = inv(K[i][i]);

        for (int j = i + 1; j <= n + n; j++)
            K[i][j] = 1ll * tmp * K[i][j] % p;

        for (int k = 1; k <= n; k++) {
            if (i == k)
                continue;

            tmp = K[k][i];

            for (int j = 1; j <= n + n; j++)
                K[k][j] = (K[k][j] - 1ll * tmp * K[i][j]) % p;
        }
    }
}
int fa[N];
int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}
int main() {
    n = read(), m = read(), t = read(), A = read();

    if (n == 1 || m == 0) {
        puts("0");
        return 0;
    }

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    for (int i = 1; i <= m; i++) {
        int x, y, a, b, P, Q;
        x = read(), y = read();
        fa[get(x)] = get(y);
        a = read(), b = read();
        P = 1ll * a * inv(b) % p;
        a = read(), b = read();
        Q = 1ll * a * inv(b) % p;
        K[x][y] = (0ll + K[x][y] + p - P + Q) % p;
        K[y][x] = (0ll + K[y][x] + p - P + Q) % p;
        K[y][y] = (0ll + K[y][y] + p + P - Q) % p;
        K[x][x] = (0ll + K[x][x] + p + P - Q) % p;
        B[x][y] = (B[x][y] + p - Q) % p;
        B[y][x] = (B[y][x] + p - Q) % p;
        B[x][x] = (B[x][x] + Q) % p;
        B[y][y] = (B[y][y] + Q) % p;
    }

    for (int i = 1; i <= n; i++)
        if (get(i) != get(1)) {
            puts("0");
            return 0;
        }

    Inv(n);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = K[i][j + n];

    gauss(n - 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = -a[i][j];

    poly(n - 1);
    int x = 1, X = 1, ans = 0;
    A = inv(A);

    for (int i = 0; i <= n; i++) {
        if (x == 1)
            X = t;
        else
            X = 1ll * (inv(x, t) - 1) * inv(x - 1) % p;

        ans = (ans + 1ll * X * b[n - 1][i]) % p;
        x = 1ll * x * A % p;
    }

    if (~n & 1)
        C = -C;

    ans = 1ll * ans * C % p;
    ans = (ans + p) % p;
    printf("%d\n", ans);
    return 0;
}

C

结论是，输出所有的 。其中设答案数量为 。

有递推式 ，考虑把答案分成两类：

• ，那么有 ，和 ，其中后者方案数为 。
• ，那么有 ，和 ，其中后者方案数为

所以总共增加的方案数为 种，满足递推式。相应的，就可以求出通项公式：
$$
化简即可发现满足要求。

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
int main() {
    int i, j;
    cin >> n;
    int k;
    m = (n * (n - 1) / 2.0 - n) / 3.0 + 1;
    cout << m << endl;

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            k = n - i - j;

            if (k <= 0)
                k += n;

            if (k > j)
                printf("%d %d %d\n", i, j, k);
        }

    return 0;
}

D

设 为转到 的概率， 表示从 变成 的期望次数， 表示转动一次能使 变大的概率。那么根据这一次转盘是否有效能得到以下式子：
$\mathcal O(n^2)$ 的。观察转移式发现只有可能从小往大转移，是有方向的。

若枚举一个分界线 ，我们想快速用 去贡献 。因为是异或卷积的形式，可以用 加速。于是在外面套一层 分治，每次用区间右边去贡献区间左边。时间复杂度 。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = (1 << 16) + 5;
const int p = 1000000007;
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 fwt(int *a, int *b, int n, int flag = 0) {
    for (int i = 0; i < n; ++i)
        b[i] = a[i];
    for (int i = 0; (1 << i) < n; ++i) {
        int t = 1 << i;
        for (int j = 0; j < n; j += t << 1) {
            int *f = b + j, *g = b + j + t;

            for (int k = 0; k < t; ++k) {
                int s = g[k];
                g[k] = (f[k] - s + p) % p;
                f[k] = (f[k] + s) % p;
            }
        }
    }
    if (flag) {
        int iv = inv(n);
        for (int i = 0; i < n; ++i)
            b[i] = 1ll * b[i] * iv % p;
    }
}
int f[N], g[N], a[N], b[N], c[N];
void solve(int l, int r) {
    if (l == r) {
        if (g[l])
            f[l] = 1ll * (f[l] + 1) * inv(g[l]) % p;
        return;
    }
    int mid = (l + r) / 2;
    solve(mid + 1, r);
    int t = l ^ (mid + 1);
    fwt(a + t, b, mid + 1 - l);
    fwt(f + mid + 1, c, mid + 1 - l);
    for (int i = 0; i < mid + 1 - l; ++i)
        c[i] = 1ll * c[i] * b[i] % p;
    fwt(c, c, mid + 1 - l, 1);
    for (int i = l; i <= mid; ++i)
        f[i] = (f[i] + c[i - l]) % p,
               g[i] = (g[i] + b[0]) % p;
    solve(l, mid);
}
int T, n;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; ++i)
            cin >> a[i], sum += a[i], f[i] = g[i] = 0;
        sum = inv(sum);
        for (int i = 0; i < n; ++i)
            a[i] = 1ll * sum * a[i] % p;
        solve(0, n - 1);
        cout << f[0] << endl;
    }
    return 0;
}

E

首先有一个操作分块的做法。把每 个操作分成一段。每次整段操作完了后，重新求出 序，对于每种颜色分别开一个数组，每次进去二分子树区间查找答案。至于散块，每次暴力 即可。时间复杂度 。实现精细的话，能卡过。

考虑另一个比较正常一点的做法，子树操作转化为序列操作。但是因为有动态加叶子，所以需要一个能动态维护子树的数据结构。直接用 ，平衡树维护括号序即可，当然也可以是 。

每次新插入一个叶子，让他一定是父亲的第一个儿子。这样他的管辖范围的右端点一定是下一个兄弟，或者是父亲的右端点。插在后面的话还要更改前一个兄弟，前一个兄弟的儿子.......的右端点，比较麻烦。

维护真正的 肯定是不现实的，但是只需要知道 的相对大小关系。有一个想法是：点 插入到 之间时，令 。要卡也非常容易，同一个位置一直插入，很快就寄掉了。

我们需要选择一些时候暴力重构 ，以保证正确性。于是考虑替罪羊树。因为节点数为 ，重构因子为 的树，高度不超过 ，只要保证这个值小于 即可。然后对于每一个颜色开一个平衡树，差分维护答案。时间复杂度 ，空间复杂度 。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 9;
const double alpha = 0.7;
int T, n, m, op, u, c, ans;
struct scapegoat_tree {
    int rt, cnt, idx, id, fa, d;
    int ls[N], rs[N], sz[N], t[N], nt[N], ed[N];
    ll l[N], r[N];
    void reset() {
        rt = sz[1] = idx = 1;
        l[1] = ls[1] = rs[1] = nt[1] = ed[1] = 0;
        r[1] = l[0] = r[0] = 1e18;
    }
    void pushup(int u) {
        sz[u] = sz[ls[u]] + sz[rs[u]] + 1;
    }
    bool ok(int u) {
        return max(sz[ls[u]], sz[rs[u]]) >= sz[u] * alpha;
    }
    void dfs(int u) {
        if (ls[u])
            dfs(ls[u]);
        t[++cnt] = u;
        if (rs[u])
            dfs(rs[u]);
    }
    int build(int L, int R, ll x, ll y) {
        if (L > R)
            return 0;
        int mid = (L + R) >> 1, u = t[mid];
        ll mid2 = (x + y) >> 1;
        l[u] = x, r[u] = y;
        ls[u] = build(L, mid - 1, x, mid2);
        rs[u] = build(mid + 1, R, mid2, y);
        pushup(u);
        return u;
    }
    void rebuild(int &u) {
        cnt = 0;
        dfs(u);
        u = build(1, cnt, l[u], r[u]);
    }
    void ins_(int &u, ll x, ll y, int Fa, int D) {
        if (!u) {
            sz[u = ++idx] = 1;
            ls[u] = rs[u] = 0;
            l[u] = x, r[u] = y;
            return;
        }
        ins_(ls[u], x, (x + y) >> 1, u, 0);
        pushup(u);
        if (ok(u))
            id = u, fa = Fa, d = D;
    }
    void inss(int u, int x, int Fa, int D) {
        if (u == x) {
            ins_(rs[u], (l[u] + r[u]) >> 1, r[u], u, 1);
            pushup(u);
            if (ok(u))
                id = u, fa = Fa, d = D;
            return;
        }
        if (l[x] + r[x] < l[u] + r[u])
            inss(ls[u], x, u, 0);
        else
            inss(rs[u], x, u, 1);
        pushup(u);
        if (ok(u))
            id = u, fa = Fa, d = D;
    }
    void ins(int u) {
        id = fa = d = 0;
        inss(rt, u, 0, 0);
        if (id) {
            if (id == rt)
                rebuild(rt);
            else if (d == 0)
                rebuild(ls[fa]);
            else
                rebuild(rs[fa]);
        }
        nt[idx] = ed[idx] = nt[u];
        nt[u] = idx;
    }
} T1;
struct fhq_treap {
    int rt[N], ls[N], rs[N], sz[N], rd[N], idx, t[N], x, y, z;
    void pushup(int u) {
        sz[u] = sz[ls[u]] + sz[rs[u]] + 1;
    }
    void split(int u, int x, int &l, int &r) {
        if (!u) {
            l = r = 0;
            return;
        }
        if (T1.l[u] + T1.r[u] < T1.l[x] + T1.r[x])
            l = u, split(rs[u], x, rs[u], r);
        else
            r = u, split(ls[u], x, l, ls[u]);
        pushup(u);
    }
    int merge(int u, int v) {
        if (!u || !v)
            return u ^ v;
        if (rd[u] < rd[v])
            rs[u] = merge(rs[u], v);
        else
            ls[v] = merge(u, ls[v]), u = v;
        pushup(u);
        return u;
    }
    void ins(int c) {
        t[++idx] = c;
        ls[idx] = rs[idx] = 0;
        sz[idx] = 1;
        rd[idx] = rand();
        split(rt[c], idx, x, y);
        rt[c] = merge(merge(x, idx), y);
    }
    int query(int c, int u) {
        split(rt[c], u, x, y);
        split(y, T1.ed[u], y, z);
        int res = sz[y];
        rt[c] = merge(merge(x, y), z);
        return res;
    }
    void clear() {
        for (int i = 1; i <= idx; ++i)
            rt[t[i]] = 0;
        idx = 0;
    }
} T2;
int main() {
    srand(114514123);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &c, &m);
        T1.reset(), T2.ins(c);
        ans = 0;
        while (m--) {
            scanf("%d%d%d", &op, &u, &c);
            op ^= ans, u ^= ans, c ^= ans;
            if (op == 1)
                T1.ins(u), T2.ins(c);
            else
                printf("%d\n", ans = T2.query(c, u));
        }
        T2.clear();
    }
    return 0;
}

F

有一个下界就是，总时间除以盘子数量上取整。设这个时间为 。

当 的时候， 把所有牛排尽可能多地塞进第一个盘子里，如果有一块塞不下了，就把它拆成两份，然后继续往第二个盘子里塞。所有烤盘按照塞进去的顺序开始烤就能到达这个下界。

当 的时候，显然是无法满足烤的时间最大的那块肉的，因为分在不同的烤盘里，时间会有重复的部分。一块牛排肯定不能在一个时间出现在两个烤盘上。只需要将时间调整为 即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int a[N], cnt = 1, lim = 0;
int n, m;
signed main() {
    scanf("%d%d", &n, &m);
    int sum = 0, t = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        t = max(t, a[i]);
        sum += a[i];
    }
    t = max(t, (sum - 1) / m + 1);
    for (int i = 1; i <= n; i++) {
        if (t - lim < a[i]) {
            printf("2 %lld 0 %lld %lld %lld %lld\n", cnt + 1, a[i] - (t - lim), cnt, lim, t);
            cnt++;
            lim = lim + a[i] - t;
        } else {
            printf("1 %lld %lld %lld\n", cnt, lim, lim + a[i]);
            lim += a[i];
            if (lim == t)
                cnt++, lim = 0;
        }
    }return 0;
}

G

设 的边数为 ，分解 。

枚举一个质因子 ，统计两个数 并且 的方案数。

发现所有合法的 只需要满足 含有质数 的个数小于 。

也就是 个（ 表示 的因子个数）。但是每次枚举所有的 不方便优化。不妨观察删掉上述 边构成的图。

发现居然是 个一模一样的图！那么 就有一个快速的计算方法，那就是枚举任意一个质因子 ，
$\rm min25$ 优化。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 9;
const int p = 1145140019;
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, f[N], g[N], d[N], w[N];
int T, pr[N], len;
bool vis[N];
void init(int n = 1e5) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i])
            pr[++len] = i, vis[i] = 1;
        for (int j = 1; j <= len; ++j) {
            if (pr[j] > n / i)
                break;
            vis[pr[j]*i] = 1;
            if (i % pr[j] == 0)
                break;
        }
    }
}
int cal() {
    int cnt = 0, t = sqrt(n), ml = 0;
    for (int i = 1; i <= n; i = n / (n / i) + 1)
        w[++cnt] = n / i;
    reverse(w + 1, w + cnt + 1);
    for (int i = 1; i <= cnt; ++i)
        g[i] = w[i] - 1;
    for (int i = 1; i <= len; ++i, ++ml) {
        int P = pr[i];
        if (P > t)
            break;
        for (int j = cnt; j; --j) {
            int l = w[j] / P;
            if (l < P)
                break;
            l = l <= t ? l : cnt - n / l + 1;
            g[j] = (g[j] + p - g[l] + i - 1) % p;
        }
    }
    for (int i = 1; i <= cnt; ++i)
        f[i] = g[i], d[i] = (2 * f[i]) % p;
    for (int i = ml; i >= 1; --i) {
        int P = pr[i];
        for (int j = cnt; j; --j) {
            int l = w[j] / P;
            if (l < P)
                break;
            for (int c = 1; l >= P; ++c, l /= P) {
                int pos = l <= t ? l : cnt - n / l + 1;
                d[j] = (d[j] + (c + 1) * (d[pos] + p - 2LL * i) % p + c + 2) % p,
                       f[j] = (f[j] + (c + 1) * (f[pos] + p - i) % p + c * (d[pos] + p - 2ll * i) % p + c + 1) % p;
            }
        }
    }
    return f[cnt];
}
signed main() {
    T = read();
    init();
    while (T--) {
        n = read();
        printf("%lld\n", cal());
    }
    return 0;
}

H

若把互相能到达的点看成同一个点，那么不同的点只有 个。于是将整个坐标系用 大小的矩形分割开来，然后将所有矩阵重合于以 为左下角，大小为 的矩阵。若存在一个点未被覆盖，那么他就是合法答案。

一个输入的矩形最多会被分成 部分，暴力拆解，然后用扫描线做一遍矩形并即可。按照 坐标扫，维护区间最小值是否为 。时间复杂度 。

#include <bits/stdc++.h>
#define y1 qweqdfrgedt
using namespace std;
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;
}
struct node {
    int L, R;
};
struct Seg {
#define ls p<<1
#define rs p<<1|1
    int mn[N << 2], tag[N << 2], L, R, W;
    void push_up(int p) {
        mn[p] = min(mn[ls], mn[rs]);
    }
    void push_down(int p) {
        if (tag[p]) {
            tag[ls] += tag[p], mn[ls] += tag[p];
            tag[rs] += tag[p], mn[rs] += tag[p];
            tag[p] = 0;
        }
    }
    void change(int p, int l, int r) {
        if (l >= L && r <= R) {
            mn[p] += W, tag[p] += W;
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if (L <= mid)
            change(ls, l, mid);
        if (R > mid)
            change(rs, mid + 1, r);
        push_up(p);
    }
    int get(int p, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        push_down(p);
        if (!mn[ls])
            return get(ls, l, mid);
        else
            return get(rs, mid + 1, r);
    }
    int query1(int n) {
        if (mn[1])
            return -1;
        return get(1, 1, n) - 1;
    }
} T;
vector<node> Add[N], Del[N];
int n, d;
void get(int &x) {
    x = (x % d + d) % d;
}
void push(int x1, int x2, int y1, int y2) {
    if (x1 >= x2 || y1 >= y2)
        return;
    Add[x1].push_back(node{y1 + 1, y2});
    Del[x2].push_back(node{y1 + 1, y2});
}
void add(int x1, int x2, int y1, int y2) {
    if (y2 - y1 >= d) {
        push(x1, x2, 0, d);
        return;
    }
    get(y1), get(y2);
    if (y1 > y2) {
        push(x1, x2, y1, d), push(x1, x2, 0, y2);
    } else
        push(x1, x2, y1, y2);
}
signed main() {
    int x1, y1, x2, y2;
    n = read(), d = read();
    for (int i = 0; i < n; i++) {
        x1 = read(), y1 = read(), x2 = read(), y2 = read();
        if (x2 - x1 >= d) {
            add(0, d, y1, y2);
            continue;
        }
        get(x1), get(x2);
        if (x1 > x2) {
            add(x1, d, y1, y2), add(0, x2, y1, y2);
        } else
            add(x1, x2, y1, y2);
    }
    for (int i = 0; i < d; i++) {
        for (auto x : Add[i])
            T.L = x.L, T.R = x.R, T.W = 1, T.change(1, 1, d);
        for (auto x : Del[i])
            T.L = x.L, T.R = x.R, T.W = -1, T.change(1, 1, d);
        int y = T.query1(d);
        if (y != -1) {
            printf("YES\n%d %d\n", i, y);
            return 0;
        }
    }
    puts("NO");
    return 0;
}

I

因为有区间并的补等于区间补的交，所以直接输出每一段未被区间覆盖的区间的补即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
pair<int, int> p[N];
int main() {
    int t, n, m, l, r;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            cin >> p[i].first >> p[i].second;
        }
        cout << m << endl;
        sort(p, p + m);
        for (int i = 0; i < m; i++) {
            cout << p[i].first << " " << p[(m + i - 1) % m].second << endl;
        }
    }
    return 0;
}

J

对于一个大小为偶数的连通块是不会操作的。

对于一个大小为奇数的连通块，想贪心只删去一个点。当这个点不是割点时，显然是可行的。否则，需要考虑删去这个点后剩下的每个连通块的答案。

显然，对于一个连通块不会同时分离出割点和非割点。否则只分离非割点是更优的选择。

考虑任意一种删去割点的方案，需要满足若删去这些被选择的割点，剩下的每个连通块大小必须是偶数（不然就不止删这些点），从而得到，选择的割点个数一定是奇数（奇+偶=奇）。

并且当选择割点数大于等于 的时候，总能选择出两个割点，满足它们之间存在一条路径不经过其他割点。同时不选择它们，会发现仍然满足剩下的每个连通块大小是偶数的条件，并且答案更优了！

所以对于一个大小为奇数的连通块，若删去割点，只会删去一个。那枚举所有割点，看删掉后剩下连通块大小是否都是偶数，然后和每个非割点的答案取最优即可。时间复杂度 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 9;
int n, m, T, mn, idx;
int dfn[N], low[N], a[N], sz[N];
vector<int>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 dfs(int x, int fa) {
    sz[x] = 1;
    int flag = 1;
    dfn[x] = low[x] = ++idx;
    for (int to : e[x]) {
        if (to != fa)
            if (!dfn[to]) {
                dfs(to, x);
                low[x] = min(low[x], low[to]);
                sz[x] += sz[to];
                if (low[to] >= dfn[x] && (sz[to] & 1))
                    flag = 0;
            } else
                chmn(low[x], dfn[to]);
    }
    if (flag)
        chmn(mn, a[x]);
}
signed main() {
    T = read();
    while (T--) {
        n = read(), m = read();
        int sum = 0;
        mn = 1e18;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            sum += a[i];
            e[i].clear();
            dfn[i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int x, y;
            x = read(), y = read();
            e[x].push_back(y);
            e[y].push_back(x);
        }
        if (n % 2 == 0)
            printf("%lld\n", sum);
        else {
            idx = 0;
            dfs(1, 0);
            printf("%lld\n", sum - mn * 2);
        }
    }
}

K

首先，不考虑数据范围，有如下几个做法：

暴力树剖，维护区间左右端点选不选然后合并，时间复杂度 .

倍增，维护 往上跳 的答案。时间复杂度都是 。空间复杂度

但是考虑这题数据范围，需要一个 回答询问的算法。

对于序列上的问题，用猫树在每个区间维护所有点到中点的答案，查询时找到 的 ，即可 回答询问。

发现猫树的思想是，每次选择中点，然后递归下去，类似于 分治。那相应的，在树上就选择重心，然后递归处理子树，像点分治那样。这样询问也是 的。预处理时空复杂度都是 。

具体实现时需要 LCA 。

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
using namespace std;
const int P = 998244353;
const int N = 5e5 + 9;
int max(int x, int y) {
    return x > y ? x : y;
}
struct Rand {
    unsigned int n, seed;
    Rand(unsigned int n, unsigned int seed)
        : n(n), seed(seed) {}
    int get(long long lastans) {
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        return (seed ^ lastans) % n + 1;
    }
};
int n, a[N], sz[N];
vector<int> e[N];
bool vis[N];
void getSize(int x, int p) {
    sz[x] = 1;
    for (int y : e[x]) {
        if (y == p || vis[y])
            continue;
        getSize(y, x);
        sz[x] += sz[y];
    }
}
int getrt(int x, int p, int s) {
    for (int y : e[x]) {
        if (y == p || vis[y] || sz[y] * 2 < s)
            continue;
        return getrt(y, x, s);
    }
    return x;
}
ll f[20][N][2], dp[N][2][2];
int fa[20][N];
void dfs(int x, int p, int d, int r) {
    fa[d][x] = r;
    f[d][x][0] = max(dp[x][0][0], dp[x][0][1]);
    f[d][x][1] = max(dp[x][1][0], dp[x][1][1]);
    for (int y : e[x]) {
        if (y == p || vis[y])
            continue;
        dp[y][0][0] = max(dp[x][0][0], dp[x][0][1]);
        dp[y][0][1] = dp[x][0][0] + a[y];
        dp[y][1][0] = max(dp[x][1][0], dp[x][1][1]);
        dp[y][1][1] = dp[x][1][0] + a[y];
        dfs(y, x, d, r);
    }
}
void solve(int x, int d) {
    getSize(x, 0);
    x = getrt(x, 0, sz[x]);
    dp[x][0][0] = 0;
    dp[x][0][1] = dp[x][1][0] = -1e18;
    dp[x][1][1] = a[x];
    dfs(x, 0, d, x);
    vis[x] = true;
    for (int y : e[x]) {
        if (vis[y])
            continue;
        solve(y, d + 1);
    }
}
ll calc(int x, int y) {
    if (x == y)
        return a[x];
    for (int i = 0; i < 20; i++) {
        if (fa[i + 1][x] != fa[i + 1][y]) {
            int p = fa[i][x];
            return max(f[i][x][1] + f[i][y][1] - a[p], f[i][x][0] + f[i][y][0]);
        }
    }return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, seed;
    cin >> n >> m >> seed;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2, x; i <= n; i++) {
        cin >> x;
        e[x].push_back(i);
        e[i].push_back(x);
    }
    solve(1, 0);
    ll lastans = 0, ans = 0;
    Rand rand(n, seed);
    for (int i = 0; i < m; i++) {
        int u = rand.get(lastans);
        int v = rand.get(lastans);
        int x = rand.get(lastans);
        lastans = calc(u, v);
        ans = (ans + lastans % P * x) % P;
    }
    cout << ans << "\n";
    return 0;
}