A. AGI

至少答对 ⌊n−12⌋\lfloor \frac{n-1}{2}\rfloor 个 evaluation 这个条件非常独特：/2/2 暗示，如果我们可以将线段两两分组，只要每组至少对一个，那么就 OK 了.

然后我们考虑怎么分组。考虑每一组的两条线段 a,ba,b：如果 a,ba,b 是不相交的，那么只要都 reject 就可以保证条件了；如果 aa 包含了 bb，那么我们可以 accept aa 且 reject bb 即可（第三种情况，即如果 a,ba,b 相交，我们先等会讨论）

所以我们可以先得出一个初步的贪心策略：将线段按左端点排完序后，用 std::deque 维护还没有被匹配掉的线段，每有一条新线段，优先查看是否能其他匹配出第一、二种情况，第一种情况和 deque.front() 判断是否相离，第二种情况和 deque.back() 判断。

所以就剩下线段相交的情况了，并且 deque 里任意两条线段都有交集（不然的话，如果 front 和 back 没有交集，他们应该会在上面的过程里被匹配掉），这个就直接交替 reject 和 accept 即可。

时间复杂度 O(nlog⁡n)O(n\log n)

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/extc++.h>
#include <bits/stdc++.h>
constexpr int N = 5e5 + 10;

struct Segment {
    int l, r, id;
} seg[N];
int mark[N];
int n;

void run() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        seg[i].id = i;
        mark[i]   = false;
        std::cin >> seg[i].l >> seg[i].r;
    }

    std::sort(seg + 1, seg + 1 + n, [](const Segment &a, const Segment &b) {
        if (a.l != b.l) return a.l < b.l;
        else if (a.r != b.r) return a.r < b.r;
        else return a.id < b.id;
    });

    std::deque<Segment> q;
    for (int i = 1; i <= n; i++) {
        if (!q.empty() && q.front().r <= seg[i].l) {
            mark[q.front().id] = false;
            mark[seg[i].id]    = false;
            q.pop_front();
            continue;
        }
        if (!q.empty() && q.back().r >= seg[i].r) {
            mark[q.back().id] = true;
            mark[seg[i].id]   = false;
            q.pop_back();
            continue;
        }
        q.push_back(seg[i]);
    }

    int t = false;
    for (auto &index : q) {
        mark[index.id] = t;
        t              = 1 - t;
    }

    for (int i = 1; i <= n; i++) std::cout << (mark[i] ? "T" : "N");
    std::cout << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout.tie(nullptr);
#endif
    int t;
    std::cin >> t;
    while (t--) run();
}

B. Collatz Sum

感觉就差了一点，想到了按奇偶分类递归，归纳成等差数列的形式，但是在处理如何递归的时候想错了：想的是按序列长度的奇偶性划分，但是实际上应该按照公差和首项分类。

考虑到 N≤1012N\le 10^{12} 但是 k≤32k\le 32，所以不可能暴力。但是 kk 比较小，考虑能不能在 kk 上做点文章。

我们发现，如果一个序列都是奇数或者都是偶数，那么我们可以直接 consume 掉一层 f(x)f(x)：

∑x are evenfk(x)  ⟹  ∑x/2fk−1(f(x))  ⟹  ∑x/2fk−1(x/2)∑x are oddfk(x)  ⟹  ∑3x+1fk−1(f(x))  ⟹  ∑3x+1fk−1(3x+1) \sum_{x\text{ are even}} f^k(x) \implies \sum_{x/2} f^{k-1}(f(x))\implies \sum_{x/2} f^{k-1}(x/2)\\ \sum_{x\text{ are odd}} f^k(x) \implies \sum_{3x+1} f^{k-1}(f(x))\implies \sum_{3x+1} f^{k-1}(3x+1)

所以这就是我们的 baseline，而且同时注意到当我把等差数列划分成奇偶数 { l },{ r }\set{l},\set{r} 的时候，{ l },{ r }\set{l},\set{r} 也会是等差数列，且公差恰好翻倍。

若当前序列长度为 nn 且公差 dd 为偶数，说明此时这个等差数列奇偶性相同，可以直接 consume 一层 f(x)f(x) 然后递归；否则如果 dd 是奇数，说明当前序列可以分解成 22 个公差为 2d2d 的等差序列，且长度为 n/2n/2，可以进一步递归。

考虑这样做的时间复杂度。考虑长度为 nn 的等差序列，公差 dd 为奇数，我们分成奇偶两部分，对于奇数部分，可以连拆两层 x←3x+12x\gets \frac{3x+1}{2}，而偶数部分可以拆一层 f(x)f(x)。

我们直接考虑每走 33 步会分出多少序列，我们用 (s,d,n)(s,d,n) 表示首项为 ss、公差为 dd、有 nn 项的等差数列：

graph TB;
A("(1,1,n)") -->|1 step| A1[["(1,2,n/2)"]] 
A1 -->|"1 step, consume f(x)"| A1t("(4,6,n/2)") -->|"1 step, consume f(x)"| A1tt[["(2, 3, n/2)"]]
A -->|1 step| A0[["(2,2,n/2)"]] -->|"1 step, consume f(x)"| A0t("(1,1,n/2)")
A0t -->|1 step| A01[["(1,2,n/4)"]]
A01 -->|"1 step, consume f(x)"| A01t("(4,6,n/4)")
A0t -->|1 step| A00[["(2,2,n/4)"]]
A00 -->|"1 step, consume f(x)"| A00t("(1,1,n/4)")
A1tt -->|"1 step"| A11("(2,6,n/4)")
A1tt -->|"1 step"| A10("(5,6,n/4)")
A11 -->|"1 step, consume f(x)"| A11t[["(1,3,n/4)"]]
A10 -->|"1 step, consume f(x)"| A10t[["(16,3,n/4)"]]
A00t -->|"1 step"| A001[["(1,2,n/8)"]]
A00t -->|"1 step"| A000[["(2,2,n/8)"]]
A01t -->|"1 step, consume f(x)"| A01tt[["(2,3,n/4)"]]
A01tt --> X(....)

继续推下去，可以发现每层的方块节点数量是比较有规律的，是 Fibonacci 数列，所以时间复杂度差不多是 O(ϕk),ϕ=1+52O(\phi^k),\phi=\frac{1+\sqrt 5}{2}. 可以通过此题

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "maths/integers/modint.hpp"
#include <bits/stdc++.h>
using i64    = long long;
using Vector = std::array<Zn, 3>;

i64 n, k;
Zn inv2 = Zn(1) / 2;

Zn sum(i64 start, i64 d, i64 num) {
    Zn sum = start, dt = d;
    sum *= num;
    dt *= num, dt *= (num - 1), dt *= inv2;
    return sum + dt;
}

// start, d, num: 记录等差数列
Zn solve(i64 start, i64 d, i64 num, int level, int depth = 0) {
    if (num <= 0) { return Zn(0); }
    if (level == 0) { return sum(start, d, num); }
    if (d % 2 == 0) { // consume one level of f()
        if (start % 2 == 1) return solve(start * 3 + 1, d * 3, num, level - 1, depth);
        else return solve(start / 2, d / 2, num, level - 1, depth);
    }
    // split into 2 parts: odd, even
    else
        return solve(start, d * 2, (num + 1) / 2, level, depth + 1) + solve(start + d, d * 2, num / 2, level, depth + 1);
}

int main() {
    std::cin >> n >> k;
    std::cout << solve(1, 1, n, k) << "\n";
}

E. One Bit

题目要求最少改几个数，我们正难则反，来求最多可以不改多少个数。由于相邻两个数最多只能有一个 bit 不同，所以对于 ai,aj,i>ja_i,a_j,i\gt j 来说，最多有 ∣i−j∣|i-j| 个 bit 不同。记 dpidp_i 表示 a1∼aia_1\sim a_i 最多可以保留 dpidp_i 个数，则

dpi=max⁡j<i{ dpj+1 }if bitdiff(ai,aj)≤∣i−j∣ dp_i=\max_{j\lt i}\set{dp_j+1} \quad\text{if } \mathop{\mathrm{bitdiff}}(a_i,a_j)\le |i-j|

乍一看是 O(n2)O(n^2) 的，但考虑到 ai≤260a_i\le 2^{60} 所以我们只需要考虑 i−64≤j<ii-64\le j\lt i 就行了，对于 j<i−64j\lt i-64 我们只需要保留 dp1∼dpjdp_1\sim dp_j 的最大值即可。

时间复杂度 O(n)O(n)

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/extc++.h>
#include <bits/stdc++.h>
template <typename K, typename V>
using umap         = __gnu_pbds::gp_hash_table<K, V>;
using i64          = long long;
constexpr int MAXN = 3e5 + 10;

i64 a[MAXN];
int n;
int dp[MAXN], g[MAXN];

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = std::max(1, i - 64); j < i; j++) {
            int v = std::__popcount(a[i] ^ a[j]);
            if (v <= i - j) dp[i] = std::max(dp[i], dp[j] + 1);
        }

        if (i >= 65) dp[i] = std::max(dp[i], g[i - 64] + 1);
        g[i] = std::max(g[i - 1], dp[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) { ans = std::max(ans, dp[i]); }
    std::cout << n - ans << "\n";
}

H. Merge Sort

考虑把 [l,m)[l,m) 和 [m,r)[m, r) 两个区间归并起来的过程。我们希望 a,ba,b 这两个数在这个双指针归并的过程中会产生比较，那么一定是左右两个指针同时指到 a,ba,b，也就是说排在 a,ba,b 之前的数应该都小于 aa。

换句话说，我们关心的只有 (a,b)(a,b) 这个区间的数，因为这些数绝对不能出现在 bb 所在的一侧，因为这样会导致 aa 提前被双指针归并掉；而 aa 这一侧取什么数都无所谓。

所以，我们这样计数：先选出 bb 这一侧的所有数字，然后进行全排列；然后在剩下的数字里，选出 aa 这一侧的数字，然后进行全排列；最后，对 [0,l),[r,n)[0, l), [r, n) 的所有剩下的数字进行全排列，于是 [l,m)[l,m) 和 [m,r)[m, r) 归并的答案为

Cn−(b−a+1)∣B∣−1⋅A∣B∣∣B∣⋅Cn−∣B∣−1∣A∣−1⋅A∣A∣∣A∣⋅An−∣A∣−∣B∣n−∣A∣−∣B∣ C_{n-(b-a+1)}^{|B|-1}\cdot A_{|B|}^{|B|}\cdot C_{n-|B|-1}^{|A|-1}\cdot A_{|A|}^{|A|}\cdot A_{n-|A|-|B|}^{n-|A|-|B|}

这里

  • ∣B∣|B| 表示 bb 这一侧的数组长度，∣A∣|A| 表示 aa 这一侧的数组长度
  • Cn−(b−a+1)∣B∣−1C_{n-(b-a+1)}^{|B|-1} 中
    • n−(b−a+1)n-(b-a+1) 表示 bb 这一侧可以选择的数字个数（不能选 a,ba,b 和 (a,b)(a,b) 之间的数）
    • ∣B∣−1|B|-1 表示要选择多少个数，之所以 −1-1 是因为必须放一个 bb
  • A∣B∣∣B∣A_{|B|}^{|B|} 是全排列。我们只关心排列个数，是因为在自底向上归并的过程中这一块一定会被排序成有序的。
  • Cn−∣B∣−1∣A∣−1C_{n-|B|-1}^{|A|-1} 中
    • n−∣B∣−1n-|B|-1 是 aa 这一侧可以选的数字个数，因为 aa 侧什么数都可以取，但是不能取已经在 bb 侧被取走的数
    • ∣A∣−1|A|-1 是因为 aa 侧必须放一个 aa
  • An−∣A∣−∣B∣n−∣A∣−∣B∣A_{n-|A|-|B|}^{n-|A|-|B|} 是剩下的数进行全排列。

这样的复杂度是多少呢？因为是从 [0,n)[0, n) 开始的，所以至多 O(log⁡n)O(\log n) 个不同的长度，对于一个长度，我们只需要计算一次，然后再计算这个长度出现的多少次即可。总体时间复杂度 O(Tlog⁡n)O(T\log n).

Code

注意，这里我没有计算长度出现几次，而是用 dp[len] += dp[left] + dp[right] 的方式。

不加这行代码的话，比如说 len 之前已经计算了一次，那么 if 会直接 return，进而少计算一次 (len+1)/2 的情况而导致答案错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "maths/integers/modint.hpp"
#include <bits/extc++.h>
#include <bits/stdc++.h>
constexpr int N = 1e6 + 10;

template <class K, class V>
using umap = __gnu_pbds::gp_hash_table<K, V>;

Zn fac[N], ifac[N];
void precompute() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i;
    ifac[N - 1] = Zn(1) / fac[N - 1];
    for (int i = N - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1);
}

Zn A(int n, int k = -1) {
    if (k == -1) return fac[n];
    else return fac[n] * ifac[n - k];
}
Zn C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] * ifac[n - k];
}

void run() {
    int n, a, b;
    std::cin >> n >> a >> b;
    if (a > b) std::swap(a, b);

    int m  = b - a - 1;
    Zn ans = 0;

    umap<int, Zn> dp;
    dp[1] = 0;

    auto dfs = [&](auto F, int l, int r, int len) {
        if (len == 1 || dp.find(len) != dp.end()) {
            ans += dp[len];
            return;
        }
        assert(r - l == len);

        Zn tmp   = 0;
        int left = (len + 1) / 2, right = len - left;
        tmp += A(left) * A(right) * C(n - m - 2, right - 1) * C(n - right - 1, left - 1) * A(n - len);
        tmp += A(right) * A(left) * C(n - m - 2, left - 1) * C(n - left - 1, right - 1) * A(n - len);

        dp[len] = tmp;
        ans += tmp;
        F(F, l, l + left, left);
        dp[len] += dp[left];
        F(F, l + left, r, right);
        dp[len] += dp[right];
    };
    dfs(dfs, 0, n, n);

    std::cout << ans << "\n";
}

int main() {
    precompute();
    int t;
    std::cin >> t;
    while (t--) run();
}

I. Santa Claus

细节题。首先解题关键就是排序不等式。我们一步一步进行处理：

如果 a[],b[]a[], b[] 都有 >0\gt 0 的部分，我们就先匹配他们：最大匹配最大，最小匹配最小；都有 <0\lt 0 的部分也是同样的处理。如果此时已经超过 kk 个了，直接结束。

否则接着处理 a[],b[]a[], b[] 中 =0=0 的部分，

N. Frequency Function

我们模拟一次 a  ⟹  f(a)a \implies f(a)，就会发现如果 { a }\set{a} 长度为 nn，则 f(a)f(a) 里至多有 O(n)O(\sqrt n) 个数是非零的。

这个怎么证明呢？考虑让 f(a)f(a) 里非零的数尽可能得多。由于 { f(a) }v\set{f(a)}_v 表示 { a }\set{a} 里 ai=va_i=v 的 ii 的个数，所以为了让 f(a)f(a) 里非零的个数尽可能多，我们优先挑选 vv 较小的。比如说我们挑选了 1…k1\dots k 非零，那么也就是说，{ a }\set{a} 里有 11 个 11、22 个 22…… 即

12+22+33+⋯+k2≤n 1^2+2^2+3^3+\dots +k^2\le n

所以我们可以推断 k=O(n)k=O(\sqrt n). 也就是说，经过有限次 f()f() 操作后，就可以变成终态 1,0,0,0,…1,0,0,0,\dots. 也就是说，如果询问的 kk 比较小，我们可以直接维护出来；否则，我们大概率只需要取前 600600 个 f10(a)f^{10}(a) 然后迭代不超过 3232 次（这个 3232 是随便取的数）就可以计算出 fk(a)f^k(a) 了。这里的时间复杂度差不多是 O(n)O(\sqrt n)

查询有了，那么修改呢？假设我们维护了 LL 层，即 f0(a),f1(a),…,fL−1(a),fL(a)f^0(a), f^1(a),\dots,f^{L-1}(a), f^L(a)，把 f0(a)if^0(a)_i 从 vv 修改为 v′v'，需要在 f1(a)f^1(a) 里扣除 vv 的一次出现次数，然后再加上 v′v' 的一次出现次数；对于 f1(a)f^1(a)，想要 f1(a)[v]←f1(a)[v]−1f^1(a)[v]\gets f^1(a)[v]-1，令 x=f1(a)[v]x=f^1(a)[v] 需要先在 f2(a)[x]f^2(a)[x] 扣除 11，更新完 f1(a)[v]f^1(a)[v] 后再在 f2(a)f1(a)[v]′f^2(a)_{f^1(a)[v]'} 加上 11…… 于是我们发现这就是一个递归的关系，终止条件是到达第 LL 层或者当前位置的值为 00（我们只关心值域 1∼n1\sim n 的出现次数）。令这一部分时间复杂度为 T(L)T(L)，则有

T(L)=2T(L−1)+O(1) T(L)=2T(L-1)+O(1)

解得这一部分是 T(L)=O(2L)T(L)=O(2^L)，实现里，我们可以把 LL 取得小一点。

于是总的时间复杂度是 O(nL+q(2L+32B))O(nL+q(2^L+32B)). 实现里，我取 L=10L=10，查询时取前 B=600B=600，迭代最多 3232 次。（建议取小一点，这个取的差点 TLE 了）

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
constexpr int N  = 3e5 + 10;
constexpr int LV = 10;

int a[N], n, m;
int cnt[LV][N], t[N], r[N];

void update(int level, int x, int val) {
    if (x <= 0 || level >= LV) return;
    if (cnt[level][x] > 0) update(level + 1, cnt[level][x], -1); // remove
    cnt[level][x] += val;
    if (cnt[level][x] > 0) update(level + 1, cnt[level][x], 1); // add
}

void log() {
    for (int lv = 0; lv < LV; lv++) {
        std::cout << "Level " << lv << ": ";
        for (int i = 1; i <= n; i++) std::cout << cnt[lv][i] << ' ';
        std::cout << '\n';
    }
}

int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) std::cin >> a[i], cnt[0][i] = a[i];
    for (int i = 1; i < LV; i++) {
        for (int j = 1; j <= n; j++) cnt[i][cnt[i - 1][j]] += 1;
    }

    while (m--) {
        int op, x, y;
        std::cin >> op >> x >> y;
        if (op == 2) {
            if (x < LV) {
                std::cout << cnt[x][y] << '\n';
                continue;
            }

            for (int i = 1; i <= 600; i++) r[i] = cnt[LV - 1][i];
            for (int lv = LV; lv <= std::min(32, x); lv++) {
                for (int i = 1; i <= 600; i++) t[i] = r[i], r[i] = 0;
                for (int i = 1; i <= 600; i++) r[t[i]] += 1;
            }

            std::cout << r[y] << '\n';
        } else {
            update(1, a[x], -1); // remove old value
            a[x] = cnt[0][x] = y;
            update(1, a[x], 1); // add new value
        }
    }
}