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

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;
}

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