提高组第六场 题解

A

观察数据生成器可以发现对于每次操作均有 。

考虑将这些三元组想象成空间直角坐标系中以 和 为对顶点的长方体。

将操作分成两部分，一部分是对 轴同时操作的，可以一开始就用前缀 统计完，将长方体变成一个底面为阶梯状的直棱柱。另一部分是对 或 操作的，考虑从小到大枚举 ，然后将 的操作变成一条横线或一条竖线，容易发现这两条线也是具有单调性的，于是每层留下的点数可以直接计算。

最后用总点数减去剩下的点数即为删除的三元组数量，由于答案最大可能到 ，所以需要使用高精或 __int128。总时间复杂度为 。

#include <bits/stdc++.h>
using namespace std;

const int N = 3e7 + 10;
typedef unsigned long long ull;

int n, A, B, C, u[N], v[N], w[N];

ull Rand (ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void GetData () {
    ull x, y;
    cin >> n >> A >> B >> C >> x >> y;
    for (int i = 1; i <= n; i++) {
        u[i] = Rand(x, y) % A + 1;
        v[i] = Rand(x, y) % B + 1;
        w[i] = Rand(x, y) % C + 1;
        if (Rand(x, y) % 3 == 0) u[i] = A;
        if (Rand(x, y) % 3 == 0) v[i] = B;
        if ((u[i] != A) && (v[i] != B)) w[i] = C;
    }
}

void Write (__int128 x) {
    if (x < 10) cout << (int)x;
    else Write(x / 10), cout << (int)(x % 10);
}

int h[N], l[N], Mx[N], My[N];

int main () {

    GetData();

    for (int i = 1; i <= n; i++) {
        if (w[i] == C) h[u[i]] = max(h[u[i]], v[i]);
        else if (u[i] == A) My[w[i]] = max(My[w[i]], v[i]);
        else if (v[i] == B) Mx[w[i]] = max(Mx[w[i]], u[i]);
    }

    for (int i = A; i >= 1; i--) h[i] = max(h[i], h[i + 1]);
    for (int i = C; i >= 1; i--) Mx[i] = max(Mx[i], Mx[i + 1]);
    for (int i = C; i >= 1; i--) My[i] = max(My[i], My[i + 1]);

    for (int i = 1, now = A; i <= B; i++) {
        while (now && h[now] < i) now--;
        l[i] = now;
    }

    __int128 ans = 0, sum = 0, All;
    for (int i = 1, Lx = A, Ly = B; i <= C; i++) {
        while (Lx > Mx[i]) sum += B - Ly - max(0, h[Lx] - Ly), Lx--;
        while (Ly > My[i]) sum += A - Lx - max(0, l[Ly] - Lx), Ly--;
        ans += sum;
    }
    All = A, All *= B, All *= C;
    Write(All - ans);

    return 0;
}

B

不难发现，如果我们知道最后剩下的物品 ，那质量优于 和劣于 的物品产生的贡献都仅与当前剩余物品的数量有关。

于是考虑枚举 ，记 表示前 道工序剩下 个物品优于 ， 个物品劣于 的概率，可以转移到 ，转移系数仅与数量有关， 即为剩下物品为 的概率。

容易发现再确定 时 的值是确定的，故状态仅需记为 。

时间复杂度 。

#include <bits/stdc++.h>
using namespace std;

const int N = 305, mod = 1e9 + 7;
int n, p[N], f[N][N], pr1[N][N], pr2[N][N], ans;

int main () {

    cin >> n;
    for (int i = 1; i < n; i++) cin >> p[i];

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

    for (int i = 1; i <= n; i++) {
        memset (f, 0, sizeof f), f[1][i] = 1;
        for (int j = 1; j < n; j++)
            for (int k = 1; k <= i; k++) if (f[j][k]) {
                f[j + 1][k - 1] = (f[j + 1][k - 1] + 1ll * f[j][k] * pr2[j][k - 1] % mod) % mod;
                f[j + 1][k] = (f[j + 1][k] + 1ll * f[j][k] * (mod + 1 - pr2[j][k]) % mod) % mod;
            }
        ans = (ans + 1ll * i * f[n][1]) % mod;
    }
    cout << ans << endl;

    return 0;
}

C

观察到 是具有单调性的，如果一个数字 导致一个区间不可行，那么这个区间所有包含 的子区间必然也不可行。

考虑分治， 表示当前分治到 ，那么我们把 中所有出现次数小于 的数字全部删掉，区间就变成了若干段，分别递归处理即可。如果当前区间没有删掉任何数字，那么说明当前区间就是合法的，直接更新答案。

考虑这个做法的复杂度，即考虑递归层数。不难发现当删除数字的时候递归层数才会增加，而最多有 种不同的出现次数，因此这个做法的复杂度为 。

考虑优化上面的做法。首先一次找出所有出现次数较小的数字比较耗时，我们可以找到任意一个出现次数不满足要求的数字，并且从这个数字处把区间分成两半进行递归，并不会影响正确性，还大大降低了编程复杂度。

但是由于分治两边可能不均等，会导致时间复杂度退化成 ，但如果我们在 的时间内完成当前层的操作，复杂度就是启发式合并的复杂度，即 。

于是利用类似于 meet in the middle 的思想，我们从区间两端同时找出现次数不满足要求的数字，显然寻找的时间就是 了。但是我们还需要维护每个数字的出现次数，考虑记 数组为每个数字的出现次数，并且假定每次递归时 数组恰好是当前区间中所有数字的出现次数，并且返回时清空 数组。

把拆开的两区间中较大的称为大区间，较小的称为小区间，每次找到分割点后，先把小区间中所有数字从 当中去掉，就可以直接递归大区间了。之后 数组被清空，我们只需要再遍历一遍小区间，把所有数字加到 中，递归完毕后 也恰好被清空，符合返回要求。

特殊的，如果一个区间找不到分割点，则需要遍历整个区间清空 ，复杂度显然没有问题。初始时， 必须设置为每个数字的出现次数再进行递归。

由于每一步花费的复杂度都是 ，因此总复杂度为 。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n, cnt[N], b[N], a[N], ans;

void calc (int l, int r) {
    if (r < l || r - l + 1 <= ans) {
        for (int i = l; i <= r; i++) --cnt[a[i]];
        return;
    }
    if (l == r) {
        --cnt[a[l]];
        if (b[1] == 1) ans = max(ans, 1);
        return;
    }
    int *p = a + l, *q = a + r, t = -1, val = b[r - l + 1];
    while (p <= q) {
        if (cnt[*p] < val) { t = p - a; break; }
        if (cnt[*q] < val) { t = q - a; break; }
        ++p, --q;
    }
    if (t < 0) {
        ans = max(ans, r - l + 1);
        for (int i = l; i <= r; i++) --cnt[a[i]];
        return;
    }
    if (t <= (l + r) >> 1) {
        for (int i = l; i <= t; i++) --cnt[a[i]];
        calc(t + 1, r);
        for (int i = l; i < t; i++) ++cnt[a[i]];
        calc(l, t - 1);
    } else {
        for (int i = t; i <= r; i++) --cnt[a[i]];
        calc(l, t - 1);
        for (int i = t + 1; i <= r; i++) ++cnt[a[i]];
        calc(t + 1, r);
    }
}

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) ++cnt[a[i]];

    calc(1, n), printf("%d\n", ans);

    return 0;
}

D

首先进行一步转化，极长连续段的平方等于满足 的数对 的数量。期望即为所有 ，满足 的概率和。

• 当 中有两个不同的颜色时，。

• 当 中有且仅有一种确定的颜色时，。

• 当 中没有确定的颜色时，。

于是只需要求 。我们发现这个信息时容易合并的，只需要维护：该区间内概率的和，左边第一个确定的颜色，右边第一个确定的颜***间长度，区间中未确定的数的数量， 中有且仅有一种确定的颜色时/没有确定的颜色时 的和。

时间复杂度 ，常数很大，实现细节见代码。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10, mod = 998244353;

int Pow (int a, int k) {
    int res = 1;
    for (; k; k >>= 1, a = 1ll * a * a % mod)
        if (k & 1) res = 1ll * res * a % mod;
    return res;
}

int n, c, q, a[N], T[3][N], f[N], inv;

struct Seg {
    int l, r, lc, rc, lans, rans, tans, all, tag;
} seg[N << 3], ans;

bool flag;

Seg Merge (Seg a, Seg b) {
    Seg res;
    res.l = (!a.lc) ? a.l + b.l : a.l;
    res.r = (!b.rc) ? a.r + b.r : b.r;
    res.lc = (!a.lc) ? b.lc : a.lc;
    res.rc = (!b.rc) ? a.rc : b.rc;
    (a.lc) ? res.lans = a.lans : res.lans = 0;
    if (a.tag) {
        if (a.lc) res.lans = (res.lans + (T[1][a.all + b.l] - T[1][a.all] + mod) % mod) % mod;
        if (a.lc && b.lc && a.lc != b.lc); 
        else res.lans = (res.lans + 1ll * T[0][a.all] * b.lans % mod) % mod;
    }
    (b.rc) ? res.rans = b.rans : res.rans = 0;
    if (b.tag) {
        if (b.rc) res.rans = (res.rans + (T[1][b.all + a.r] - T[1][b.all] + mod) % mod) % mod;
        if (a.rc && b.rc && a.rc != b.rc); 
        else res.rans = (res.rans + 1ll * T[0][b.all] * a.rans % mod) % mod;
    }
    res.tans = (a.tans + b.tans) % mod;
    int x = T[1][a.r], y = T[1][b.l];
    res.tans = (res.tans + 1ll * T[2][a.r] * y % mod) % mod;
    if (!a.rc || !b.lc || a.rc == b.lc)
        res.tans = (res.tans + (1ll * ((a.rans + x) % mod) * ((b.lans + y) % mod) % mod - 1ll * x * y % mod + mod) % mod) % mod;
    else res.tans = (res.tans + 1ll * x * b.lans % mod) % mod, res.tans = (res.tans + 1ll * y * a.rans % mod) % mod;
    res.tag = a.tag & b.tag & (!a.lc || !b.lc || a.lc == b.lc);
    res.all = a.all + b.all;
    return res;
}

void Build (int p, int l, int r) {
    if (l == r) {
        if (a[l]) seg[p] = (Seg){0, 0, a[l], a[l], 1, 1, 1, 0, 1};
        else seg[p] = (Seg){1, 1, 0, 0, 0, 0, 1, 1, 1};
        return;
    }
    Build (p << 1, l, (l + r) >> 1);
    Build (p << 1 | 1, ((l + r) >> 1) + 1, r);
    seg[p] = Merge(seg[p << 1], seg[p << 1 | 1]);
}

void Update (int p, int l, int r, int k) {
    if (l == r) {
        if (a[l]) seg[p] = (Seg){0, 0, a[l], a[l], 1, 1, 1, 0, 1};
        else seg[p] = (Seg){1, 1, 0, 0, 0, 0, 1, 1, 1};
        return;
    }
    if((l + r) >> 1 >= k) Update(p << 1, l, (l + r) >> 1, k);
    else Update(p << 1 | 1, ((l + r) >> 1) + 1, r, k);
    seg[p] = Merge(seg[p << 1], seg[p << 1 | 1]);
}

void Query (int p, int l, int r, int kl, int kr) {
    if (kl > r || kr < l) return;
    if (kl <= l && kr >= r) {
        if (!flag) flag = 1, ans = seg[p];
        else ans = Merge(ans, seg[p]);
        return;
    }
    Query (p << 1, l, (l + r) >> 1, kl, kr);
    Query (p << 1 | 1, ((l + r) >> 1) + 1, r, kl, kr);
}

int main() {

    scanf("%d%d%d", &n, &c, &q);
    inv = Pow(c, mod - 2);

    for (int i = 0; i < 2; i++) {
        T[i][0] = 1;
        int x = i ? Pow(c, mod - 2) : c;
        for (int j = 1; j <= n; j++) T[i][j] = 1ll * T[i][j - 1] * x % mod;
        T[i][0] = 0;
        for (int j = 2; j <= n; j++) T[i][j] = (T[i][j - 1] + T[i][j]) % mod;
    }
    T[0][0] = 1;
    for (int j = 1; j <= n; j++) T[0][j] = 1ll * T[0][j - 1] * inv % mod;
    for (int j = 0; j <= n; j++) T[2][j] = 1ll * T[1][j] * c % mod;

    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Build(1, 1, n);
    for (int i = 1, op, tx, ty; i <= q; i++) {
        scanf("%d%d%d", &op, &tx, &ty);
        if (op == 1) a[tx] = ty, Update(1, 1, n, tx);
        else flag = 0, Query(1, 1, n, tx, ty), printf("%d\n", (1ll * ans.tans * 2 % mod - (ty - tx + 1) + mod) % mod);
    }

    return 0;
}