寒假营第四场题解

Easy：E、I、K

Mid：B、C、D

Hard：A、F、J、L

AK：G、H

前言

川柳一则：

出题人摸鱼

就让我来写官解

结果偷偷卷

本来出题人说不写题解，让我帮他写的，结果他好像昨晚写了，那我就乱写了。

原本这场在第一场，但是我感觉这场太难了，然后在 K 题中客串的 “浅川☆☆击剑🤺” 就决定跟原来的第四场换一下顺序。

说一下难度划分的原因：

内测榜中， D 题是通过人数第三多的，但似乎很多人的 D 都是猜出来的，实际难度应该并不是很简单。

B 题需要使用 DFS 或者二进制枚举，理论上不应该分类到简单题中，可能这题比较简单，最后通过的人数说不定也不少，但我还是认为这题应该要划分到中档题里面。

H 的思维难度其实不高，就是纯纯的恶心人，感觉除了实在没题可开的情况下，绝对不会有人想碰它。

感觉整体难度挺大的，甚至从简单题开始就不是很简单，代码量也极大，而且这场也是前几场中第一场不把签到题放 A 的场次。

————————————————分界线————————————————

以上是提前写好的，此处开始是赛时写的。

今天上午，出题人似乎还想在 G 题后加一个 EX 版本卡掉 2log ，最后也没加，感觉加了之后会非常毒瘤且无聊。

14：45

前四题榜单和我预期中的接近，而 J 来到了防 AK 题的档次，归功于它抽象的读题难度（已经骂过好多次了），实际上 J 题并不是很难，甚至比其他几个 mid 题更简单， D 题也确实不在 easy 的位置， F、G 的通过人数差距较小， 21 分钟就有人吃下了第一坨 H ，真可怕。

神*兰子也拿到了她的 rk1 （虽然 5 分钟后就被 反超），但由于 Tobo 有着 F、G、H 三题的巨大优势，感觉这把胜负已定了，而兰子应该会被 ，G 似乎不像是她会的题， F 和 H 倒是容易弄出来，所以亚军大概率会是 cup-pyy 。

15：15

兰子 H 的第一个思路是 ，看上去是多记录了一个状态导致多了一个循环，只要她想到把多出来的状态去掉应该就会了，然后再坐牢写个一小时左右就能过了。

现在她决定去做 F ，似乎说有一个思路了，看上去马上就要过了（对？对吗？）。

而 cup-pyy 似乎还在死磕 G ，感觉有一定的可能会输罚时。

似乎突然出现了一个神秘的倒开选手 thisislike_fan ，马上就要终结比赛成为第一个 AK 的选手了吗？

而此时 Tobo 也成功过了倒二题，只剩一个 A ，但是感觉应该还是能赢罚时。

cup-pyy 此时也过掉了死磕的 G ，看来榜单还是会和上面预测的差不多。

15：30

兰子过掉了 F ，但是做法跟我并不一样，而应该是正解的做法，如果兰子数据结构水平强一些的话，她应该马上就能过 G 了，但是很可惜，兰子的数据结构水平似乎还不太够。

15：45

兰子居然会了，震惊！

但是群里另一位选手的二分主席树似乎又WA，又TLE，又RE，又MLE，还CE，祝兰子幸运。

16：15

cup-pyy 终于 AK ，来到了冠军的位置，Tobo 由于不会分类讨论，看上去反而要输罚时了。

兰子终于发现了她的 H 多了一个循环，现在会做了，那么她在 17：00 之前能过吗？先相信一下！

16：45

兰子居然半小时就过了 H ，太强了。

此时兰子已经来到了 的位置，接下来能不能过她的二分主席树呢？

兰子感觉二分主席树不太对，于是摆烂后直接 Steam 启动了！

我写好了剧本，兰子演完了剧本，完美！可惜兰子不够相信自己，如果她相信自己，说不定就能 AK 了。

E Tokitsukaze and Dragon's Breath

枚举、哈希

一个非常经典（很原）的题。

存储对角线有一个小技巧：

1） 从左上到右下的对角线满足 都相等。

1） 从左下到右上的对角线满足 都相等。

不信的话你可以试一下。

因此我们可以将每一条对角线上所有的数字之和记录下来。

然后枚举每一个格子作为“龙之吐息”的中心位置。

中心位置所在的两条对角线上的数字之和减去中心的数字就是这在这个中心使用“龙之吐息”的收益。

枚举所有位置作为中心计算收益后取一个最大值即可。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        map<int, long long> mp1, mp2;
        vector a(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                int x;
                cin >> x;
                mp1[i + j] += x;
                mp2[i - j] += x;
                a[i][j] = x;
            }
        }
        auto ans = 0ll;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                auto sum = mp1[i + j] + mp2[i - j] - a[i][j];
                ans = max(ans, sum);
            }
        }
        cout << ans << endl;
    }
}

I Tokitsukaze and Pajama Party

字符串、模拟、枚举、前缀和

非常无趣的一个题，一个简单的知识点，缝合了一个长长的背景。

本质上等价于问字符串中有多少个 "ab" 子序列。

上述问题的做法是枚举每一个 'b' ，看这个 'b' 的前面有多少个 'a' ，记录前面有多少个 'a' 需要使用前缀和的思想。

我们把 "u" 作为 'a' ， "uwawauwa" 看成一个整体作为 'b' ，接下来就是看这个 'b' 前面有多少个 'a' 。

由于这里的 "*" 号至少需要占一个位置，因此我们需要看的是 'b' 的前一个位置之前有多少个 'a' 。

（但是正则表达式中 '*' 应该是可以匹配 0 个字符的，匹配非 0 个字符要用 '+' 才对）

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        s = " " + s + "BanG Dream! Ave Mujica!";
        int f = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            string t = s.substr(i + 1, 8);
            if(t == "uwawauwa") ans += f;
            f += s[i] == 'u';
        }
        cout << ans << endl;
    }
}

K Tokitsukaze and Shawarma

阅读理解

按照题目描述模拟即可。

本场没有任何难度的一题，为什么不放在 A 呢？

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int x, y, z, a, b, c;
        cin >> x >> y >> z >> a >> b >> c;
        int ans = max({x * a, y * b, z * c});
        cout << ans << endl;
    }
}

B Tokitsukaze and Balance String (easy)

搜索、二进制枚举

数据范围较小，因此我们可以二进制枚举每一个 '?' 填什么。

之后再枚举每一个字符翻转后是否可以将字符串变平衡。

计算答案即可。

时间复杂度 。

全都不会写！

C Tokitsukaze and Balance String (hard)

思维、分类讨论

本题为上一题的 hard 版，是这一套题中比较有趣的一题。

首先根据上题，我们需要发现两个结论：

1） 首尾相同的字符串一定是平衡的。

2） 首尾不相同的字符串一定是不平衡的。

那么可以推导出下面四个结论：

1） 一个平衡的字符串翻转除了首尾外的任意一个字符后依然是平衡的。

2） 一个不平衡的字符串只有翻转首尾字符才可能变成平衡的。

记录字符串长度为 ，字符串中 '?' 的数量为 ，接下来需要使用。

接下来就是分类讨论：

1） 字符串长度为 1 ：

​ 1.1） 字符串为 '?' ，答案为 2 。

​ 1.2） 否则，答案为 1 。

​ 直接特判结束。

2） 字符串首尾都不是 '?' ：

​ 2.1） 字符串首尾相同，那么字符串中间任意翻转一个都行（ ）。

​ 2.2） 字符串首尾不同，那么字符串首尾任意翻转一个都行（ ）。

​ 答案记得乘上字符串的种类数，即要乘以 。

3） 字符串首尾中有一个 '?' ：

​ 3.1） 如果将首尾中的 '?' 填成首尾相同，那么字符串中间任意翻转一个都行（ ）。

​ 3.2） 如果将首尾中的 '?' 填成首尾不同，那么字符串首尾任意翻转一个都行（ ）。

​ 答案就是两种情况相加后再乘上字符串的种类数，由于固定了首尾中的一个 '?' ，最后还需要除以 2 ，即 。

4） 字符串首尾都是 '?' ：

​ 4.1） 如果将首尾中的 '?' 填成首尾相同，那么字符串中间任意翻转一个都行（ ）。

​ 4.2） 如果将首尾中的 '?' 填成首尾不同，那么字符串首尾任意翻转一个都行（ ）。

​ 答案就是两种情况相加后再乘上字符串的种类数，由于固定了首尾中的两个 '?' ，导致最后首尾相同和不同各有 2 种情况，最后还需要除以 4 后再乘以 2 ，即 。

可以发现（3）和（4）的结论是一致的，所以实际写代码时可以把两种情况合并。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

const int M = 1e9 + 7;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        if(s.size() == 1){
            if(s == "?") cout << 2 << endl;
            else cout << 1 << endl;
            continue;
        }
        s = " " + s;
        int cnt = ranges::count(s, '?');
        int ksm = 1;
        for(int i = 1; i <= cnt; i++){
            ksm *= 2;
            ksm %= M;
        }
        int ksm_1 = 1;
        for(int i = 1; i <= cnt - 1; i++){
            ksm_1 *= 2;
            ksm_1 %= M;
        }
        int ans = 0;
        if(s[1] != '?' && s[n] != '?'){
            if(s[1] == s[n]) ans = 1ll * ksm * (n - 2) % M;
            else ans = ksm * 2 % M;
        }
        else ans = 1ll * ksm_1 * n % M;
        cout << ans << endl;
    }
}

D Tokitsukaze and Concatenate‌ Palindrome

字符串、贪心、分类讨论

由于字符串可以重排，那么回文串就相当于是一种连连看，消除相同的字符。

那么首先我们第一个想法应该是用短的字符串消除长的字符串，记录无法消除的字符个数为 。

如果一个字符在短字符串中出现了，在长的字符串中也出现了，那就将这个字符在两个字符串中各删除一个。

如果一个字符在短字符串中出现了，在长的字符串中没出现，那这个字符就无法消除，只能进行修改， 。

例如短的字符串为 "abc" ，长的字符串为 "abddf" ，我们可以重排后连起来变成 "abc | ddfba" ，实际上等效于 "c" 和 "ddf" 拼接成 "c | ddf" ， 。

在用短的字符串尝试消除长的字符串后，长的字符串就残余了一些字母，这些残余的字母两两之间也可以相互抵消，最后字母个数为奇数的都会残余一个无法抵消的，记录为 。

例如 "ddf" 中的两个 'd' 可以相互抵消，字符串可以等效变成 "f" ， 。（根据拼接的位置决定放在哪，总有办法可以抵消的）

由于 和 都是无法抵消必须要操作的，那么：

1） ，答案就是 ，因为 中的字符无法相互抵消只能修改成长字符串中的字符。

2） ，先将 与 抵消，再让 两两抵消，答案就是 。

例如上述 "c" 和 "f" 拼成的 "c | f" ，只要将 'c' 修改成 'f' 即可。

若两个字符串为 "abc" ， "abdef" ，就会拼成 "c | def" ，需要先将 'c' 修改成 'f' ，再将 'd' 修改成 'e' ，字符串变成 "f | eef" 。

若两个字符串为 "abccc" ， "abddf" ，就会拼成 "ccc | f" ，由于实际上中间两个 'c' 是无法相互抵消的，因此不能让两个 'd' 相互抵消，需要拼成 "ccc | ddf" ，先将第一个 'c' 修改成 'f' ，再将后两个 'c' 修改成 'd' ，字符串变成 "fdd | ddf" 。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        string s, t;
        cin >> s >> t;
        if(n < m){
            swap(n, m);
            swap(s, t);
        }
        map<int, int> mp;
        for(auto &i : s){
            mp[i]++;
        }
        int sum = 0;
        for(auto &i : t){
            if(mp[i]) mp[i]--;
            else sum++;
        }
        int ans = 0;
        for(auto &[x, y] : mp){
            if(y & 1) ans++;
        }
        if(sum >= ans) ans = sum;
        else{
            ans -= sum;
            ans /= 2;
            ans += sum;
        }
        cout << ans << endl;
    }
}

A Tokitsukaze and Absolute Expectation

概率、期望、打表、找规律、OEIS、分类讨论、数论、快速幂、逆元

本题不做评价。

1） 如果两个区间不相交，那就是两个等差数列相减。

2） 如果两个区间相同，可以先手玩或打表算出区间长度的前几项，然后使用瞪眼法或OEIS大法找到规律。

3） 如果两个区间相交但不相同，可以把相交且相同的部分摘出来，不相交的部分摘出来，分别对应（1）、（2）中的情况。

然后这题就做完了，就是你讨论的时候可能会非常的痛苦。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

const int M = 1e9 + 7;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<pair<int, int>> a(n);
        for(auto &[l, r] : a){
            cin >> l >> r;
        }
        auto C = [&](int l, int r){
            if(l > r) return 0;
            return r - l + 1;
        };
        auto S = [&](int l, int r){
            auto ans = 1ll * (l + r) * C(l, r) / 2;
            if(l > r) ans = 0;
            return ans % M;
        };
        auto Sub = [&](int t){
            int ans = ((__int128)1 * (t - 2) * (t - 1) * (t) / 6) % M;
            return ans;
        };
        auto sum = 0ll;
        for(int i = 1; i < n; i++){
            auto [l, r] = a[i];
            auto [x, y] = a[i - 1];
            if(l > x){
                swap(l, x);
                swap(r, y);
            }
            if(l == x && r > y){
                swap(l, x);
                swap(r, y);
            }
            auto ans = 0ll;
            if(r <= x) ans += S(x, y) * C(l, r) - S(l, r) * C(x, y);
            else if(r <= y){
                if(r < y) ans += S(r + 1, y) * C(l, r) - S(l, r) * C(r + 1, y);
                if(x > l) ans += S(x, y) * C(l, x - 1) - S(l, x - 1) * C(x, y);
                if(r < y && x > l) ans -= S(r + 1, y) * C(l, x - 1) - S(l, x - 1) * C(r + 1, y);
                int t = C(x, r);
                ans += S(1, t - 1) * t;
                ans -= Sub(t);
            }
            else{
                if(y < r) ans += S(y + 1, r) * C(x, y) - S(x, y) * C(y + 1, r);
                if(x > l) ans += S(x, y) * C(l, x - 1) - S(l, x - 1) * C(x, y);
                int t = C(x, y);
                ans += S(1, t - 1) * t;
                ans -= Sub(t);
            }
            auto inv = [&](int x){
                int y = M - 2;
                auto ans = 1ll;
                while(y){
                    if(y & 1) ans = ans * x % M;
                    x = 1ll * x * x % M;
                    y >>= 1;
                }
                return ans;
            };
            ans = (ans + 4ll * M * M) % M;
            sum += __int128(1) * ans * inv(C(l, r)) * inv(C(x, y)) % M;
        }
        cout << sum % M << endl;
    }
}

F Tokitsukaze and Kth Problem (easy)

STL、排序、枚举、二分

本题比较有趣，但我的做法比较神秘，理论有错，实际能过（包括后续的 hard 版本也是），求一个 hack 。

当然，我的神秘解法只要稍微修改一下就是正解了。

趣事：本题解是在第一场的 M 题解上进行修改的，两个题目的难度顺序一致，知识点也几乎完全一致，甚至同样使用到了 。

首先，如果 ，多余的部分实际上是无用的，直接让 即可。

然后我们可以枚举 往前找 ，此时复杂度为 ，显然无法通过。

虽然二元组是 的，但实际上我们只需要找一对 和 ，并不需要管它们之间的大小关系（大不了反过来即可）。

因此我们可以进行排序，再按上述方法进行枚举，依然可以得到答案，虽然整体的复杂度并没有改变。

但是，我们可以发现两个数字相加后模 可以分成两种情况，而且固定 后，一定会有一个临界点 使得 ：

1） ，由于已经排好序的原因， 一定成立。

2） ，由于已经排好序的原因， 一定成立。

接下来我们讨论的 的大小关系均是在模 意义下的！！！！！

这个临界点 显然是可以通过二分得出，接下来枚举每一个 时，分别对临界点 两边枚举 。如果我们在枚举时发现 已经不大于当前的第 大值，那么很显然再往下枚举是没有意义的，可以直接剪枝；否则，将当前第 大值删除，将现在这个值插入进去。

大胆猜测一下，这样剪枝之后，插入删除的次数是在 级别的，大胆开写即可。

至于如果动态维护第 小，直接用 即可。

小技巧：初始时可以在 里放 个 -1 ，可以省略很多边界的判断和结尾的处理等。

由于 同阶，时间复杂度 。

如果你比较聪明的话，你就可以发现，在我上述结论中，临界点分割完之后，对于一个 而言，最有可能加入答案的值一定是 和 中较大的那一个。若是我们选择了 ，很显然下一个就是 和 。

如果我们对所有的 将 和 都放进一个堆里，每次取出一个最大值 从中删除，再插入一个 （注意这里的 不能是临界点和 0 ），这样我们的复杂度就下降到了稳定的 。

代码还是上面的神秘做法。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, p, k;
        cin >> n >> p >> k;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            a[i] %= p;
        }
        ranges::sort(a);
        multiset<int> st;
        for(int i = 1; i <= k; i++){
            st.insert(-1);
        }
        vector<int> r(n + 1);
        for(int i = n; i >= 1; i--){
            r[i] = ranges::lower_bound(a, p - a[i]) - a.begin();
            if(r[i] > i) r[i] = i;
            for(int j = i - 1; j >= 1; j--){
                int t = (a[i] + a[j]) % p;
                if(t <= *st.begin()){
                    if(j >= r[i]) j = r[i];
                    else break;
                }
                st.insert(t);
                st.erase(st.begin());
            }
        }
        for(auto &i : st | views::reverse){
            cout << i << " ";
        }
        cout << endl;
    }
}

J Tokitsukaze and Recall

图论、并查集、BFS、贪心

一个难读且比较板的题目，读题难度有点过于抽象了。

很显然，属于同一个连通块的岛屿可以不使用技能到达，而不同的连通块只能空降。

那么在技能次数有限的情况下，肯定是优先占领尽可能大的连通块。

如果两个连通块大小相同，则第二关键字应该找连通块中最小岛屿的编号尽可能小的连通块。

之后对所有连通块同时进行 BFS 即可。

由于要求占领顺序的字典序，此处我们需要将 BFS 的队列改成优先队列，每一个连通块初始的岛屿就是连通块中编号最小的。

然后我们就会发现，第三个样例过不去，原因是我们可以在同一个连通块中再次空降。也就是说，如果技能次数溢出的话，我们是全图可飞的。

那么要保证字典序的话，需要在占领的第 个岛屿编号不为 时，空降到 ，强行将 的占领进度提前，这样的操作在技能次数用完之前可以一直做（在 BFS 中加入一个特判即可）。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> f(n + 1);
        iota(f.begin(), f.end(), 0);
        vector<int> cnt(n + 1, 1);
        auto find = [&](auto find, int x){
            if(x == f[x]) return x;
            return f[x] = find(find, f[x]);
        };
        auto add = [&](int x, int y){
            x = find(find, x);
            y = find(find, y);
            if(x == y) return;
            if(x > y) swap(x, y);
            f[y] = x;
            cnt[x] += cnt[y];
        };
        vector g(n + 1, vector<int>());
        for(int i = 1; i <= m; i++){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            add(u, v);
        }
        vector<pair<int, int>> ve;
        for(int i = 1; i <= n; i++){
            if(i == find(find, i)) ve.push_back({cnt[i], -i});
        }
        ranges::sort(ve);
        set<int> q;
        int ans = 0;
        while(ve.size() && k){
            auto [x, y] = ve.back();
            ve.pop_back();
            q.insert(-y);
            ans += x;
            k--;
        }
        cout << ans << endl;
        int now = 0;
        vector<int> vis(n + 1);
        while(q.size()){
            auto u = *q.begin();
            if(u != now + 1 && k){
                q.insert(now + 1);
                k--;
                u = *q.begin();
            }
            q.erase(q.begin());
            cout << u << " ";
            vis[u]++;
            now = u;
            for(auto &v : g[u]){
                if(!vis[v]) q.insert(v);
            }
        }
        cout << endl;
    }
}

L Tokitsukaze and XOR-Triangle

前缀和

一个比较需要扎实基础的前缀和题，适合进一步掌握前缀和，以及练习推柿子。

异或计算权值往往需要使用拆位，每一位可以分别讨论。

那对每一位来说，就变成了 ，其中 表示当 成立权值为 1 ，否则为 0 。

那么我们首先对两个数组的每一位都记录一个前缀和。

然后记录每一个后缀的答案 ，更新就是根据 这一位的值，看这一位在 数组 区间中 0 或 1 的个数。

查询时就是先用 ，然后根据 区间中 0 和 1 的个数，乘以 区间中 1 和 0 的个数。

最后对每一位乘以一个这一位对应的二进制值即可。

由于 是同阶的，因此时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

const int M = 1e9 + 7;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, q;
        cin >> n >> q;
        vector<int> a(n + 1), b = a;
        vector fa(n + 1, vector<int>(31)), fb = fa;
        vector<int> f(n + 2);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            fa[i] = fa[i - 1];
            for(int j = 0; j <= 30; j++){
                if(a[i] & (1 << j)) fa[i][j]++;
            }
        }
        for(int i = 1; i <= n; i++){
            cin >> b[i];
            fb[i] = fb[i - 1];
            for(int j = 0; j <= 30; j++){
                if(b[i] & (1 << j)) fb[i][j]++;
            }
        }
        for(int i = n; i >= 1; i--){
            f[i] = f[i + 1];
            for(int j = 0; j <= 30; j++){
                int b1 = fb[n][j] - fb[i - 1][j];
                int b0 = (n - i + 1) - b1;
                if(a[i] & (1 << j)) f[i] += (1ll << j) * b0 % M;
                else f[i] += (1ll << j) * b1 % M;
                f[i] %= M;
            }
        }
        while(q--){
            int l, r;
            cin >> l >> r;
            auto ans = (f[l] - f[r + 1] + M) % M;
            for(int i = 0; i <= 30; i++){
                int a1 = fa[r][i] - fa[l - 1][i];
                int b1 = fb[n][i] - fb[r][i];
                int a0 = (r - l + 1) - a1;
                int b0 = (n - r) - b1;
                auto t = 1ll * a1 * b0 + 1ll * a0 * b1;
                ans -= (t % M) * (1 << i) % M;
                ans = (ans + M) % M;
            }
            cout << ans << endl;
        }
    }
}

G Tokitsukaze and Kth Problem (hard)

STL、排序、枚举、二分、数据结构、主席树

此事在 F 题解中亦有记载。

F 中有一个步骤，排序。

因此我们对每一个区间进行排序，然后按照 F 的做法做即可，那么此时时间复杂度为 ，显然是过不去的。

观察可以发现，我们排序实际上需要的是区间中第 1 大值的位置、第 2 大值的位置…………

并且这个区间是静态的，不带修的，那么有一个很经典的静态区间第 大算法，也就是主席树。

那么如何找到临界点 呢？

我们还是可以和原来一样通过二分，每次在主席树中找区间第 大的数字，最终得到临界点 。

由于 同阶，神秘做法的时间复杂度似乎还是 。

用 F 题题解中用堆优化到正解的方式，我们的复杂度就变成了稳定的 。

代码还是上面的神秘做法。

#include<bits/stdc++.h>

using namespace std;

template<typename T = int>
class PSGT{
public:
    struct node{
        int x;
        int ls, rs;
    };
    vector<node> tr;
    int pt = 0;
    int n = 0;
    vector<T> a;

    PSGT(vector<T> &b, int idx = 1){      //下标必须从1开始
        auto st = set<T>(b.begin() + idx, b.end());
        a = vector<T>(st.begin(), st.end());
        n = a.size();

        pt = b.size() - idx + 1;
        build(0, 0, n - 1);
        for(int i = idx; i < b.size(); i++){
            int t = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
            update(i, i - 1, 0, n - 1, t);
        }
    }

    int build(int u, int l, int r){
        while(tr.size() <= u) tr.push_back({});
        int mid = l + r >> 1;
        tr[u].x = 0;
        if(l < r){
            tr[u].ls = build(++pt, l, mid);
            tr[u].rs = build(++pt, mid + 1, r);
        }
        return u;
    }

    int update(int u, int old, int l, int r, int t){
        while(tr.size() <= u) tr.push_back({});
        int mid = l + r >> 1;
        tr[u] = tr[old];
        tr[u].x = tr[old].x + 1;
        if(l < r){
            if(t <= mid) tr[u].ls = update(++pt, tr[old].ls, l, mid, t);
            else tr[u].rs = update(++pt, tr[old].rs, mid + 1, r, t);
        }
        return u;
    }

    int rank(int le, int ri, int l, int r, int k){
        if(l == r) return l;
        int mid = l + r >> 1;

//区间第k大
        // int t = tr[tr[ri].rs].x - tr[tr[le].rs].x;
        // int ans = 0;
        // if(t >= k) ans = rank(tr[le].rs, tr[ri].rs, mid + 1, r, k);
        // else ans = rank(tr[le].ls, tr[ri].ls, l, mid, k - t);
        // return ans;

//区间第k小
        int t = tr[tr[ri].ls].x - tr[tr[le].ls].x;
        int ans = 0;
        if(t >= k) ans = rank(tr[le].ls, tr[ri].ls, l, mid, k);
        else ans = rank(tr[le].rs, tr[ri].rs, mid + 1, r, k - t);
        return ans;
    }

    int rank(int le, int ri, int k){
        int t = rank(le - 1, ri, 0, n - 1, k);
        return a[t];
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #define endl '\n'
    int T;
    cin >> T;
    while(T--){
        int n, p, k;
        cin >> n >> p >> k;
        vector<int> a(n + 1);
        map<int, vector<int>> mp;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            a[i] %= p;
            mp[a[i]].push_back(i);
        }
        PSGT tr(a);
        vector<array<int, 4>> ve;
        for(int i = 1; i <= n; i++){
            int l, r;
            cin >> l >> r;
            ve.push_back({a[i], l, r, i});
        }
        multiset<int> st;
        for(int i = 1; i <= k; i++){
            st.insert(-1);
        }
        set<pair<int, int>> in;
        auto find = [&](int x, int y){
            if(x > y) swap(x, y);
            int t = in.count({x, y});
            if(!t) in.insert({x, y});
            return t;
        };
        ranges::sort(ve);
        for(auto &[a, l, r, i] : ve | views::reverse){
            int len = r - l + 1;
            int le = 1, ri = len;
            while(le < ri){
                int mid = le + ri + 1 >> 1;
                if(a + tr.rank(l, r, mid) < p) le = mid;
                else ri = mid - 1;
            }
            for(int k = len; k >= 1; k--){
                int b = tr.rank(l, r, k);
                int t = (a + b) % p;
                if(t <= *st.begin()){
                    if(k > le) k = le + 1;
                    else break;
                }
                st.insert(t);
                st.erase(st.begin());
            }
        }
        for(auto &i : st | views::reverse){
            cout << i << " ";
        }
        cout << endl;
    }
}

H Tokitsukaze and Necklace

DP

这是一坨题，一坨非常无趣且恶心的东西，感觉又典又原，还叠了一坨又一坨。

首先，且有用的长度是 3 ，因此记录状态时需要一个维度记录前两位的状态。

又因为项链是首尾相连的，所以记录状态时还需要一个维度记录初始两位的状态。

再由于项链跟三种颜色数量有关，因此记录状态时还需要至少两个维度记录每种颜色剩余的珠子数量。

最后还需要一个维度记录项链当前的长度。

你说最后一个维度可以滚动？别忘了还要还原方案呢！

也就是说现在你需要一个五维数组，那么你调用一个数组就变成了 ，是不是非常痛苦？

当然，你可以每次枚举初始两位的状态，那么就可以减少一维。

或者直接使用三种颜色作为 DP 的状态，也可以优化时间和空间。

虽然这个 DP 数组的定义是非常抽象的，但还好它的转移是比较显然的，也就只需要 6 个 for 循环而已。

事情还没有结束，在求出这个抽象的 DP 数组之后，你还需要进行路径还原。

路径还原完成了，你终于可以连跳几个 for 循环输出答案了。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        vector<int> w(27);
        for(int i = 1; i <= m; i++){
            string s;
            cin >> s;
            s[0] -= 'a';
            s[1] -= 'a';
            s[2] -= 'a';
            int t = s[0] * 9 + s[1] * 3 + s[2];
            cin >> w[t];
        }
        int A = ranges::count(s, 'a');
        int B = ranges::count(s, 'b');
        int C = ranges::count(s, 'c');
        auto dp = vector(n + 1, vector(A + 1, vector(B + 1, vector(9, vector<long long>(9, -1e18)))));
        /*
        aa 00 0
        ab 01 1
        ac 02 2
        ba 10 3
        bb 11 4
        bc 12 5
        ca 20 6
        cb 21 7
        cc 22 8
        */
        if(A >= 2) dp[2][2][0][0][0] = 0;
        if(B >= 2) dp[2][0][2][4][4] = 0;
        if(C >= 2) dp[2][0][0][8][8] = 0;
        if(A && B) dp[2][1][1][1][1] = dp[2][1][1][3][3] = 0;
        if(A && C) dp[2][1][0][2][2] = dp[2][1][0][6][6] = 0;
        if(B && C) dp[2][0][1][5][5] = dp[2][0][1][7][7] = 0;
        auto get = [&](auto &l, auto r){
            l = max(l, r);
        };
        for(int i = 3; i <= n; i++){
            for(int a = 0; a <= A; a++){
                for(int b = 0; b <= B; b++){
                    int c = i - a - b;
                    if(c > C) continue;
                    for(int j = 0; j < 9; j++){
                        for(int l = 0; l < 9; l++){
                            for(int k = 0; k < 3; k++){
                                int t = j * 3 + k;
                                int ne = t % 9;
                                if(k == 0 && a) get(dp[i][a][b][ne][l], dp[i - 1][a - 1][b][j][l] + w[t]);
                                if(k == 1 && b) get(dp[i][a][b][ne][l], dp[i - 1][a][b - 1][j][l] + w[t]);
                                if(k == 2 && c) get(dp[i][a][b][ne][l], dp[i - 1][a][b][j][l] + w[t]);
                            }
                        }
                    }
                }
            }
        }
        long long ans = -1e18;
        auto &f = dp[n][A][B];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                auto t = f[i][j];
                t += w[i * 3 + j / 3];
                t += w[i % 3 * 9 + j];
                ans = max(ans, t);
            }
        }
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                {
                    auto t = f[i][j];
                    t += w[i * 3 + j / 3];
                    t += w[i % 3 * 9 + j];
                    if(t != ans) continue;
                }
                string t;
                int x = n;
                int a = A;
                int b = B;
                int c = C;
                int p = i;
                vector<int> v;
                while(x >= 3){
                    v.push_back(p);
                    int la = p % 3;
                    int na = a - (la == 0);
                    int nb = b - (la == 1);
                    int nc = c - (la == 2);
                    t += la + 'a';
                    for(int k = 0; k < 9; k++){
                        if(k % 3 != p / 3) continue;
                        int t = k * 3 + la;
                        if(dp[x][a][b][p][j] == dp[x - 1][na][nb][k][j] + w[t]){
                            p = k;
                            break;
                        }
                    }
                    a = na;
                    b = nb;
                    c = nc;
                    x--;
                }
                t += j % 3 + 'a';
                t += j / 3 + 'a';
                ranges::reverse(t);
                s = t;
                goto end;
            }
        }
        end:;
        cout << ans << endl;
        cout << s << endl;
    }
}