Znzryb's Blog

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——G. GATA-CAT（骨架插入式构造方法）

Posted on 2026-03-25

题目大意

题目描述
构造一个长度不超过 $500$ 且仅由大写字母 C、G、A、T 组成的非空字符串，使其满足以下两个条件：

字符串中包含恰好 $G$ 个子序列 GATA（即字符 G、A、T、A 按顺序出现，中间可以包含其他字符）。
字符串中包含恰好 $C$ 个子序列 CAT（即字符 C、A、T 按顺序出现，中间可以包含其他字符）。

输入格式
第一行包含一个整数 $Q$ （ $1 \le Q \le 1000$ ），表示询问的组数。
接下来的 $Q$ 行，每行包含两个整数 $G$ 和 $C$ （ $0 \le G, C \le 10^6$ ），分别表示所需的 GATA 子序列的数量和 CAT 子序列的数量。

输出格式
对于每组询问，输出一行满足条件的字符串（长度不超过 $500$ 且仅包含 C、G、A、T）。如果存在多个解，输出任意一个即可。题目保证在给定限制下一定有解。

样例输入与输出

样例 1：

Input:
4
1 1
2 3
18 1
2 1

Output:
GATCAT
GGCATAT
GATGGATATCAT
GGATCAT

样例 2：

Input:
5
1 0
0 1
1 1
0 0
0 0

Output:
GATAT
CAT
GATCAT
GG
GG

样例解释

对于样例 1 的第一组询问（ $G=1, C=1$ ），输出为 GATCAT：

GATA 子序列的数量为 $1$ （由第 1 个字符 G、第 2 个字符 A、第 3 个字符 T、第 5 个字符 A 组成）。
CAT 子序列的数量为 $1$ （由第 4 个字符 C、第 5 个字符 A、第 6 个字符 T 组成）。

对于样例 2 的第一组询问（ $G=1, C=0$ ），输出为 GATAT：

GATA 子序列的数量为 $1$ （由第 1 个字符 G、第 2 个字符 A、第 3 个字符 T、第 5 个字符 A 组成）。
由于字符串中完全不包含字符 C，因此 CAT 子序列的数量为 $0$ 。

思路讲解

gemini 的固定骨架式插入构造方法

题目描述

需要构造一个长度不超过 $500$ 且仅由大写字母 C、G、A、T 组成的非空字符串，要求该字符串中包含恰好 $G$ 个 GATA 子序列和恰好 $C$ 个 CAT 子序列。
输入包含多组询问（ $Q \le 1000$ ），每组询问给出 $G$ 和 $C$ （ $0 \le G, C \le 10^6$ ）。

解题思路

我们可以采用“固定骨架 + 贪心插入字符”的策略。
首先，我们构造一个由 A 和 T 交替组成的骨架字符串： $(AT)^K = \text{ATAT}\dots\text{AT}$ （共 $K$ 对）。
因为目标子序列 CAT 和 GATA 分别以唯一的字符 C 和 G 开头，且在我们的构造中，C 和 G 只会作为这两个子序列的起始字符，所以它们的贡献是完全独立且互不干扰的。
当我们在这个骨架中插入一个 C 时，它能形成的 CAT 数量仅取决于它右侧的 A 和 T。
如果我们把 C 插入到倒数第 $i$ 个 A 的前面（即其右侧恰好有 $i$ 对 AT），那么它右侧的骨架字符串本质上是 $(AT)^i$ 。
经过数学推导，在 $(AT)^i$ 中：

AT 子序列的数量为： $\text{AT}_i = \frac{i \times (i+1)}{2}$
ATA 子序列的数量为： $\text{ATA}_i = \frac{(i-1) \times i \times (i+1)}{6}$
因此，在倒数第 $i$ 个 A 前面插入一个 C，就会增加 $\text{AT}_i$ 个 CAT；同理，插入一个 G，就会增加 $\text{ATA}_i$ 个 GATA。
为了用最少的字符凑出恰好 $C$ 个 CAT 和 $G$ 个 GATA，我们可以将其转化为完全背包问题（找零钱问题）。由于 $\text{AT}_i$ 是三角形数， $\text{ATA}_i$ 是四面体数，它们的增长速度非常快，使用贪心算法（每次优先分配面值最大的数）可以极快地完成任务，且所需的“硬币”数量极少。
经过计算，当选定 $K = 130$ 时：
骨架长度为 $260$ 。
最大可用面值 $\text{AT}*{130} = 8515$ ， $\text{ATA}*{130} = 366145$ 。
凑出最大的 $10^6$ 时，最多只需要约 $120$ 个 C 和约 $10$ 个 G。
总长度最大约为 $260 + 120 + 10 = 390$ ，严格满足题目中要求的不超过 $500$ 字符的限制。

代码实现

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 用于存储骨架后缀带来的增量面值
long long AT[135];
long long ATA[135];

// 预处理所有 AT_i 和 ATA_i 的面值
void precompute() {
    for (int i = 1; i <= 130; i++) {
        AT[i] = (long long)i * (i + 1) / 2;
        ATA[i] = (long long)(i - 1) * i * (i + 1) / 6;
    }
}

void solve() {
    long long G, C;
    cin >> G >> C;

    vector<int> cnt_C(135, 0);
    vector<int> cnt_G(135, 0);

    // 贪心划分 C
    long long rem_C = C;
    for (int i = 130; i >= 1; i--) {
        if (AT[i] > 0) {
            cnt_C[i] = rem_C / AT[i];
            rem_C %= AT[i];
        }
    }

    // 贪心划分 G
    long long rem_G = G;
    for (int i = 130; i >= 1; i--) {
        if (ATA[i] > 0) {
            cnt_G[i] = rem_G / ATA[i];
            rem_G %= ATA[i];
        }
    }

    // 从左到右构造最终字符串
    // 外层循环代表剩余后缀从大到小，倒数第 i 个 A 前方插入字符
    string res = "";
    for (int i = 130; i >= 1; i--) {
        res.append(cnt_C[i], 'C'); // 插入所需数量的 C
        res.append(cnt_G[i], 'G'); // 插入所需数量的 G
        res += "AT";               // 补上骨架的一环
    }

    cout << res << "\\n";
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int Q;
    if (cin >> Q) {
        while (Q--) {
            solve();
        }
    }
    return 0;
}

复杂度分析与代码解释

时间复杂度：
预处理的时间复杂度为 $O(K)$ 。对于每组询问，贪心求解两个面值数组并拼装字符串的操作最多只需要遍历 $K$ 次，循环内的除法与取模均为常数时间操作，因此单次查询的时间复杂度为 $O(K)$ 。
总时间复杂度为 $O(K + Q \times K)$ ，其中 $K = 130, Q \le 1000$ ，总体运算量不到 $2 \times 10^5$ 次，能够在一瞬间通过 $1000$ 组询问。
空间复杂度：
我们只用了一维数组存储 $130$ 个计算好的面额，和输出使用的字符串等局部变量，空间复杂度为 $O(K)$ 。极低的内存占用，安全可靠。
特殊边界考虑：
当 $G = 0, C = 0$ 时，所有的余数分配都会置零。最终程序只会打印单纯由 $(AT)^{130}$ 构成的骨架，此时没有 C 也没有 G 混入其中，答案为合法字符串，长 $260$ ，完美符合题意。最大要求情况下，贪心的结果余数迅速收敛下降，确保最终总长度不会越过 $500$ 限制。

AC代码

源代码

心路历程（WA，TLE，MLE……）

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——F. Fun with Balls（读题面，一定要把每句话都读到，你就看大写字母就完了）（其实，你会发现，虽然 n 的大小为 150，但是需要你决策的地方其实不多）

Posted on 2026-03-24 Edited on 2026-03-25

题目大意

一开始没注意到这句话，绷不住了。注意，读题面，一定要把每句话都读到，你就看大写字母就完了。

也不能怪我，这个 if 在 cf 题面上的这个位置太阴了。

题意总结

给定 $N$ 个球，以及它们被依次使用时的颜色序列 $K_1,K_2,\dots,K_N$ 。

Antonella 按如下规则逐个放球，且每一步之后都必须保持整个球堆稳定：

第一个球一定放在地面上。
之后每次加入一个新球时，这个球要么放在地面上，要么恰好放在两个球的正上方。
所有在地面上的球必须紧密排列，中间不能有空隙。
如果当前有多个合法放置位置，Antonella 一定选择最高的位置。
如果最高的位置不止一个，则她可以任选其中一个。

若若干个同色球两两之间可以通过“接触”的球一路连通，则它们构成一个同色连通块，称为一个 cluster。cluster 的大小就是其中球的个数。

题目要求你在所有可能构造出的稳定球堆中，求出：

所有颜色的所有 cluster 里，最大 cluster 的大小 的最大可能值。

也就是说，要输出 Antonella 在满足规则的前提下，最终有可能得到的最大同色连通块大小。

输入格式

第一行是整数 $N$ 。

第二行是 $N$ 个整数 $K_1,K_2,\dots,K_N$ ，表示每个球按加入顺序的颜色。

输出格式

输出一个整数，表示答案。

样例 1

Input
3
1 2 1

Output
2

解释：

先放第一个颜色为 1 的球。第二个颜色为 2 的球也只能放在地面上，可以放在第一个球左边或右边。第三个颜色为 1 的球此时会放到前两个球上方。这样最终颜色为 1 的两个球会连成一个大小为 2 的 cluster，所以答案是 2。

样例 2

Input
3
1 1 1

Output
3

解释：

三个球颜色都相同，不管具体怎么放，最终都能连成一个大小为 3 的同色 cluster，所以答案是 3。

样例 3

Input
4
1 5 5 1

Output
2

解释：

按规则逐步加入后，最大的同色连通块大小最多只能达到 2，因此答案是 2。

样例 4

Input
6
1 2 2 1 2 3

Output
3

解释：

在某种合法构造下，颜色为 2 的球可以形成一个大小为 3 的 cluster，因此答案是 3。

思路讲解

这道题目不是很想补，毕竟暴力嘛，算了。

AC代码

源代码

心路历程（WA，TLE，MLE……）

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——A. Ants on a Ring（这种题目就是推性质）（这个环，一定要想办法化曲为直！一定要在一个地方，把环变成一条直线）

Posted on 2026-03-24

题目大意

题目描述
在一个圆上有 $N$ 只蚂蚁。圆被顺时针划分为 $L$ 个位置，编号为 $1$ 到 $L$ ，其中位置 $L$ 与位置 $1$ 相邻。
每只蚂蚁初始站在不同的位置上，并且都需要到达各自不同的目标位置。
在每一秒内，每只蚂蚁可以选择：

停留在原地。
顺时针或逆时针移动到相邻的位置。

在任何时刻（包括在两个位置之间移动的过程中），任意两只蚂蚁都不能处于同一个位置。例如，如果某只蚂蚁在某一秒内顺时针从位置 $1$ 移动到位置 $2$ ，那么在同一秒内，其他蚂蚁不能进行以下操作：

停留在位置 $2$ （这会导致两只蚂蚁在位置 $2$ 相遇）。
逆时针从位置 $3$ 移动到位置 $2$ （这会导致两只蚂蚁在位置 $2$ 相遇）。
逆时针从位置 $2$ 移动到位置 $1$ （这会导致两只蚂蚁在位置 $1$ 和位置 $2$ 之间相遇）。

你需要判断是否有可能让所有蚂蚁都到达各自的目标位置。如果可以，求出所需的最短时间（秒数）。

输入格式
第一行包含两个整数 $N$ （ $1 \le N \le 1000$ ）和 $L$ （ $1 \le L \le 10^9$ ），分别表示蚂蚁的数量和位置的总数。
第二行包含 $N$ 个互不相同的整数 $A_1, A_2, \dots, A_N$ （ $1 \le A_i \le L$ ），表示每只蚂蚁的初始位置。
第三行包含 $N$ 个互不相同的整数 $B_1, B_2, \dots, B_N$ （ $1 \le B_i \le L$ ），表示每只蚂蚁的目标位置。

输出格式
输出一行，包含一个整数，表示所有蚂蚁到达目标位置所需的最短时间。如果无论如何都无法全部到达目标位置，则输出星号 *。

样例展示与解释

样例 1
输入：

1
2
3

2 2
2 1
2 1

输出：

样例 1 解释：两只蚂蚁初始就已经在各自的目标位置上，因此需要 $0$ 秒。

样例 2
输入：

1
2
3

2 2
1 2
2 1

输出：

样例 2 解释：两只蚂蚁可以同时顺时针（或同时逆时针）移动，仅需 $1$ 秒即可到达目标位置。

样例 3
输入：

1
2
3

1 10
1
7

输出：

样例 4
输入：

1
2
3

3 5
1 3 2
5 2 4

输出：

样例 5
输入：

1
2
3

3 5
1 3 2
4 2 5

输出：

样例 5 解释：三只蚂蚁都可以选择逆时针移动，其中第二只蚂蚁需要在中途停留一秒。

思路讲解

这道题目，实际上可以 $O(n)$ 解决（忽略了快排的时间复杂度），至少我们的做法是这个时间复杂度的。

sort(all(lr_global));
for (int i = 0; i < SZ(lr_global); ++i) {
    if (lr_global[0].r > lr_global[i].r) {
        lr_global[i].r += L;
    }
}
auto check = [&]() -> bool {
    for (int i = 1; i < N; ++i) {
        if (lr_global[i].l == lr_global[i - 1].l) {
            return false;
        }
    }
    for (int i = 1; i < N; ++i) {
        if (lr_global[i].r <= lr_global[i - 1].r) {
            return false;
        }
    }
    return true;
};
if (!check()) {
    cout << "*\n";
    return;
}

核心代码就这一段，只能说化曲为直 yyds。

for (ll shift: {-1, 0, 1}) {
    ll ans = 0;
    for (auto [l,r]: lr_global) {
        ans = max(abs(l + L * shift - r), ans);
    }
    ans_global = min(ans_global, ans);
}

为什么这个代码对呢？其实在化曲为直下，一切都非常简单。

说白了，我们只要 l 的相对位置不变，r 的相对位置不变，那么就一定有解，是不是？

那么，我们知道，一个点，他切换方向，其实就是 l 在化曲为直的线段上，平移了 Len 位。如果其他点不也平移的 L 位的话，这个一定会导致错误的发生（即 l 的相对位置发生变化）！

那么我们就知道了，要切换方向，要么一起切换，要么一起不切换。

当然，你会说，这很奇怪啊，明明这个有些例子是有些点逆时针，有些点顺时针啊？其实，这个是因为为了符合我们的第一个条件，就是起始点和结束点必须都保持升序的条件，在保持这个条件的情况下，其实方向的变化是一起的。

AC代码

AC
http://codeforces.com/gym/106416/submission/368041079

源代码

/**
 * Problem: A. Ants on a Ring
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/A
 * Created: 2026-03-24 19:13:11
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
struct L_R {
    ll l, r;

    bool operator<(const L_R &o) const {
        return l < o.l;
    }
};

void Solve() {
    ll N, L;
    cin >> N >> L;
    vector<L_R> lr_global(N);
    for (int i = 0; i < N; ++i) cin >> lr_global[i].l;
    for (int i = 0; i < N; ++i) cin >> lr_global[i].r;
    // auto lr_backup = lr_global;
    sort(all(lr_global));
    for (int i = 0; i < SZ(lr_global); ++i) {
        if (lr_global[0].r > lr_global[i].r) {
            lr_global[i].r += L;
        }
    }
    auto check = [&]() -> bool {
        for (int i = 1; i < N; ++i) {
            if (lr_global[i].l == lr_global[i - 1].l) {
                return false;
            }
        }
        for (int i = 1; i < N; ++i) {
            if (lr_global[i].r <= lr_global[i - 1].r) {
                return false;
            }
        }
        return true;
    };
    if (!check()) {
        cout << "*\n";
        return;
    }
    ll ans_global = INF;
    for (ll shift: {-1, 0, 1}) {
        ll ans = 0;
        for (auto [l,r]: lr_global) {
            ans = max(abs(l + L * shift - r), ans);
        }
        ans_global = min(ans_global, ans);
    }
    cout << ans_global << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*
AC
http://codeforces.com/gym/106416/submission/368041079

*/

心路历程（WA，TLE，MLE……）

2025 河南省赛——Gym-105941-Problem B. 随机栈 II

Posted on 2026-03-23 Edited on 2026-03-24

题目大意

题目描述
维护一个初始为空的多重集。每次从中取出一个元素时，集合中每个元素被取出的概率均等，取出后该元素从集合中删除。每次取出事件相互独立。
给定 $n$ 次操作序列，操作分为两种：

向集合中插入一个给定的非负整数。
从集合中随机取出一个元素。
保证每次取出时集合非空，且整个操作序列至少包含一次取出操作。
求所有被取出的元素排成的序列满足单调不降（即序列中每一项都小于等于它的后一项）的概率。答案对 998244353 取模。

输入格式
第一行包含一个正整数 $T$ （ $1 \le T \le 2.5 \times 10^3$ ），表示测试数据组数。
每组数据第一行包含一个整数 $n$ （ $2 \le n \le 5 \times 10^3$ ），表示操作总数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $-1 \le a_i \le n$ ），表示操作序列：

$a_i \ge 0$ 表示向集合中插入 $a_i$ 。
$a_i = -1$ 表示从集合中随机取出一个元素。
保证所有数据的 $\sum n \le 5 \times 10^3$ 。

输出格式
对于每组数据，输出一行一个整数，表示概率对 998244353 取模的结果。

样例输入 1

3
3
1 2 -1
5
1 2 -1 3 -1
7
1 2 3 4 -1 -1 -1

样例输出 1

1
2
3

1
249561089
166374059

样例输入 2

3
4
1 2 -1 -1
6
1 2 -1 -1 1 -1
8
1 -1 2 -1 3 -1 4 -1

样例输出 2

1
2
3

499122177
0
1

样例解释
对于样例一的第 1 组数据，由于总共只取出了一个元素，序列无论如何都是单调不降的，概率为 1。

对于样例一的第 2 组数据，操作过程和对应概率如下：

加入 1，集合变为 $\{1\}$ ；加入 2，集合变为 $\{1, 2\}$ 。
此时取出 1 的概率为 $\frac{1}{2}$ 。若取出 1，接下来加入 3，集合变为 $\{2, 3\}$ 。之后无论取出哪个数，得到的序列（1 然后是 2 或 1 然后是 3）均满足单调不降。此情况的合法概率为 $\frac{1}{2} \times 1 = \frac{1}{2}$ 。
此时取出 2 的概率为 $\frac{1}{2}$ 。若取出 2，接下来加入 3，集合变为 $\{1, 3\}$ 。之后为了保持单调不降，必须取出 3，取出 3 的概率为 $\frac{1}{2}$ 。此情况的合法概率为 $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ 。
最终单调不降的总概率为 $\frac{1}{2} + \frac{1}{4} = \frac{3}{4}$ 。 $\frac{3}{4}$ 对 998244353 取模的结果为 249561089。

思路讲解

这道题目其实不难，就是细节比较多。

for (ll op = 1; op <= cnt_op; ++op) {
    vector<ll> vals;
    for (int val = 0; val <= N; ++val) {
        if (op_val_cnt[op][val] >= 1) {
            vals.push_back(val);
        }
    }
    if (op == 1) {
        for (auto val: vals) {
            dp_val_cnt[val].resize(2);
            // 注意，有多个数字可选的时候，有多种可能，答案不是 1
            dp_val_cnt[val][1] = op_val_cnt[op][val];
            dpacc_val[val] = op_val_cnt[op][val];
        }
    } else {
        vector<vector<ll> > ndp_val_cnt(N + 2);
        vector<ll> ndpacc_val(N + 2);
        vector<ll> presum_dpacc(N + 2);
        // 注意使用前缀和优化
        partial_sum(all(dpacc_val), presum_dpacc.begin(), [](ll a, ll b) {
            return (a + b) % mod;
        });
        for (auto val: vals) {
            ll val_cnt = op_val_cnt[op][val];
            ndp_val_cnt[val].resize(min(op, val_cnt) + 2);
            for (int cnt = 1; cnt <= min(op, val_cnt); ++cnt) {
                ll rem_val = val_cnt - cnt + 1;
                if (cnt >= 2) {
                    if (cnt - 1 > SZ(dp_val_cnt[val]) - 1) {
                        break;
                    }
                    ndp_val_cnt[val][cnt] = rem_val * dp_val_cnt[val][cnt - 1];
                    ndp_val_cnt[val][cnt] %= mod;
                } else {
                    // for (int s_val = 0; s_val < val; ++s_val) {
                    //     ndp_val_cnt[val][cnt] += dpacc_val[s_val];
                    //     ndp_val_cnt[val][cnt] %= mod;
                    // }
                    if (val - 1 >= 0) {
                        ndp_val_cnt[val][cnt] = presum_dpacc[val - 1];
                    }
                    ndp_val_cnt[val][cnt] *= rem_val;
                    ndp_val_cnt[val][cnt] %= mod;
                }
                ndpacc_val[val] += ndp_val_cnt[val][cnt];
                ndpacc_val[val] %= mod;
            }
        }
        swap(dp_val_cnt, ndp_val_cnt);
        swap(dpacc_val, ndpacc_val);
    }
}

AC代码

AC
https://codeforces.com/gym/105941/submission/367931586

源代码

/**
 * Problem: 随机栈 II
 * Contest: Gym
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/Gym-105941B#author=user:262248
 * Created: 2026-03-23 21:30:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
// 在 k<=0 的时候返回 1
ll binpow(ll a, ll k, const ll &p = mod) {
    ll res = 1;
    a %= p;
    while (k > 0) {
        if ((k & 1) == 1) res = a * res % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    ll cnt_op = count(all(A), -1);
    vector<vector<ll> > op_val_cnt(cnt_op + 2, vector<ll>(N + 2));
    ll tot_num = 1;
    do {
        ll opc = 0, numc = 0;
        vector<ll> cnt(N + 2);
        for (int i = 1; i <= N; ++i) {
            if (A[i] == -1) {
                tot_num *= (numc - opc);
                tot_num %= mod;
                opc++;
                op_val_cnt[opc] = cnt;
            } else {
                cnt[A[i]]++;
                numc++;
            }
        }
    } while (false);
    vector<vector<ll> > dp_val_cnt(N + 2);
    vector<ll> dpacc_val(N + 2);
    for (ll op = 1; op <= cnt_op; ++op) {
        vector<ll> vals;
        for (int val = 0; val <= N; ++val) {
            if (op_val_cnt[op][val] >= 1) {
                vals.push_back(val);
            }
        }
        if (op == 1) {
            for (auto val: vals) {
                dp_val_cnt[val].resize(2);
                dp_val_cnt[val][1] = op_val_cnt[op][val];
                dpacc_val[val] = op_val_cnt[op][val];
            }
        } else {
            vector<vector<ll> > ndp_val_cnt(N + 2);
            vector<ll> ndpacc_val(N + 2);
            vector<ll> presum_dpacc(N + 2);
            partial_sum(all(dpacc_val), presum_dpacc.begin(), [](ll a, ll b) {
                return (a + b) % mod;
            });
            for (auto val: vals) {
                ll val_cnt = op_val_cnt[op][val];
                ndp_val_cnt[val].resize(min(op, val_cnt) + 2);
                for (int cnt = 1; cnt <= min(op, val_cnt); ++cnt) {
                    ll rem_val = val_cnt - cnt + 1;
                    if (cnt >= 2) {
                        if (cnt - 1 > SZ(dp_val_cnt[val]) - 1) {
                            break;
                        }
                        ndp_val_cnt[val][cnt] = rem_val * dp_val_cnt[val][cnt - 1];
                        ndp_val_cnt[val][cnt] %= mod;
                    } else {
                        // for (int s_val = 0; s_val < val; ++s_val) {
                        //     ndp_val_cnt[val][cnt] += dpacc_val[s_val];
                        //     ndp_val_cnt[val][cnt] %= mod;
                        // }
                        if (val - 1 >= 0) {
                            ndp_val_cnt[val][cnt] = presum_dpacc[val - 1];
                        }
                        ndp_val_cnt[val][cnt] *= rem_val;
                        ndp_val_cnt[val][cnt] %= mod;
                    }
                    ndpacc_val[val] += ndp_val_cnt[val][cnt];
                    ndpacc_val[val] %= mod;
                }
            }
            swap(dp_val_cnt, ndp_val_cnt);
            swap(dpacc_val, ndpacc_val);
        }
    }
    ll tot_dp_cnt = 0;
    for (int val = 0; val <= N; ++val) {
        for (int cnt = 1; cnt < SZ(dp_val_cnt[val]); ++cnt) {
            tot_dp_cnt += dp_val_cnt[val][cnt];
            tot_dp_cnt %= mod;
        }
    }
    ll ans = tot_dp_cnt * binpow(tot_num, mod - 2);
    ans %= mod;
    cout << ans << "\n";
    // #ifdef LOCAL
    //     debug(tot_dp_cnt);
    //     debug(tot_num);
    //     debug2d(dp_val_cnt);
    // #endif

    // mod
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/105941/submission/367931586

1
3
1 2 -1

*/

心路历程（WA，TLE，MLE……）

do {
  // 注意，还是要把 numc 显式地写出来
    ll opc = 0, numc = 0;
    vector<ll> cnt(N + 2);
    for (int i = 1; i <= N; ++i) {
        if (A[i] == -1) {
            tot_num *= (numc - opc);
            tot_num %= mod;
            opc++;
            op_val_cnt[opc] = cnt;
        } else {
            cnt[A[i]]++;
            numc++;
        }
    }
} while (false);

2025 河南省赛——Problem C. Toxel 与宝可梦图鉴（珂朵莉树+值域线段树维护全局信息）（因为这道题目，可以设计珂朵莉树无这个查询操作，只有 assign 操作，因此严格 O(nlogn)）（区间等差数列赋值，全局查询最小众数）

Posted on 2026-03-23 Edited on 2026-03-25

2025 National Invitational of CCPC (Zhengzhou), 2025 CCPC Henan Provincial Collegiate Programming Contest

题目大意

给定一个长度为 $n$ 的数组 $a$ ，初始时第 $i$ 个位置的值为 $a_i$ （ $1 \le a_i \le n$ ）。共有 $m$ 次操作，每次操作给定 $l, r, d$ ，将区间 $[l, r]$ 内的值依次替换为 $d, d+1, \ldots, d+r-l$ 。

在初始状态以及每次操作后，输出数组中出现次数最多的值及其出现次数。若有多个值出现次数相同，输出其中编号最小的。

多组测试数据， $T$ 组，保证 $\sum n \le 2 \times 10^5$ ， $\sum m \le 2 \times 10^5$ 。

样例

输入：
3
3 3
1 2 3
1 1 2
2 2 3
3 3 1
1 1
1
1 1 1
8 8
7 6 6 4 3 8 5 3
4 4 4
6 8 6
1 1 7
4 7 4
6 7 6
2 7 5
1 5 7
1 6 8

输出：
1 1
2 2
3 2
1 1
1 1
1 1
3 2
3 2
6 3
6 3
6 3
6 3
7 2
8 2
8 2

样例解释（第一组数据）

初始数组为 $[1, 2, 3]$ ，三个值各出现 $1$ 次，输出最小编号 $1$ ，次数 $1$ 。

第 $1$ 次操作 $l=1, r=1, d=2$ ：将位置 $1$ 替换为 $2$ ，数组变为 $[2, 2, 3]$ ，值 $2$ 出现 $2$ 次最多，输出 $2\ 2$ 。

第 $2$ 次操作 $l=2, r=2, d=3$ ：将位置 $2$ 替换为 $3$ ，数组变为 $[2, 3, 3]$ ，值 $3$ 出现 $2$ 次最多，输出 $3\ 2$ 。

第 $3$ 次操作 $l=3, r=3, d=1$ ：将位置 $3$ 替换为 $1$ ，数组变为 $[2, 3, 1]$ ，三个值各出现 $1$ 次，输出最小编号 $1$ ，次数 $1$ 。

思路讲解

我看了一下，宝可梦这道题目珂朵莉树不会被卡的原因是因为全局查询，可以通过维护全局信息解决这个问题。
好像只要改成区间查询，区间修改，珂朵莉树一定会被卡。

珂朵莉树的时间复杂度过于玄学了，我还是想用这个时间复杂度更加确定的算法解决问题。

还是学一下珂朵莉树吧，好像这道题目只能用珂朵莉树，或者至少用珂朵莉树最简单，其他各种各样，形形色色的数据结构，都不是说特别好。

不难发现，珂朵莉树只有 assign 操作，肯定是 $O(n\log n)$ ，当然，这个东西没有那么显然，但是不难理解。因为 l，r 越大，需要遍历的区间就越多，但是一次性也把很多区间给整合在一起了。区间小嘛，一共就不遍历几个区间，何谈什么复杂度？

template<class F>
void assign(ll l, ll r, ll val, F on_change) {
    // 这个顺序对于我们 mp 珂朵莉树实现无所谓
    split(r + 1);
    split(l);
    auto it = mp.lower_bound(l);
    while (it != mp.end() && it->first <= r) {
        ll st=it->first;
        auto [ed,val]=it->second;
        // 具体怎么调用看你的 on_change() 实现，一般是一个全局操作
        on_change();
        it = mp.erase(it);
    }
    mp[l]={r,val};
    on_change();
}

我感觉那种只问一次，或者像这种全局询问的，都非常适合珂朵莉树。

AC代码

AC
https://codeforces.com/gym/105941/submission/368114371

源代码

/**
 * Problem: Toxel 与宝可梦图鉴
 * Contest: Gym
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/Gym-105941C
 * Created: 2026-03-24 10:25:47
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 * 2026-02-18: 测试这个线段树二分（找到第 K 个 1）（这里是单点的时候测试的）
 * https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/submission/363516918
 * 2026-02-26: 测试区间加，区间查
 * https://www.luogu.com.cn/record/264293552
 */
struct Tag {
    ll add = 0;
    bool need_apply = false;

    void apply(const Tag &t) {
        add += t.add;
        need_apply = true;
    }

    friend ostream &operator<<(ostream &os, const Tag &t) {
        os << "add:" << t.add;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }
};

struct Info {
    // 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
    // 不过我们其实改进了这个 query 函数，所以说如果说你给的这个数组当中所有的值都是所有的值都是有的话，其实不用考虑初值。
    // 如果一定要赋初值的话，注意就是 sum 类的都不要赋 infinite 然后只有 max 和 min 的你要好好想想。
    struct Cnt_val {
        ll cnt, val = INF;

        bool operator<(const Cnt_val &o) const {
            if (o.cnt != cnt) return cnt < o.cnt;
            return val > o.val;
        }
    };

    ll l = 0, r = 0;
    Cnt_val mx{};

    static Info merge(const Info &a, const Info &b) {
        Info res;
        res.l = a.l;
        res.r = b.r;
        res.mx = max(a.mx, b.mx);
        return res;
    }

    void apply(const Tag &t) {
        if (!t.need_apply) return;
        mx.cnt += t.add;
    }

    friend ostream &operator <<(ostream &os, const Info &a) {
        os << "[" << a.l << ";" << a.r << "]:" << "mx_cnt:" << a.mx.cnt << "  mx_val:" << a.mx.val;
        return os;
    }

    string to_string() const {
        stringstream ss;
        ss << *this;
        return ss.str();
    }
};

using I = Info;
using T = Tag;

struct SEG {
    ll N;
    vector<I> infos;
    vector<T> tags;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N, const vector<I> &a) {
        infos.resize(4 * N + 5);
        tags.resize(4 * N + 5);
        this->N = N;
        build(a, 1, 1, N);
    }

    void push(ll u) {
        if (infos[u].l == infos[u].r) {
            return;
        }
        if (!tags[u].need_apply) {
            return;
        }
        infos[u << 1].apply(tags[u]);
        infos[u << 1 | 1].apply(tags[u]);
        tags[u << 1].apply(tags[u]);
        tags[u << 1 | 1].apply(tags[u]);
        tags[u] = {};
    }

    void pull(ll u) {
        infos[u] = I::merge(infos[u << 1], infos[u << 1 | 1]);
    }

    void build(const vector<I> &a, ll u, ll l, ll r) {
        if (l == r) {
            infos[u] = a[l];
            infos[u].l = l;
            infos[u].r = r;
            return;
        }
        ll mid = l + r >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        pull(u);
    }

    I query(ll u, ll l, ll r) {
        if (infos[u].l >= l && infos[u].r <= r) {
            return infos[u];
        }
        push(u);
        I res{};
        // 为什么要设置 isget 这个 bool 呢？其实是因为防止使用初值进行 merge
        // 我们并不保证使用初值进行 merge 一定是对的。
        bool isget = false;
        if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
            res = query(u << 1, l, r);
            isget = true;
        }
        if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
            if (isget) {
                res = I::merge(res, query(u << 1 | 1, l, r));
            } else {
                res = query(u << 1 | 1, l, r);
            }
        }
        return res;
    }

    void assign(ll u, ll pos, const I &val) {
        if (infos[u].l == infos[u].r && infos[u].l == pos) {
            infos[u] = val;
            infos[u].l = pos;
            infos[u].r = pos;
            return;
        }
        push(u);
        if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
            assign(u << 1, pos, val);
        }
        if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
            assign(u << 1 | 1, pos, val);
        }
        pull(u);
    }

    void modify(ll u, ll l, ll r, const T &t) {
        if (infos[u].l >= l && infos[u].r <= r) {
            infos[u].apply(t);
            tags[u].apply(t);
            return;
        }
        // 在判断完全覆盖之后再去push，不影响结果，会省一点操作
        push(u);
        if (isIntersect(infos[u << 1].l, infos[u << 1].r, l, r)) {
            modify(u << 1, l, r, t);
        }
        if (isIntersect(infos[u << 1 | 1].l, infos[u << 1 | 1].r, l, r)) {
            modify(u << 1 | 1, l, r, t);
        }
        pull(u);
    }

    //  返回第k个有值的下标，当然，要求线段树叶节点值是0或1
    // ll findkth(ll u,ll cur_k) {
    //     push(u);
    //     if (infos[u].l==infos[u].r) {
    //         return infos[u].l;
    //     }
    //     if (cur_k<=infos[u<<1].sum) {
    //         return findkth(u<<1,cur_k);
    //     }
    //     return findkth(u<<1|1,cur_k-infos[u<<1].sum);
    // }

    //
    // void opposite(ll u, ll pos) {
    //     if (infos[u].l == infos[u].r && infos[u].l == pos) {
    //         infos[u].sum ^= 1;
    //         return;
    //     }
    //     if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
    //         opposite(u << 1, pos);
    //     }
    //     if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
    //         opposite(u << 1 | 1, pos);
    //     }
    //     pull(u);
    // }

    template<class F>
    ll findFirst(ll u, ll l, ll r, F &&fun) {
        push(u);
        if (infos[u].l == infos[u].r) {
            if (fun(infos[u])) return infos[u].l;
            return -1;
        }
        ll res = -1;
        if (isIntersect(infos[u << 1].l, infos[u << 1].r, l, r) && fun(infos[u << 1])) {
            res = findFirst(u << 1, l, r, fun);
        }
        if (res != -1) return res;
        if (isIntersect(infos[u << 1 | 1].l, infos[u << 1 | 1].r, l, r) && fun(infos[u << 1 | 1])) {
            res = findFirst(u << 1 | 1, l, r, fun);
        }
        return res;
    }

    /*
     *AC https://codeforces.com/gym/106169/submission/363483057
     *线段树可视化 AC 记录
     */
#ifdef LOCAL
    string node_str(ll u) const {
        string s = infos[u].to_string();
        if (tags[u].need_apply)
            s += " {" + tags[u].to_string() + "}";
        return s;
    }

    vector<ll> vis_w;
    ll vis_depth;

    void visualize() {
        vis_w.assign(4 * N + 2, 0);
        vis_depth = 0;
        cal_w(1, 0);
        vector<string> rows(vis_depth + 1);
        render(1, 0, 0, rows);
        for (auto &s: rows) {
            while (!s.empty() && s.back() == ' ') s.pop_back();
            cerr << s << "\n";
        }
    }

    void cal_w(ll u, ll d) {
        vis_depth = max(vis_depth, d);
        if (infos[u].l == infos[u].r) {
            vis_w[u] = node_str(u).size();
            return;
        }
        cal_w(u << 1, d + 1);
        cal_w(u << 1 | 1, d + 1);
        vis_w[u] = vis_w[u << 1] + 3 + vis_w[u << 1 | 1];
    }

    void safe_put(string &row, ll col, char c) {
        if (col < 0) return;
        if (col >= (ll) row.size()) row.resize(col + 1, ' ');
        row[col] = c;
    }

    void render(ll u, ll sc, ll d, vector<string> &rows) {
        string label = node_str(u);
        if (infos[u].l == infos[u].r) {
            for (ll i = 0; i < (ll) label.size(); i++)
                safe_put(rows[d], sc + i, label[i]);
            return;
        }
        ll pipe = sc + vis_w[u << 1] + 1;
        ll labStart = max(pipe - (ll) label.size() / 2, (ll) 0);
        for (ll i = 0; i < (ll) label.size(); i++)
            safe_put(rows[d], labStart + i, label[i]);
        for (ll i = d + 1; i <= vis_depth; i++)
            safe_put(rows[i], pipe, '|');
        render(u << 1, sc, d + 1, rows);
        render(u << 1 | 1, sc + vis_w[u << 1] + 3, d + 1, rows);
    }
#endif
};


struct ODT {
    struct R_val {
        ll r;
        ll val;
    };

    map<ll, R_val> mp;

    // 用来初始化用的
    void insert(ll l, ll r, ll val) {
        mp[l] = {r, val};
    }

    void split(ll pos) {
        auto it = mp.upper_bound(pos);
        if (it == mp.begin()) return;
        --it;
        // l 这里肯定是 <=pos 的
        ll l = it->first;
        auto [r,val] = it->second;
        if (r < pos || l == pos) {
            return;
        }
        mp.erase(it);
        mp[l] = {pos - 1, val};
        mp[pos] = {r, val};
    }

    template<class F>
    void assign(ll l, ll r, ll val, F on_change) {
        // 这个顺序对于我们 mp 珂朵莉树实现无所谓
        split(r + 1);
        split(l);
        auto it = mp.lower_bound(l);
#ifdef LOCAL
        debug(l);
        debug(r);
#endif
        while (it != mp.end() && it->first <= r) {
            ll st = it->first;
            auto [ed,val] = it->second;
            // 具体怎么调用看你的 on_change() 实现，一般是一个全局操作
#ifdef LOCAL
            debug(val + st);
            debug(val + st + ed - st);
#endif
            on_change(val + st, val + st + ed - st, -1);
            it = mp.erase(it);
        }
        mp[l] = {r, val};
#ifdef LOCAL
        debug(val + l);
        debug(val + l + r - l);
#endif
        on_change(val + l, val + l + r - l, 1);
    }
};

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N + 2);
    vector<Info> info_ls(2 * N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        info_ls[A[i]].mx.cnt++;
        // info_ls[A[i]].mx.val = A[i];
    }
    for (int i = 1; i <= 2 * N; ++i) {
        info_ls[i].mx.val = i;
    }
    SEG seg(2 * N, info_ls);
    ODT odt;
    for (ll i = 1; i <= N;) {
        ll j = i;
        while (j < N && A[j] + 1 == A[j + 1]) {
            j++;
        }
        odt.insert(i, j, A[i] - i);
        i = j + 1;
    }
    Info res = seg.infos[1];
    cout << res.mx.val << " " << res.mx.cnt << "\n";
// #ifdef LOCAL
//     seg.visualize();
//     cend;
// #endif
    for (int _ = 1; _ <= M; ++_) {
        ll l, r, d;
        cin >> l >> r >> d;
        odt.assign(l, r, d - l, [&](ll val_l, ll val_r, ll add) {
            seg.modify(1, val_l, val_r, {add, true});
        });
#ifdef LOCAL
        // seg.visualize();
        cend;
#endif
        Info res = seg.infos[1];
        cout << res.mx.val << " " << res.mx.cnt << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/105941/submission/368114371

*/

starsilk 的代码

https://codeforces.com/gym/105941/submission/322881549

starsilk 的代码

#include <bits/stdc++.h>
using namespace std;
int a[200000];
struct dval{
	int r;
	int d;
};
map<int,dval>mp;
void split(int p){
	map<int,dval>::iterator it;
	dval dvl;
	it=mp.upper_bound(p);
	it--;
	if((*it).first==p)return;
	dvl.r=(*it).second.r;
	dvl.d=(*it).second.d+p-(*it).first;
	(*it).second.r=p;
	mp[p]=dvl;
}
struct dmax{
	int mx;
	int p;
};
dmax dm[1<<20];
int lazy[1<<20];
void gen(int t,int dep,int p){
	dm[t].mx=0;
	dm[t].p=p;
	lazy[t]=0;
	if(dep==0)return;
	gen(t*2+1,dep-1,p);
	gen(t*2+2,dep-1,p+(1<<(dep-1)));
}
void pushdown(int t){
	int l=t*2+1,r=t*2+2;
	lazy[l]+=lazy[t];
	lazy[r]+=lazy[t];
	dm[l].mx+=lazy[t];
	dm[r].mx+=lazy[t];
	lazy[t]=0;
}
dmax combine(dmax a,dmax b){
	if(a.mx<b.mx)swap(a,b);
	return a;
}
void add(int t,int dep,int l,int r,int vl){
	if(l==0&&r==(1<<dep))
	{
		dm[t].mx+=vl;
		lazy[t]+=vl;
		return;
	}
	pushdown(t);
	int x=(1<<(dep-1));
	if(l<x)
	{
		if(r<=x)add(t*2+1,dep-1,l,r,vl);
		else
		{
			add(t*2+1,dep-1,l,x,vl);
			add(t*2+2,dep-1,0,r-x,vl);
		}
	}
	else add(t*2+2,dep-1,l-x,r-x,vl);
	dm[t]=combine(dm[t*2+1],dm[t*2+2]);
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,q,i,l,r,d,tdep=0;
	dval dvl;
	map<int,dval>::iterator it;
	for(cin>>T;T>0;T--)
	{
		cin>>n>>q;
		for(;(1<<tdep)<n*2+5;tdep++);
		gen(0,tdep,0);
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			dvl.r=i+1;
			dvl.d=a[i];
			add(0,tdep,a[i],a[i]+1,1);
			mp[i]=dvl;
		}
		cout<<dm[0].p<<' '<<dm[0].mx<<'\n';
		for(;q>0;q--)
		{
			cin>>l>>r>>d;
			l--;
			split(l);
			if(r!=n)split(r);
			while(1)
			{
				it=mp.lower_bound(l);
				if(it==mp.end()||(*it).first>=r)break;
				add(0,tdep,(*it).second.d,(*it).second.d+(*it).second.r-(*it).first,-1);
				mp.erase(it);
			}
			dvl.r=r;
			dvl.d=d;
			add(0,tdep,d,d+r-l,1);
			mp[l]=dvl;
			cout<<dm[0].p<<' '<<dm[0].mx<<'\n';
		}
	}
	return 0;
}