526互联

CSP模拟38

发布时间 2023-09-15 09:33:46作者: User-Unauthorized

A. 我是 A 题

做法 \(1\)

观察到题目给出的三维坐标中一定有一维是该维最大值，故我们按最大值将点分类存储，将剩余的两维使用单调栈求平面凸包。现在问题就转化成立求若干棱柱的体积并，应用容斥定理即可。值得一提，平面内随机撒 \(n\) 个点的凸包大小是 \(\mathcal{O}(\log n)\) 级别的。所以此算法复杂度为 \(\mathcal{O}(n + \log^3 n)\)。

做法 \(2\)

给出的坐标点中会有 \(\dfrac{1}{9}\) 的概率出现前两维度取最大值的情况，我们对于所有的这部分点求出其剩余维度的最大值并删去那部分，这样剩下的棱柱的高期望为 \(9\)，直接对于每个高应用一次单调栈即可。但是由于此做法的复杂度基于 \(n, C\) 同阶，故可以很轻松的构造数据使其超时，考虑进行优化，只有存在点使得凸包形态更新时才重新计算，这样的话是可以通过的。

B. 我是 B 题

定义 \(f_{i,j}\) 为第 \(i\) 次质检后第 \(j\) 小元素的期望质量，转移时枚举本次质检删除的元素即可，复杂度 \(\mathcal{O}(n^3)\)。

C. 我是 C 题

注意到 \(b\) 数组单调递减，那么若一个区间不符合要求，任意包含使该区间不符合要求的元素（即出现次数小于 \(b_k\) 的元素）的子区间也不会符合要求。所以我们可以去遍历整个区间，找出所有不符合要求的元素并将其删除，进而去递归求解余下的各个子区间。若不存在不符合要求的元素，那么更新答案，由于子区间不可能贡献出更优的答案，故无需递归。

我们来分析这个做法的复杂度，显然只有删除数字时递归深度才会增加，由于一个区间最多有 \(\mathcal{O}(\sqrt{n})\) 中元素出现次数，所以递归深度为 \(\mathcal{O}(\sqrt{n})\)，总复杂度为 \(\mathcal{O}(n \sqrt{n})\)。

考虑优化这一算法，发现若我们找到一个不符合要求的元素便将其删除后递归左右两个子区间，那么正确性是显然的。但是由于分治后的两个区间长度可能不等，所以该算法的最劣复杂度为 \(\mathcal{O}(n^2)\)。考虑优化，发现若我们能够保证在递归查找区间 \(\left[l, r\right]\) 时花费的复杂度为分治后两个区间的较小值，那么我们就可以得到一个类似于启发式合并的复杂度，即 \(\mathcal{O}(n \log n)\)。

下面我们考虑如何实现这一复杂度，首先寻找断点直接从区间两端同时开始寻找即可，可以发现难点在于如何处理用于计数的桶。我们要求在递归查找区间 \(\left[l, r\right]\) 前桶的状态为恰好存储了这个区间内的数，并且每次递归结束后桶为空。由于只要遍历小区间的次数为常数次那么复杂度就是正确的，故我们可以在每次向下递归前先清空小区间的桶，然后递归大区间，根据我们的要求，此时桶为空，接下来将小区间的元素加入桶中后递归小区间即可。这样的话，总复杂度为 \(\mathcal{O}(n \log n)\)。

D. 我是 D 题

首先将题目要求求出的平方转化为无序数对 \((i, j)\) 且满足 \((b_i = b_{i + 1} = \cdots = b_{j})\) 的期望数量。发现无序数对难于统计，我们可以考虑统计有序数对的期望数量即每个数对符合要求的概率的和，那么对于有序数对 \((i, j)\)，有

\[P(i, j) = \begin{cases} m^{-(\operatorname{count}_{l, r})} & [l, r] \text{内均为} 0 \\ m^{-(\operatorname{count}_{l, r}) - 1} & [l, r] \text{内均为} 只含有一种颜色 \\ 0 & \text{其他} \end{cases}\]

其中 \(\operatorname{count}_{l, r}\) 表示区间 \(\left[l, r\right]\) 内 \(0\) 的个数。考虑合并两个区间的贡献，可以发现只有左区间的后缀和右区间的前缀会产生贡献，计算出这部分的 \(\sum\limits_{m^{-\operatorname{count}}}\) 后相乘即可，注意需要特殊处理左区间或右区间均为 \(0\) 的情况。

Code

A

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef __int128 resultType;
typedef unsigned long long randType;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

std::ostream &operator<<(std::ostream &os, resultType V) {
    if (V == 0) {
        os << '0';
        return os;
    }

    if (V < 0) {
        os << '-';

        V = -V;
    }

    std::string str;

    while (V > 0) {
        str.push_back((char) (V % 10 + '0'));
        V /= 10;
    }

    std::reverse(str.begin(), str.end());

    os << str;

    return os;
}

struct Node {
    valueType x, y, z;

    Node() : x(0), y(0), z(0) {}

    Node(valueType x, valueType y, valueType z) : x(x), y(y), z(z) {}
};

typedef std::vector<Node> NodeVector;

valueType cross(valueType l1, valueType r1, valueType l2, valueType r2) {
    return std::max(std::min(r1, r2) - std::max(l1, l2), 0);
}

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    randType x, y;
    valueType N, A, B, C;

    std::cin >> N >> A >> B >> C >> x >> y;

    NodeVector nodeA, nodeB, nodeC;

    nodeA.reserve(N / 3);
    nodeB.reserve(N / 3);
    nodeC.reserve(N / 3);

    for (valueType i = 0; i < N; ++i) {
        auto u = (valueType) (Rand(x, y) % A + 1);
        auto v = (valueType) (Rand(x, y) % B + 1);
        auto w = (valueType) (Rand(x, y) % C + 1);

        if (Rand(x, y) % 3 == 0) u = A;

        if (Rand(x, y) % 3 == 0) v = B;

        if ((u != A) && (v != B)) w = C;

        if (u == A) {
            nodeA.emplace_back(u, v, w);
        } else if (v == B) {
            nodeB.emplace_back(u, v, w);
        } else if (w == C) {
            nodeC.emplace_back(u, v, w);
        }
    }

    std::cerr << nodeA.size() << ' ' << nodeB.size() << ' ' << nodeC.size() << std::endl;

    { // checkA
        std::sort(nodeA.begin(), nodeA.end(), [](const Node &a, const Node &b) {
            return a.y < b.y;
        });

        NodeVector result;

        result.emplace_back(A, 0, C + 1);

        for (auto const &iter: nodeA) {
            while (!result.empty() && result.back().z < iter.z)
                result.pop_back();

            result.emplace_back(iter);
        }

        nodeA = result;
    }

    { // checkB
        std::sort(nodeB.begin(), nodeB.end(), [](const Node &a, const Node &b) {
            return a.x < b.x;
        });

        NodeVector result;

        result.emplace_back(0, B, C + 1);

        for (auto const &iter: nodeB) {
            while (!result.empty() && result.back().z < iter.z)
                result.pop_back();

            result.emplace_back(iter);
        }

        nodeB = result;
    }

    { // checkC
        std::sort(nodeC.begin(), nodeC.end(), [](const Node &a, const Node &b) {
            return a.x < b.x;
        });

        NodeVector result;

        result.emplace_back(0, B + 1, C);

        for (auto const &iter: nodeC) {
            while (!result.empty() && result.back().y < iter.y)
                result.pop_back();

            result.emplace_back(iter);
        }

        nodeC = result;
    }

    nodeA.front() = nodeB.front() = nodeC.front() = Node(0, 0, 0);

    resultType count1 = 0, count2 = 0, count3 = 0;

    for (valueType i = 1; i < nodeA.size(); ++i)
        count1 += (resultType) A * (nodeA[i].y - nodeA[i - 1].y) * nodeA[i].z;

    for (valueType i = 1; i < nodeB.size(); ++i)
        count1 += (resultType) B * (nodeB[i].x - nodeB[i - 1].x) * nodeB[i].z;

    for (valueType i = 1; i < nodeC.size(); ++i)
        count1 += (resultType) C * (nodeC[i].x - nodeC[i - 1].x) * nodeC[i].y;

    std::cerr << "count1 = " << count1 << std::endl;

    for (valueType i = 1; i < nodeA.size(); ++i) {
        for (valueType j = 1; j < nodeB.size(); ++j) {
            count2 += (resultType) (nodeA[i].y - nodeA[i - 1].y) * (nodeB[j].x - nodeB[j - 1].x) * std::min(nodeA[i].z, nodeB[j].z);
        }
    }

    for (valueType j = 1; j < nodeB.size(); ++j) {
        for (valueType k = 1; k < nodeC.size(); ++k) {
            count2 += (resultType) cross(nodeB[j - 1].x, nodeB[j].x, nodeC[k - 1]x, nodeC[k].x) * nodeC[k].y * nodeB[j].z;
        }
    }

    for (valueType i = 1; i < nodeA.size(); ++i) {
        for (valueType k = 1; k < nodeC.size(); ++k) {
            count2 += (resultType) cross(nodeA[i - 1].y, nodeA[i].y, 0, nodeC[k].y) * nodeA[i].z * (nodeC[k].x - nodeC[k - 1].x);
        }
    }

    std::cerr << "count2 = " << count2 << std::endl;

    for (valueType i = 1; i < nodeA.size(); ++i) {
        for (valueType j = 1; j < nodeB.size(); ++j) {
            for (valueType k = 1; k < nodeC.size(); ++k) {
                valueType H, W, D; //height, width, depth

                H = std::min(nodeA[i].z, nodeB[j].z);
                W = cross(nodeB[j - 1].x, nodeB[j].x, nodeC[k - 1].x, nodeC[k].x);
                D = cross(nodeA[i - 1].y, nodeA[i].y, 0, nodeC[k].y);

                count3 += (resultType) H * W * D;
            }
        }
    }

    std::cerr << "count3 = " << count3 << std::endl;

    resultType const ans = count1 - count2 + count3;

    std::cout << ans << std::endl;
}

B

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

constexpr valueType MOD = 1e9 + 7;

template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a + b;

    if (a >= mod)
        a -= mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a - b;

    if (a < 0)
        a += mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
    return a + b >= mod ? a + b - mod : a + b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
    return a - b < 0 ? a - b + mod : a - b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
    return (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
    a = (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
    T1 result = 1;

    while (b > 0) {
        if (b & 1)
            Mul(result, a, mod);

        Mul(a, a, mod);
        b = b >> 1;
    }

    return result;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    ValueVector P(N + 1);

    for (valueType i = 1; i < N; ++i)
        std::cin >> P[i];

    ValueMatrix F(N + 1, ValueVector(N + 1, 0));

    for (valueType i = 1; i <= N; ++i)
        F[0][i] = i;

    for (valueType i = 1; i < N; ++i) {
        for (valueType k = 1; k <= N - i; ++k) {
            valueType const p = mul(pow(sub(1, P[i]), k - 1), P[i]);

            for (valueType j = 1; j < k; ++j)
                Inc(F[i][j], mul(F[i - 1][j], p));

            for (valueType j = k; j <= N - i; ++j)
                Inc(F[i][j], mul(F[i - 1][j + 1], p));
        }

        {
            valueType const k = N - i + 1;

            valueType const p = pow(sub(1, P[i]), k - 1);

            for (valueType j = 1; j < k; ++j)
                Inc(F[i][j], mul(F[i - 1][j], p));
        }
    }

    std::cout << F[N - 1][1] << std::endl;

    return 0;
}

C

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;

valueType N, ans = 0;
ValueVector A, B, bucket;

void dfs(valueType l, valueType r) {
    if (l > r || r - l + 1 < ans) {
        for (valueType i = l; i <= r; ++i)
            --bucket[A[i]];

        return;
    }

    valueType const len = r - l + 1;

    if (len == 1 && B[len] <= 1) {
        --bucket[A[l]];

        ans = std::max(ans, len);

        return;
    }

    valueType pos = -1;

    for (valueType i = 0; i * 2 < len; ++i) {
        if (bucket[A[l + i]] < B[len]) {
            pos = l + i;

            break;
        }

        if (bucket[A[r - i]] < B[len]) {
            pos = r - i;

            break;
        }
    }

    if (pos == -1) {
        ans = std::max(ans, len);

        for (valueType i = l; i <= r; ++i)
            --bucket[A[i]];

        return;
    }

    valueType const mid = (l + r) >> 1;

    if (pos <= mid) {
        for (valueType i = l; i <= pos; ++i)
            --bucket[A[i]];

        dfs(pos + 1, r);

        for (valueType i = l; i <= pos - 1; ++i)
            ++bucket[A[i]];

        dfs(l, pos - 1);
    } else {
        for (valueType i = pos; i <= r; ++i)
            --bucket[A[i]];

        dfs(l, pos - 1);

        for (valueType i = pos + 1; i <= r; ++i)
            ++bucket[A[i]];

        dfs(pos + 1, r);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::cin >> N;

    A.resize(N + 1);
    B.resize(N + 1);
    bucket.resize(N + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= N; ++i)
        std::cin >> B[i];

    for (valueType i = 1; i <= N; ++i)
        ++bucket[A[i]];

    dfs(1, N);

    std::cout << ans << std::endl;

    return 0;
}

D

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

constexpr valueType MOD = 998244353;

template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a + b;

    if (a >= mod)
        a -= mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a - b;

    if (a < 0)
        a += mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
    return a + b >= mod ? a + b - mod : a + b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
    return a - b < 0 ? a - b + mod : a - b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
    return (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
    a = (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
    T1 result = 1;

    while (b > 0) {
        if (b & 1)
            Mul(result, a, mod);

        Mul(a, a, mod);
        b = b >> 1;
    }

    return result;
}

ValueVector InvSum, Power, Sum2;

class Tree {
private:
    struct Node {
        valueType leftCount, rightCount;
        valueType leftValue, rightValue;
        valueType leftAns, rightAns;
        valueType totalAns, totalCount;
        bool tag;

        Node() : leftCount(0), rightCount(0), leftValue(0), rightValue(0), leftAns(0), rightAns(0), totalAns(0),
                 totalCount(0), tag(false) {}

        explicit Node(valueType x) : leftCount(x == 0 ? 1 : 0), rightCount(x == 0 ? 1 : 0), leftValue(x), rightValue(x),
                                     leftAns(x == 0 ? 0 : 1), rightAns(x == 0 ? 0 : 1), totalAns(1),
                                     totalCount(x == 0 ? 1 : 0), tag(true) {}
    };

    typedef std::vector<Node> NodeVector;

    static Node merge(Node const &left, Node const &right) {
        Node result;

        if (left.leftValue == 0) {
            result.leftCount = left.totalCount + right.leftCount;
            result.leftValue = right.leftValue;

            result.leftAns = 0;
        } else {
            result.leftCount = left.leftCount;
            result.leftValue = left.leftValue;

            result.leftAns = left.leftAns;
        }

        if (right.rightValue == 0) {
            result.rightCount = left.rightCount + right.totalCount;
            result.rightValue = left.rightValue;

            result.rightAns = 0;
        } else {
            result.rightCount = right.rightCount;
            result.rightValue = right.rightValue;

            result.rightAns = right.rightAns;
        }

        result.tag = left.tag && right.tag && (left.rightValue == 0 || right.leftValue == 0 || left.rightValue == right.leftValue);

        result.totalCount = left.totalCount + right.totalCount;

        result.totalAns = sum(left.totalAns, right.totalAns);

        if (left.tag) {
            if (left.leftValue != 0) {
                Inc(result.leftAns, sub(InvSum[left.totalCount + right.leftCount], InvSum[left.totalCount]));
            }
            if (left.leftValue == 0 || right.leftValue == 0 || left.rightValue == right.leftValue) {
                Inc(result.leftAns, mul(Power[left.totalCount], right.leftAns));
            }
        }

        if (right.tag) {
            if (right.rightValue != 0) {
                Inc(result.rightAns, sub(InvSum[right.totalCount + left.rightCount], InvSum[right.totalCount]));
            }
            if (left.leftValue == 0 || right.leftValue == 0 || left.rightValue == right.leftValue) {
                Inc(result.rightAns, mul(Power[right.totalCount], left.rightAns));
            }
        }

        valueType const x = InvSum[left.rightCount], y = InvSum[right.leftCount];

        Inc(result.totalAns, mul(Sum2[left.rightCount], y));

        if (left.rightValue == 0 || right.leftValue == 0 || left.rightValue == right.leftValue) {
            Inc(result.totalAns, mul(sum(left.rightAns, x), sum(right.leftAns, y)));
            Dec(result.totalAns, mul(x, y));
        } else {
            Inc(result.totalAns, mul(x, right.leftAns));
            Inc(result.totalAns, mul(left.rightAns, y));
        }

        return result;
    }

    valueType N;

    NodeVector data;

public:
    Tree(valueType n, ValueVector const &source) : N(n), data((n << 2) + 10) {
        build(1, 1, N, source);
    }

    void update(valueType pos, valueType key) {
        update(1, 1, N, pos, key);
    }

    valueType query(valueType l, valueType r) {
        return sub(mul(query(1, 1, N, l, r).totalAns, 2), r - l + 1);
    }

private:
    void build(valueType id, valueType l, valueType r, ValueVector const &source) {
        if (l == r) {
            data[id] = Node(source[l]);

            return;
        }

        valueType const mid = (l + r) >> 1;

        build(id << 1, l, mid, source);
        build(id << 1 | 1, mid + 1, r, source);

        data[id] = merge(data[id << 1], data[id << 1 | 1]);
    }

    void update(valueType id, valueType nodeL, valueType nodeR, valueType pos, valueType key) {
        if (nodeL == nodeR) {
            data[id] = Node(key);

            return;
        }

        valueType const mid = (nodeL + nodeR) >> 1;

        if (pos <= mid)
            update(id << 1, nodeL, mid, pos, key);
        else
            update(id << 1 | 1, mid + 1, nodeR, pos, key);

        data[id] = merge(data[id << 1], data[id << 1 | 1]);
    }

    Node query(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR) {
        if (queryL <= nodeL && nodeR <= queryR)
            return data[id];

        valueType const mid = (nodeL + nodeR) >> 1;

        if (queryR <= mid)
            return query(id << 1, nodeL, mid, queryL, queryR);
        else if (queryL > mid)
            return query(id << 1 | 1, mid + 1, nodeR, queryL, queryR);
        else
            return merge(query(id << 1, nodeL, mid, queryL, queryR),
                         query(id << 1 | 1, mid + 1, nodeR, queryL, queryR));
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M, Q;

    std::cin >> N >> M >> Q;

    InvSum.resize(N + 1);

    valueType const InvM = pow(M, MOD - 2);

    InvSum[0] = 1;
    for (valueType i = 1; i <= N; ++i) {
        InvSum[i] = mul(InvSum[i - 1], InvM);
    }

    Power = InvSum;

    InvSum[0] = 0;
    for (valueType i = 2; i <= N; ++i) {
        Inc(InvSum[i], InvSum[i - 1]);
    }

    Sum2 = InvSum;

    for (valueType i = 1; i <= N; ++i) {
        Mul(Sum2[i], M);
    }

    ValueVector B(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> B[i];

    Tree tree(N, B);

    for (valueType i = 0; i < Q; ++i) {
        valueType opt, x, y;
        std::cin >> opt >> x >> y;

        if (opt == 1) {
            tree.update(x, y);
        } else {
            std::cout << tree.query(x, y) << '\n';
        }
    }

    std::cout << std::flush;

    return 0;
}