算法竞赛模板

宝可梦图鉴

珂朵莉树 + 权值线段树
赛时想到了珂朵莉树的做法但是不知道这个板子
可惜了

一般的珂朵莉树，查询也是暴力遍历每个区间，因此有可能会被卡掉
这个做法结合了珂朵莉树的优点，由于查询是在权值线段树上的，所以不会被卡掉

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _ cout << "----------" << endl

struct node {
    int v, id;
    void apply(int val) {
        v += val;
    }
    node ():v(0),id(0) {}
    node operator+(const node& b) const {
        node tmp;
        if (v == b.v) {
            tmp.v = v;
            tmp.id = min(id,b.id);
        } else {
            if (v > b.v) {
                tmp.v = v;
                tmp.id = id;
            } else {
                tmp.v = b.v;
                tmp.id = b.id;
            }
        }
        return tmp;
    }
};

struct nd {
    int l, r;
    mutable ll d;
    nd(int _l, int _r,int _d): l(_l),r(_r),d(_d) {}
    bool operator< (const nd& b) const {
        return l < b.l;
    }
};


struct seg {
    int n;
    vector<node> tree;
    vector<int> tg;
    seg(int _n, vector<node>& b): n(_n) {
        tree.assign(4*n,node());
        tg.assign(4*n,0);
        build(1,n,1,b);
    } 
    
    void up(int p) {
        tree[p] = tree[p<<1] + tree[p<<1|1];
    }

    void build(int l, int r, int p, vector<node>& b) {
        if (l == r) {
            tree[p] = b[l];
            return;
        }
        int mid = l + r >> 1;
        build(l,mid,p<<1,b);
        build(mid+1,r,p<<1|1,b);
        up(p);
    }

    void apply(int p, int v) {
        tree[p].apply(v);
        tg[p] += v;
    }

    void down(int p) {
        apply(p<<1,tg[p]);
        apply(p<<1|1,tg[p]);
        tg[p] = 0;
    }

    void modify(int ml, int mr, int l, int r, int p, int v) {
        if (r < ml || l > mr) return;
        if (l >= ml && r <= mr) {
            apply(p,v);
            return;    
        } 
        down(p);
        int mid = l + r >> 1;
        modify(ml,mr,l,mid,p<<1,v);
        modify(ml,mr,mid+1,r,p<<1|1,v);
        up(p);
    }

    void modify(int l, int r, int v) {
        modify(l, r, 1, n, 1, v);
    }
    
    set<nd> s;

    auto split(int pos) {
        auto it = s.lower_bound(nd(pos,-1,0));
        if (it != s.end() && it->l == pos) return it;
        assert(it != s.end());
        it--;
        int l = it->l, r = it->r, d = it->d;
        s.erase(it);
        s.insert(nd(l, pos-1, d));
        return s.insert(nd(pos,r,d + pos - l)).first;
    }

    void assign(int l, int r, int x) {
        auto itr = split(r+1), itl = split(l);
        for (auto it = itl; it != itr; it++) {
            modify(it->d,it->d + it->r - it->l,-1);
        }
        s.erase(itl,itr);
        s.insert(nd(l,r,x));
        modify(x,x+r-l,1);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<node> a(2*n + 10);
    for (int i = 1; i <= 2*n + 5; i++) {
        a[i].id = i;
    }
    vector<int> b(n+10,0);
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        b[i] = v;
        a[v].v++;
    }

    seg tree(2*n + 5,a);
    tree.s.clear();
    for (int i = 1; i <= n; i++) {
        tree.s.insert(nd(i,i,b[i]));
    }
    tree.s.insert(nd(n + 1, n + 1,0));
    cout << tree.tree[1].id << " " << tree.tree[1].v << '\n';
    while (m--) {
        int l, r, d;
        cin >> l >> r >> d;
        tree.assign(l,r,d);
        cout << tree.tree[1].id << " " << tree.tree[1].v << '\n';
        // cout << tree.s.size() << endl;
        // for (auto tmp : tree.s) {
        //     cout << " ? "<< tmp.l << " " << tmp.r << " " << tmp.d << endl;
        // }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
       solve();
    }
    return 0;
} /* 2025-06-06 21:16 */