算法竞赛比赛记录: The 3rd Universal Cup. Stage 39: Tokyo

A. Array Similarity

我们先来考察 $a_i$ 什么时候可以成为区间 $[l,r]$ 的某个前缀最大值。我们用单调栈预处理出 $L_i$ 满足 $a_{L_i-1}\gt a_i\land a_{L_i}\le a_i$ （即 $a_i$ 向前可以是多少个数的最大值），那么就只要 $L_i\le l\land i\le r$ ， $a_i$ 就可以成为 $[l,r]$ 的前缀最大值。

我们要判断两个区间是否 similar，也就是说对于 $[l,r]$ ，我们需要把所有符合条件的 $a_i$ 都拿出来，并且需要计算 $i_1-l,i_2-l\dots$ （即相对于 $l$ 的相对位置）是否相同。

比较是否相同这一点可以用哈希，道理和字符串哈希是一样的，只不过我们这里只关注“哈希可以表示相对位置”这个特点。

那么怎么提取所有符合条件的 $a_i$ 呢？我们注意到 $a_i$ 满足的条件是一个二维偏序，

L_i\le l\\ i\le r

解决二维偏序的经典方法是对一个维度进行排序，然后用数据结构维护另一个维度。这里，我们对 $L_i,l$ 维度进行排序，用双指针将满足 $L_i\le l$ 的 $a_i$ 插入数据结构，然后在数据结构里查询 $[l,r]$ 的区间信息。结合上文所说的利用哈希确定 $\set{i}$ 的集合，我们可以往数据结构里插入哈希值。取出 $[l,r]$ 的哈希值之和后，再除以 base[l-1] 即可。

时间复杂度：排序是 $O(n\log n +q\log q)$ 的。我写的求哈希有点小问题，导致这一块的时间复杂度变成了 $O(n\log V)$ ，但可以做到 $O(n+\log V)$ 。总时间复杂度的瓶颈在排序上，因此为 $O(n\log n+q\log q)$ .

Code

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
using pii         = std::pair<int, int>;
using u64         = long long;
constexpr int N   = 2e5 + 10;
constexpr u64 MOD = 998244353;
constexpr u64 B   = 100003;
constexpr u64 P   = 1373;

struct Range {
    int l, r, qid;
    bool left;
};
struct Query {
    Range x, y;
    u64 Lval, Rval;
} query[N];

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int n, q;
int a[N], L[N];
u64 hash[N], base[N];
std::vector<Range> range;
std::vector<pii> rk;

u64 fw[N], count[N];

void update(u64 *x, int i, u64 val) {
    for (; i <= n; i += i & -i) x[i] += val, x[i] %= MOD;
}
u64 get(u64 *x, int p) {
    u64 res = 0;
    for (; p > 0; p -= p & -p) res += x[p], res %= MOD;
    return res;
}
u64 get(u64 *x, int l, int r) { return ((get(x, r) - get(x, l - 1)) % MOD + MOD) % MOD; }

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::cin >> n >> q;
    base[0] = 1;
    hash[0] = 1;
    for (int i = 1; i <= n; i++) std::cin >> a[i], hash[i] = hash[i - 1] * B % MOD, base[i] = base[i - 1] * B % MOD;
    [&] {
        auto fpow = [&](u64 b, u64 p) {
            u64 res = 1;
            while (p) {
                if (p & 1) res = res * b % MOD;
                b = b * b % MOD;
                p >>= 1;
            }
            return res;
        };
        for (int i = 1; i <= n; i++) { base[i] = fpow(base[i], MOD - 2) % MOD; }
    }();

    [&] { // monotonous stack
        using pii = std::pair<int, int>;
        std::vector<pii> stk;
        stk.push_back({1e9 + 10, 0});
        for (int i = 1; i <= n; i++) {
            while (!stk.empty() && stk.back().first <= a[i]) stk.pop_back();
            L[i] = stk.back().second + 1;
            stk.push_back({a[i], i});
        }
    }();

    for (int i = 1; i <= q; i++) {
        std::cin >> query[i].x.l >> query[i].x.r >> query[i].y.l >> query[i].y.r;
        query[i].x.qid = query[i].y.qid = i;
        query[i].x.left = true, query[i].y.left = false;
        range.push_back(query[i].x);
        range.push_back(query[i].y);
    }

    for (int i = 1; i <= n; i++) rk.push_back({L[i], i});
    std::sort(rk.begin(), rk.end());
    std::sort(range.begin(), range.end(), [](const Range &a, const Range &b) { return a.l < b.l || (a.l == b.l && a.r < b.r); });

    auto pl = rk.begin();
    auto pr = range.begin();
    while (pr != range.end()) {
        while (pl != rk.end() && pl->first <= pr->l) {
            update(fw, pl->second, hash[pl->second]);
            update(count, pl->second, 1);
            pl++;
        }

        u64 res = get(fw, pr->l, pr->r);
        u64 cnt = base[pr->l - 1] % MOD;
        u64 as  = res * cnt % MOD;
        if (pr->left) query[pr->qid].Lval = as;
        else query[pr->qid].Rval = as;

        pr++;
    }

    for (int i = 1; i <= q; i++) {
        std::cout << (query[i].Lval == query[i].Rval ? "Yes" : "No") << '\n';
    }
}

B.

C. D. Digits of Prefix Product

核心是考虑 $a_i=10^d-1$ . 以 $x=36483, d=5$ 为例，相当于 $x\times 10^d-x$ ，则有

\begin{array}{r|r} x &36483\\ \times 10^d &3648300000\\ -x & -36843\\ \hline &3648263157 \end{array}

可以发现，只要 $x$ 选的好，再令 $d=len(x)$ ，那么 $(10^d-1)x$ 就基本上不会有相邻两个数位相同。所以我们只需要选好初值即可。

Code

import sys
sys.set_int_max_str_digits(0)

a = int("4267185198539595929746816985463149678978597531947912876793684139682713457571713713824196914894814137")
b = a
print(a)
for i in range(1, 10):
	val = int("9" * len(str(b)))
	b *= val
	print(val)

G. Guarding Plan

首先可以想到的是，有一些点 $p_i$ 可以被其他点 $p_j$ 覆盖（只需要 $p_j$ 在 $p_i$ 的右上角）。我们先排序结合单调栈预处理，排除那些一点会被其他现有的点覆盖掉的那些点。

接下来，我们考虑这样的点：不在凸包上，且没有被其他点覆盖的点 $S$ 。这就意味着我们必须在凸包上的点之间取点，来把 $S$ 覆盖进去。

因为对于两个点 $(x_1,y_1),(x_2,y_2)$ 来说，最小的能同时覆盖两个点的点是 $(\max\set{x_1,x_2},\max\set{y_1,y_2})$ ，我们只需要确保这个点如果在凸包内部那么就一定可以选点覆盖住这两个点。反之，如果这个点不在凸包内，那么这两个点一定不可能被一个点覆盖。

由此，一个重要的观察是：考虑一个凸包上的点 $p_i=(x_i,y_i)$ ，和其两侧但不在凸包上的点 $s_a=(x_1,y_1),s_b=(x_2,y_2)$ ，他们满足 $x_1\lt x_i\lt x_2, y_1\gt y_i\gt y_2$ ，则永远不可能在某条直线上选出点把这两个点覆盖起来。

所以，被凸包边覆盖的点，只可能被凸包边上的点覆盖。这话可能有点抽象，还是看图

Example

浅蓝色的点被蓝色的边覆盖（都在灰色线左侧），淡绿色的点被绿色的边覆盖（都在灰色线右侧），灰色线就是经过凸包点的竖直线

所以问题就变成了，在每个颜色的点的内部，计算出最少需要新建几个点、最少需要几个点才能全覆盖。这是一个 DP 问题，记录 $dp_i=(a,b)$ 表示最少需要 $a$ 个点，需要新建 $b$ 个点。

考虑第 $i$ 个点，我们可以写出如下的转移：

如果不新建点，直接把这个点作为 final guard，那么就有

$dp_i=dp_{i-1} + (1, 0)$
如果考虑新建点，那么我们需要选取 $l$ 使得 $[l,i]$ 之间的所有点都可以被凸包边上的某个点覆盖，根据之前讨论的，也就是 $(\max\set{x_l,x_i}, \max\set{y_l,y_i})$ 在凸包内部，此时可以得出转移

$dp_i=dp_{l-1} + (1, 1)$
而且注意到， $dp_i$ 是单调不减的，也就是我们只关心 $\min l$ 即可。

接着，我们发现，由于点之前已经排过序，所以 $x$ 必然严增且 $y$ 必然严减，故 $\max\set{x_l,x_i}=x_i$ ，所以， $\min l\Longleftrightarrow \max y_l$ ，我们只需要维护一个单调队列即可。

所以总的时间复杂度为 $O(n\log n)$

Code

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using i64       = long long;
using point     = std::pair<i64, i64>;
using vi        = std::vector<int>;
constexpr int N = 2e5 + 10;

std::ostream &operator<<(std::ostream &os, const point &p) { return os << "(" << p.first << ", " << p.second << ")"; }
point operator+(point a, point b) { return {a.first + b.first, a.second + b.second}; }

int n;
point p[N];
int convex[N];

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> p[i].first >> p[i].second;
    std::sort(p + 1, p + 1 + n);

    [&] { // extract useful points
        std::vector<point> stk;
        for (int i = 1; i <= n; i++) {
            while (!stk.empty() && p[i].second >= stk.back().second) stk.pop_back();
            stk.push_back(p[i]);
        }
        for (int i = 1; i <= stk.size(); i++) p[i] = stk[i - 1];
        n = stk.size();
    }();

    auto cross = [&](int px, int a, int b) {
        i64 v1x = p[a].first - p[px].first, v1y = p[a].second - p[px].second;
        i64 v2x = p[b].first - p[px].first, v2y = p[b].second - p[px].second;
        return v1x * v2y - v1y * v2x;
    };

    std::vector<int> stk;
    int tp = -1;
    for (int i = 1; i <= n; i++) {
        while (tp >= 1 && cross(stk[tp - 1], stk[tp], i) >= 0) {
            convex[stk.back()] = false;
            stk.pop_back();
            tp--;
        }
        convex[i] = true;
        stk.push_back(i);
        tp++;
    }

    std::vector<point> dp(n + 1, {0, 0});
    int cnt = 0, c1 = 0;
    for (int i = 1; i <= n; i++) {
        if (convex[i]) { continue; }
        int r = i;
        while (r <= n && !convex[r]) r++; // [i, r)

        std::queue<int> q;
        for (int l = i; l < r; l++) {
            dp[l] = dp[l - 1] + point{1, 0};
            while (!q.empty()) {
                int u    = q.front();
                point t  = {p[l].first, p[u].second};
                p[n + 1] = t;
                if (cross(i - 1, r, n + 1) <= 0) break;
                q.pop();
            }
            if (!q.empty()) { dp[l] = std::min(dp[l], dp[q.front() - 1] + point{1, 1}); }
            q.push(l);
        }

        cnt += dp[r - 1].second;
        c1 += dp[r - 1].first;
        i = r;
    }

    std::cout << stk.size() + c1 << "\n" << cnt << "\n";
}

K. K-rep Array

首先我们可以想到的一个思路是，如果 $k$ 是合法的，那么对于 $\forall i,j,i=j\pmod k$ ，要么 $a_i=-1$ 或者 $a_j=-1$ ，要么 $a_i=a_j$ .

那么一个 $O(n^2)$ 的做法是显而易见的：枚举 $k$ ，然后枚举每一个 $i$ ，用哈希表 $hash[i\mod k]$ 记录 $a_i$ 是否都相等

考虑怎么加速这一过程。现在的判断方式基本不涉及四则运算，考虑改写一下是否有什么性质。让 $a_i=-1$ 的 $a_i$ 变成 $0$ ，且令

f(d)=\sum_{i-j=d}a_ia_j(a_i-a_j)^2=\sum_{i-j=d} a_ia_j^3 - 2a_i^2a_j^2 + a_i^3a_j

如果 $k$ 是合法的，那么应该有 $f_k=f_{2k}=\dots=f_{ik}=0$ . 只要我们可以求出 $f(d),d\in [1,n]$ 的值，那么我们枚举 $k$ ，然后检查 $f(k),f(2k),\dots,f(\lfloor\frac{n}{k}\rfloor\cdot k)$ 就可以在 $O(n\log n)$ 的时间内解出答案。

考虑怎么快速求出 $f(d),d\in [1,n]$ . 我们可以使用多项式乘法进行加速. 比如说，把 $f(d)$ 拆成三个部分： $\sum_{i-j=d}a_ia_j^3$ ， $\sum_{i-j=d}a_i^2a_j^2$ ， $\sum_{i-j=d}a_i^3a_j$

对于第一部分 $\sum_{i-j=d}a_ia_j^3$ ，考虑构造这么两个多项式

g_1(x)=a_1^3+a_2^3x+a_3^3x^2+a_4^3x^3+\dots a_n^3x^{n-1}\\ g_2(x)=a_n+a_{n-1}x+a_{n-2}x^2+a_{n-3}x^3+\dots a_1x^{n-1}\\

所以 $h_1(x)=g_1(x)\ast g_2(x)$ 的卷积结果为

h_1(x)=a_1^3a_n+\Big( a_1^3a_{n-1}+a_2^3a_{n} \Big)x + \Big( a_1^3a_{n-2} + a_2^3a_{n-1} + a_3^3a_{n} \Big)x^2 + \dots

我们可以发现的规律是： $\Big( \sum_{i-j=d} a_ia_j^3 \Big)x^{n-1-d}$ （我们这里只需要考虑前 $n-1$ 项，即 $d=\set{1,2,\dots, n-1}$ ）

同理，我们再做两次这样的卷积 $h_2(x),h_3(x)$ ，就可以求出

H(x)=h_1(x)-2h_2(x)+h_3(x)

再将 $f(d)$ 对应到 $H(x)$ 的系数就可以了。时间复杂度 $O(n\log n)$

Code

我这里用 NTT 实现多项式卷积，FFT 用 long double 也不行，会有精度问题。模数用 $998244343$ 也会被卡

#include <algorithm>
#include <cassert>
#include <iostream>
constexpr int N   = 2e5 + 10;
constexpr int M   = 524289; // 524288 + 1
constexpr int MOD = 740294657;
constexpr int P   = 3;
using i64         = long long;

int n, lim = 1;
i64 a[M], r[M];
i64 op1[M], op2[M];
i64 p1[M], p2[M], p3[M], p[M];
int ans[N];

int fpow(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) res = (i64)res * a % mod;
        a = (i64)a * a % mod;
        b >>= 1;
    }
    return res;
}

void NTT(i64 *d, int lim, int inv) {
    for (int i = 0; i < lim; i++)
        if (i > r[i]) std::swap(d[i], d[r[i]]);

    for (int m = 2; m <= lim; m <<= 1) {
        int k  = m >> 1;
        int gn = fpow(P, (MOD - 1) / m, MOD);
        for (int i = 0; i < lim; i += m) {
            int g = 1;
            for (int j = 0; j < k; j++, g = 1ll * g * gn % MOD) {
                int tmp      = 1ll * d[i + j + k] * g % MOD;
                d[i + j + k] = (d[i + j] - tmp + MOD) % MOD;
                d[i + j]     = (d[i + j] + tmp) % MOD;
            }
        }
    }

    if (inv == -1) {
        std::reverse(d + 1, d + lim);
        int inv_lim = fpow(lim, MOD - 2, MOD);
        for (int i = 0; i < lim; i++) d[i] = 1ll * d[i] * inv_lim % MOD;
    }
}

int main() {
    std::cin >> n;
    while (lim < (n << 1)) lim <<= 1;
    assert(lim < M);

    for (int i = 0; i < n; i++) std::cin >> a[i], a[i] += a[i] == -1;
    for (int i = 0; i < lim; i++) r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);

    // PART 1
    for (int i = 0; i < n; i++) {
        op1[i] = a[i] * a[i] % MOD * a[i] % MOD;
        op2[i] = a[n - 1 - i];
    }
    NTT(op1, lim, 1), NTT(op2, lim, 1);
    for (int i = 0; i < lim; i++) p1[i] = op1[i] * op2[i] % MOD, op1[i] = op2[i] = 0;
    NTT(p1, lim, -1);

    // PART 2
    for (int i = 0; i < n; i++) {
        op1[i] = a[i] * a[i] % MOD;
        op2[i] = a[n - 1 - i] * a[n - 1 - i] % MOD;
    }
    NTT(op1, lim, 1), NTT(op2, lim, 1);
    for (int i = 0; i < lim; i++) p2[i] = op1[i] * op2[i] % MOD, op1[i] = op2[i] = 0;
    NTT(p2, lim, -1);

    // PART 3
    for (int i = 0; i < n; i++) {
        op1[i] = a[i];
        op2[i] = a[n - 1 - i] * a[n - 1 - i] % MOD * a[n - 1 - i] % MOD;
    }
    NTT(op1, lim, 1), NTT(op2, lim, 1);
    for (int i = 0; i < lim; i++) p3[i] = op1[i] * op2[i] % MOD, op1[i] = op2[i] = 0;
    NTT(p3, lim, -1);

    // H(x)
    for (int i = 0; i < lim; i++) p[i] = ((p1[i] - 2ll * p2[i] % MOD + p3[i]) % MOD + MOD) % MOD;
    for (int d = n - 1, pw = 0; d > 0; d--, pw++) ans[d] = p[pw] != 0;
    for (int g = 1; g < n; g++) {
        int w = ans[g];
        for (int j = 2 * g; j < n; j += g) w |= ans[j];
        std::cout << 1 - w;
    }
    std::cout << "1\n";
}

The 3rd Universal Cup. Stage 39: Tokyo

A. Array Similarity

B.

C.

D. Digits of Prefix Product

G. Guarding Plan

K. K-rep Array

M.