Codeforces Round#716 div.2 回顾

补题地址：https://codeforces.com/contest/1514

记录

就是我上一篇博文中提到的那个因为记错时间而忘记打的 Div2；顺便一提，这一场的下一场也是非经典时间 21:35 开始，希望可以正常打起来吧……？

曾经也在本博客的博文里登场的学弟打了 ABD 三个题，C 题奇妙的被 hack 了（）着实有点恐怖；本以为我至少也能打个 ABCD 的，没想到 CD 全都挂了，，属实不行==

题解

C - Product 1 Modulo N

给 $n \leq 10^5$ ；现在要求求出 $1, \dots, n-1$ 的最长子序列 $a$ ，满足 $\prod a_i \mod n \equiv 1$ ；输出子序列 $a$ 的长度以及它包含的元素；

一种很显然的想法是现将它们都乘起来，然后取余数，再将余数的数字从列表中删除（当然，如果为 1 就算了）从而得到了答案序列；如果再打表的话还会意识到如果 $n$ 是素数，那么答案是 $1, \dots, n-2$ ；但是再稍微打表就会意识到，如果 $n$ 不是素数，那么你删除模数之后的乘积未必是 1，于是这种做法显而易见的错误了——毕竟就连样例都过不了（

稍事思考：对于任何数 $n$ 都显然有 $\gcd(1, n) = 1$ ；由辗转相除法的转移式子 gcd(a, b) = gcd(b, a % b) 可知 $\gcd(\prod a_i \mod n, n) = \gcd(\prod a_i, n)$ ；联立一下就是我们选择的序列的乘积和 $n$ 互素：如果这样，那么选择的序列中的每一个 $a_i$ 都应该和 $n$ 互素（这是必要条件）；在这样的基础上，我们先以此作为标准，过滤掉所有和 $n$ 不互质的数字。

同理，我们可以通过将剩下的数字全部乘起来取模，得到这个很大的数字和 $n$ 的最大公因数；因为现在所有的数字都和 $n$ 互素，所以这个因子一定出现在了我们选择的数字中；此时我们只要把它移除就可以了；~~当然，如果你打表，你也能发现在删除了所有的不互质的数字之外还需要删除一个数字（~~

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n = $.nextInt();
    set<int> ans;
    longs tmp = 1;
    for (int i = 1; i < n; ++ i)
        if (gcd(i, n) == 1) {
            ans.insert(i);
            tmp = tmp * i % n;
        }
    if (tmp != 1) ans.erase((int)tmp);
    $.put(ans.size()).putArray(ans.begin(), ans.end());

    return 0;
}

看代码也能看出来这个过程实际上非常的自然；但是说又说不清楚…… 只能说需要补习数论了==

D - Cut and Stick

定义“好序列”是其中没有元素出现的次数超过 $\lceil \frac{n}2 \rceil$ ，其中 $n$ 是序列的长度；对于一个序列，如果它不是好序列，但你可以将它划分为 $m$ 个子序列，它们都是好序列，那么这个序列的权值是 $m$ ；显然，对于一个好序列自身而言，它的权值是 $1$ 。
现提供长度为 $n \leq 3 \cdot 10^5$ 的序列；进行 $q \leq 3 \cdot 10^5$ 次询问：每次询问 $[l, r]$ 区间的字串序列的权值。

可以说是一个很乱搞的题目了；如果有差不多的算法素养或者代码能力的话应该就能写出来的~~只可惜我没有，残疾人竟是我自己~~。下面介绍一下这个题目的三种思路：

首先，如果暴力移动区间，显然每次扩张和收缩都可以 $O(1)$ 完成：需要维护的是区间内每个数字出现的次数，以及这个次数出现的次数；因为每次移动只会使得某数字出现的次数变化 1，所以转移一定可以直接完成。

那么，对于这种询问次数很大，又可以这样暴力维护的问题，而且还没有在线的要求；我们就可以考虑使用莫队算法离线维护；时间复杂度是 $\mathcal{O}(n \sqrt n)$ 的：

const int N = 3e5 + 5;
int a[N];

namespace MO {
    int block_size = 1;

    struct query {
        int l, r, id;

        query() = default;
        query(int l, int r, int id) : l(l), r(r), id(id) {}

        bool operator <(const query &rhs) const {
            if (l / block_size == 
                rhs.l / block_size)
                return r < rhs.r;
            else return l < rhs.l;
        }
    };

    vector<query> req;
    vector<int> ans;
    int cnt[N], tim[N];

    void step(int pos, int sig, int &now) {
        auto &times = tim[a[pos]];
        if (times >= 0) -- cnt[times];
        times += sig;
        if (times >= 0) ++ cnt[times];
        if (sig > 0) maximize(now, times);
        else while (!cnt[now]) -- now;
    }

    void solve(int n) {
        int l = 0, r = 0, tmp = 0;
        const auto increase = [&](int pos) { step(pos, +1, tmp); };
        const auto decrease = [&](int pos) { step(pos, -1, tmp); };
        for (auto [ql, qr, qid] : req) {
            while (ql < l) increase(-- l);
            while (qr > r) increase(++ r);
            while (ql > l) decrease(l ++);
            while (qr < r) decrease(r --);
            const auto len = qr - ql + 1;
            ans[qid] = max(1, 2 * tmp - len);
        }
    }

    void run(int n, int m) {
        ans.resize(m + 1);
        block_size = (int) n / sqrt(m * 2 / 3);
        stable_sort(req.begin(), req.end());
        solve(n);
    }
}

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

    int n = scanner.nextInt(),
        m = scanner.nextInt();
    for (int i = 1; i <= n; ++ i)
        a[i] = scanner.nextInt();
    for (int i = 1; i <= m; ++ i) {
        int l = scanner.nextInt(),
            r = scanner.nextInt();
        MO::req.emplace_back(l, r, i);
    }
    MO::run(n, m);
    for (int i = 1; i <= m; ++ i)
        println(MO::ans[i]);
    return 0;
}

特别说明：分块的方法没有采用经典的 $\lceil \sqrt{n} \rceil$ ，写法采用的分块方法在本题的表现更好~~其实是抄学弟的~~；

虽然这样修改分块方法已经使得我的莫队运行时间从 2200ms 变成了 1800ms，但是学弟原本的代码跑到了令人发指的 900ms…… MSYS2 这么拉的嘛（）

虽然如果要求众数，只能使用莫队这种优雅的暴力来维护；但是我们还是应该敏感地注意到众数和“过半数”的微妙的区别；虽然前者没办法用树形数据结构维护，但是后者是可以的——考虑将两个区间的结果合并成的大区间的结果：显然大区间的“过半数”必为两个子区间的“过半数”中的一个，因此可以使用线段树维护。

那么我们应该如何合并结果呢？查找一个数字在区间 $[l, r]$ 中出现的次数，我们可以将这些位置存进数组里，然后使用二分查找确定上下界，那么两界之差就是我们要求的结果；这个询问的时间复杂度是 $\mathcal{O}(\log n)$ 的。

确定了合并策略，我们就可以写出下面的代码~~什么嘛，合并策略这个抽象不是挺好用的嘛~~：

template <class T>
class seg_tree {

    using merge_method = function<T(T, T, int, int)>;

    int siz;
    vector<T> t;
    merge_method merge;

    void build(int id, int l, int r, const T *arr) {
        if (l + 1 == r) { t[id] = arr[l]; return; }
        int m = (l + r) / 2;
        build(id * 2 + 1, l, m, arr);
        build(id * 2 + 2, m, r, arr);
        t[id] = merge(t[id * 2 + 1], t[id * 2 + 2], l, r);
    }

    T query(int id, int l, int r, int ll, int rr) {
        if (ll >= rr) return (T)-1;
        else if (ll == l && rr == r) return t[id];
        int m = (l + r) / 2;
        auto lv = query(id * 2 + 1, l, m, ll, min(rr, m));
        auto rv = query(id * 2 + 2, m, r, max(m, ll), rr);
        return merge(lv, rv, ll, rr);
    }

public:
    explicit seg_tree(int n, merge_method m) 
    : siz(n), merge(move(m)) { t.resize(4 * n); }

    void build(const T *arr) { return build(0, 0, siz + 1, arr); }

    T query(int ll, int rr) { return query(0, 0, siz + 1, ll, rr); }
};

const int N = 3e5 + 5;
int a[N];
vector<int> pos[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n, q, l, r;
    const auto count = [&](int l, int r, int i) -> int {
        if (i <= 0) return -1;
        auto ll = lower_bound(pos[i].begin(), pos[i].end(), l);
        auto rr = lower_bound(pos[i].begin(), pos[i].end(), r);
        return rr - ll;
    };
    $(n, q).nextArray(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++ i)
        pos[a[i]].push_back(i);
    seg_tree<int> t(n + 1, [&](int a, int b, int l, int r) -> int {
        const auto aa = count(l, r, a), bb = count(l, r, b);
        return aa > bb ? a : b;
    });
    t.build(a);
    while (q --) {
        $(l, r);
        auto id = t.query(l, r + 1);
        auto ans = count(l, r + 1, id);
        ans = ans * 2 - (r + 1 - l);
        $.put(max(ans, 1));
    }

    return 0;
}

线段树总体的复杂度大概是 $\mathcal{O}(n\log n \cdot X)$ 的，其中 $X$ 是合并策略的单次操作的复杂度；那么这个问题的整体复杂度是 $\mathcal{O}(n \log^2n)$ 的，倒也可以接受。

还有一种比较野的思路，就是随机化：对于每次询问，我们在区间 $[l, r]$ 中随机选择一个位置，并假定它的值的出现次数最多，并更新答案，重复多次；如果重复选择的次数足够多，就可以将出错的概率降到很低：

const int N = 3e5 + 5, T = 40;
int a[N];
vector<int> pos[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n, q, l, r, ans, t;
    const auto count = [&](int l, int r, int i) -> int {
        if (i <= 0) return -1;
        auto ll = lower_bound(pos[i].begin(), pos[i].end(), l);
        auto rr = upper_bound(pos[i].begin(), pos[i].end(), r);
        return rr - ll;
    };
    $(n, q).nextArray(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++ i)
        pos[a[i]].push_back(i);
    mt19937 rng(
        chrono::steady_clock::now()
        .time_since_epoch().count()
    );
    while (q --) {
        $(l, r), ans = 1, t = T;
        while (t --) {
            int gen = a[uniform_int_distribution<int>(l, r)(rng)];
            maximize(ans, 2 * count(l, r, gen) - (r - l + 1));
        }
        $.println(ans);
    }

    return 0;
}

什么是真正的乱搞啊（战术后仰）因为我们求的权值是可以像最大值那样合并的，所以这样做非常合理；算法整体的时间复杂度是 $\mathcal{O}(qT\log n)$ 的，其中 $T$ 是重复随机的次数。

据出题人说，这个题还可以使用某种方法做到 $\mathcal{O}(n\log n)$ ，这我就真不会了（）如果会的话欢迎教我==

E - Baby Ehab’s Hyper Apartment

有 $n \leq 100$ 个节点，每对节点之间都有一条有向边；现在你可以进行以下两种询问：
询问 $u \to v$ 的方向，正向返回 1，否则 0；不超过 $9n$ 次
询问 $u \to \{a_1, \dots, a_n\}$ 中是否存在到其中任一通路，全部不可达返回 0，否则 1；不超过 $2n$ 次
要求你在规定的询问次数内求出 $n \times n$ 矩阵 $M$ ， $M_{i, j}$ 代表 $i \to j$ 是否可达。

完全没有思路，，看了题解才发现需要的知识基本也都还给离散老师了，直接埋了吧（无慈悲

首先，我们考虑只使用其中的一部分边来完成所有的转移——其他的边都是多余的；然后，发现这张图是一个竞赛图：因此它必定存在一条按照某种顺序可以到达所有的点仅一次的哈密顿通路；在这条哈密顿通路上，处于偏序位置较低的点可以到达任何偏序位置较高的点。

那么，在这样的基础上，我们只需要考虑从偏序位置较高的点到达较低的点即可；假设从某个高位置 $i$ 可以到达的最低的位置是 $p$ ，那么所有在 $p$ 点上，在 $i$ 点下的位置都可以从 $i$ 出发到达，而在 $p$ 点下的位置不可到达；因此，只需要找到所有位置可以到达的最低的位置，就可以知道 $i$ 点到达其他任何节点的可达情况。

那么我们应该怎么样实现呢？在竞赛图中，我们将每一条有向边都看作是一对偏序关系，然后使用归并排序，就可以得到一条哈密顿路（所代表的偏序顺序）；这也很好理解：假设我们将所有的节点分成两个部分，它们内部都已经找到了哈密顿路的偏序；那么我们就比较两个部分的最低点——它们之间一定存在偏序关系——找到其中较低的插入待求的偏序中；因为它比接下来的两个部分的最低点都要低，所以可以继续将更低的点插入其中。

在 C++ STL 中，已经有了默认的归并排序的实现 stable_sort，直接调用，并将第一种询问作为排序方式即可完成哈密顿路的求解。显然，这样最多会询问 $n\log_2n$ 次，对于 $n \leq 100$ 显然满足小于 $9n$ 。

然后，我们维护一个指针 $p$ ，指向当前可以到达的最低位置；我们只需要使用第二种询问询问在 $p$ 之前的前缀是否可以包含可以到达的位置，就可以判断是否继续将 $p$ 左移。这样，对于每个前缀位置 $p$ ，都会存在一次询问的返回为 1 从而使得 $p$ 左移；对于每个位置 $i$ ，都有一次询问返回 0 说明当前的 $p$ 为它可以到达的最低距离，所以询问次数也是满足 $2n$ 的限制的。

bool askTheEdge(int a, int b) {
    int res = $.put(1, a, b).flush().nextInt();
    if (res == -1) exit(EXIT_SUCCESS);
    else return (bool) res;
}

bool askEdges(int a, const vector<int> &b) {
    int res = $.print(2, ' ', a, ' ', b.size(), ' ').
                putArray(b.begin(), b.end()).flush().
                nextInt();
    if (res == -1) exit(EXIT_SUCCESS);
    else return (bool) res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt(), n;
    bitset<128> g[128];
    while (T --) {
        int n = $.nextInt();
        for (int i = 0; i < n; ++ i)
            g[i].reset(), g[i] = ~g[i];
        vector<int> path(n), tmp;
        iota(path.begin(), path.end(), 0);
        stable_sort(path.begin(), path.end(), askTheEdge);
        int p = n - 2;
        const auto makeTmp = [&](int p) -> vector<int>& {
            tmp.assign(path.begin(), path.begin() + p + 1);
            return tmp;
        };
        for (int i = n - 1; i >= 0; -- i) {
            if (p == i) {
                for (int j = 0; j <= i; ++ j)
                    for (int k = i + 1; k < n; ++ k)
                        g[path[k]][path[j]] = false;
                -- p;
            }
            while (askEdges(path[i], makeTmp(p))) -- p;
        }
        $.put(3).putArray(0, n, [&](int i, cquery $) {
            $.putArray(0, n, [&i](int j, cquery $) {
                $.print(g[i].test(j) ? 1 : 0);
            }, "");
        }, "").flush();
        int res = $.nextInt();
        if (-1 == res) exit(EXIT_SUCCESS);
    }

    return 0;
}

实际上，第二种询问还可以使用缓存减少一定的询问次数，不过优势不明显，也实在没有必要就是了（

后记

做 C 题的时候，博主也和恰好在旁边的同学 tmc 讨论了为什么会想不出来——得到的回复是只是单纯的对于数论不够敏感，换句话说就是做的少了（）真的得多加注意了==

年轻人的第一个莫队题目竟然是在这样的场合…… 只能说对比就是生产力啊（

Codeforces Round#716 div.2 回顾

记录

题解

A - Perfectly Imperfect Array

B - AND 0, Sum Big

C - Product 1 Modulo N

D - Cut and Stick

E - Baby Ehab’s Hyper Apartment

后记