珂朵莉树学习笔记

tallnut · 2025-03-07 22:08:50 · 算法·理论

你猜我为什么要学珂朵莉树？因为我省选 D2T1 被创死了。~~不过把我创死的题又何止这一道呢。~~

算法介绍

用途

珂朵莉树，又名 ODT，是一种暴力数据结构，在数据随机的情况下，可以以正确的复杂度解决区间推平（即将一段区间全部变为一个数，并且支持其他诡异的操作）问题。只要理解了算法思想，具有代码实现难度极低（比线段树之类好写得多）且容易学习等优点。

~~不过考虑到现在官方赛事出题人大多脚造数据，珂朵莉树即使复杂度不对也可能骗很多分。~~

暴力数据结构几乎都有一种共同点：复杂度可能不够优，但通用性很强。

具体介绍

珂朵莉树本质是将同一颜色段压缩成一个区间，扔进 set 里高效维护。

结构定义

以下是常见的珂朵莉树写法：

struct node
{
    int l;
    int r;
    mutable int val;
    bool operator<(const node& xx) const { return l < xx.l; }
};
set<node> st;

表示一个区间为 [l,r]，区间内所有数的值均为 val。

初始化

把第 i 个点视为一个 [i,i] 的区间，把所有点装进 set 里面。

for (int i = 1;i <= n;i++)
    st.insert({i,i,a[i].a});

非常容易实现。

核心操作：`split` & `assign`

通过将区间分裂为 [l,pos-1] 和 [pos,r] 并重新组合，实现高效推平操作。

带有详细注释的 split:

set<node>::iterator split(int pos)
{
    set<node>::iterator it = s.lower_bound({pos,0,0});
    //如果这本身就是区间开头，就不用切割了
    if (it != s.end() && it->l == pos)
        return it;
    //先往前移一格
    it--;
    //pos太大了
    if (it->r < pos)
        return s.end();
    //删除区间，插入两个新区间
    ll l = it->l;
    ll r = it->r;
    ll v = it->v;
    s.erase(it);
    s.insert({l,pos - 1,v)});
    //可以借此学习一下 insert 的特殊用法
    return s.insert({pos,r,v}).first;
}

assign 操作可以说和 split 相反，将多个区间删除，合并成一个推平过的区间，实现很简单：

void assign(ll l,ll r,ll x)
{
    set<Node>::iterator itr = split(r + 1);
    set<Node>::iterator itl = split(l);
    s.erase(itl,itr);
    s.insert({l,r,x});
}

其他操作

直接暴力解决。按照要求取出对应区间然后暴力操作即可。

例题

CF896C

珂朵莉树模板题，也是珂朵莉树的起源。

按照上面的思路，除了推平外其余都暴力暴力暴力就完了。代码就不放了。

P11833

没错省选题也能用珂朵莉树做~~并且还是 ABC 原题~~。

结论：按照 t_i 从小到大贪心处理，中间遇上箱子就推着一起走。因为 a_i,b_i 均单调递增可以证明。

注意到推着一起走相当于把所有箱子都推到终点，是推平操作。于是可以珂朵莉树做。

因为查询区间与操作区间总是相同，复杂度可以得到保证。

完整代码：

#include <bits/stdc++.h>
#define int long long
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
using namespace std;
const int N = 2e5 + 10;
int n,ans;
struct xxx
{
    int a;
    int b;
    int t;
    int id;
    bool operator<(const xxx& xx) { return t < xx.t; }
} a[N];
class odt
{
    struct node
    {
        int l;
        int r;
        mutable int val;
        bool operator<(const node& xx) const { return l < xx.l; }
    };
    set<node> st;
    public:
        void init()
        {
            st.clear();
            rep1(i,1,n)
                st.insert({i,i,a[i].a});
        }
        void modify(int i)
        {
            int id = a[i].id;
            auto p = st.upper_bound({id,-1,-1});
            p--;
            int l0 = p->l;
            int r0 = p->r;
            int val0 = p->val;
            if (a[i].a < a[i].b)
            {
                if (l0 != id)
                {
                    st.erase(p);
                    st.insert({l0,id - 1,val0});
                    p = st.insert({id,r0,val0}).first;
                }
                auto p2 = p;
                int sum = 0;
                int rpos = id - 1;
                while (p2 != st.end() && p2->val < a[i].b)
                {
                    sum += (p2->r - p2->l + 1) * p2->val;
                    rpos = p2->r;
                    p2++;
                }
                st.erase(p,p2);
                st.insert({id,rpos,a[i].b});
                ans += (rpos - id + 1) * a[i].b - sum;
            }
            else
            {
                if (r0 != id)
                {
                    st.erase(p);
                    st.insert({id + 1,r0,val0});
                    p = st.insert({l0,id,val0}).first;
                }
                auto p2 = p;
                int sum = 0;
                int lpos = id + 1;
                while (p2->val > a[i].b)
                {
                    sum += (p2->r - p2->l + 1) * p2->val;
                    lpos = p2->l;
                    if (p2 == st.begin())
                        break;
                    p2--;
                }
                auto beg = st.upper_bound({lpos,-1,-1});
                beg--;
                p++;
                st.erase(beg,p);
                st.insert({lpos,id,a[i].b});
                ans += sum - (id - lpos + 1) * a[i].b;
            }
        }
} tree;
void solve()
{
    ans = 0;
    cin >> n;
    rep1(i,1,n)
    {
        cin >> a[i].a >> a[i].b >> a[i].t;
        a[i].a -= i;
        a[i].b -= i;
        a[i].id = i;
    }
    tree.init();
    sort(a + 1,a + n + 1);
    rep1(i,1,n)
    {
        tree.modify(i);
        if (ans > a[i].t)
        {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t >> t;
    while (t--)
        solve();
}