【毒瘤Warning】Chtholly Tree珂朵莉树详解

2018-07-24 17:34:34


本文被yfz批判,正在修改

一、什么是珂朵莉树

珂朵莉树,又称Old Driver Tree(ODT)。是一种某毒瘤发明的、常基于std::set实现的算法。

二、什么时候用珂朵莉树

关键操作:推平一段区间,使一整段区间内的东西变得一样,另有一些奇奇怪怪的查询。要求复杂度$m\log n$,保证数据随机

ODT起源:CF896C Willem, Chtholly and Seniorious

$n$个数,$m$次操作$(n,m\leq10^5)$。

操作:

  1. 区间加
  2. 区间赋值
  3. 区间第k小
  4. 求区间幂次和

数据随机,时限2s。

当然了,遇到一道区间推平、线段树可做、数据不保证随机的题时,你如果觉得线段树代码量巨大,害怕写挂,也可以选择ODT来骗分。之所以说是骗分,是因为如果使用std::set维护ODT,在非随机数据下,其复杂度可能是不对的。只有使用线段树辅助维护,才可以获得正确的复杂度。在出题人没有认真造数据的情况下有奇效。本文最后给出的几道练习题表明,目前几乎没有出题人有意卡掉珂朵莉树。

三、珂朵莉树的初始化

一般来说,珂朵莉树可以用线段树或平衡树维护。我们用std::set维护每个包含的数相同的区间。这道题里,这样定义珂朵莉树的节点:

struct node
{
    int l,r;
    mutable LL v;
    node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const
    {
        return l < o.l;
    }
};

这样的一个节点表示$[l,r]$内的所有数都是$v$,ODT的本质就是把区间缩成点,std::set维护的ODT,可以视为一棵缩点后的平衡树。需要注意的是mutable,意为易变的,不定的。它对v的修饰,使得我们可以在add操作中修改v的值。没有它的修饰会在add函数里导致CE。

我们把节点存在set里。

set<node> s;

像CF896C这道题就这样初始化。

cin>>n>>m>>seed>>vmax;
for (int i=1; i<=n; ++i)
{
    a[i] = (rnd() % vmax) + 1;
    s.insert(node(i,i,a[i]));
}

初始化完了?初始化完了。

四、核心操作1:split

split(pos)操作是指将原来含有pos位置的节点分成两部分:$[l,pos-1]$和$[pos,r]$。

看这个操作的代码:

#define IT set<node>::iterator
IT split(int pos)
{
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    LL V = it->v;
    s.erase(it);
    s.insert(node(L, pos-1, V));
    return s.insert(node(pos, R, V)).first;
}

这都什么啊?看不懂啊。我们一行一行来看。

#define IT set<node>::iterator

宏定义没什么好说的。

IT it = s.lower_bound(node(pos));

找到首个$l$不小于pos的节点。

if (it != s.end() && it->l == pos)
    return it;

如果pos是某个节点的左端点,直接返回该节点。

--it;

否则pos一定在前一个区间中。

int L = it->l, R = it->r;

$[L,R]$就是要被分割的区间。

LL V = it->v;

取出这个节点的值。

s.erase(it);

删除原节点。

s.insert(node(L, pos-1, V));

插入前半段。

return s.insert(node(pos, R, V)).first;

插入后半段,返回后半段的迭代器。这里利用了pair<iterator,bool> insert (const value_type& val)的返回值。

五、核心操作2:assign

要是只有split还不得复杂度爆炸?我们需要assign操作迅速减小set的规模。

void assign(int l, int r, LL val=0)
{
    IT itr = split(r+1),itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}

把$l$和$r+1$进行split,再把$[l,r]$合成一个节点。为什么要先split出r+1呢?因为如果先split出l,再split出r+1,之前的itl可能就不是l对应的迭代器了。void erase (iterator first, iterator last)可删除$[first,last)$区间。这里就是把$[l,r+1)$内的部分推成一段。

珂朵莉树的复杂度是由assign保证的。由于例题数据随机,有$\frac{1}{4}$的操作为assign。我们还可以证明,每次assign的区间的期望大小为$\frac{n}{3}$。(初赛竟然考了诶)

set的大小快速下降,使得珂朵莉树在随机数据下的时间复杂度为期望$m\log n$。复杂度证明:http://codeforces.com/blog/entry/56135?#comment-398940

注意:珂朵莉树的时间复杂度在非随机数据下是错误的,只能用于骗分,不是正解。

六、其他操作:set里走路

区间加:

void add(int l, int r, LL val=1)
{
    IT itr = split(r+1),itl = split(l);
    for (; itl != itr; ++itl) itl->v += val;
}

split出来挨个加一下就行。

区间第k小:

LL rank(int l, int r, int k)
{
    vector<pair<LL, int> > vp;
    IT itr = split(r+1),itl = split(l);
    vp.clear();
    for (; itl != itr; ++itl)
        vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1));
    sort(vp.begin(), vp.end());
    for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)
    {
        k -= it->second;
        if (k <= 0) return it->first;
    }
    return -1LL;
}

暴力取出排序就好了,反正也没有多少段。

LL sum(int l, int r, int ex, int mod)
{
    IT itr = split(r+1),itl = split(l);
    LL res = 0;
    for (; itl != itr; ++itl)
        res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod;
    return res;
}

暴力遍历,快速幂,然后加起来。

那么,这道题就可做了,快写一发试试吧!

七、ODT如何应付非随机数据

例题:USACO08FEB 酒店Hotel

区间赋值,区间填补,这不是傻逼ODT题吗,赶快写一发!

布星啊,这第二组数据的区间填补长度都不超过10,ODT内这么多区间,复杂度退化了啊!

其实还是有办法的。复杂度之所以不对,是因为在set中的暴力for。如果改成用线段树维护ODT,批量对区间操作,复杂度就正确了。而且我们可以想象到,它的速度会大大快于标算。

看到这里,也许读者会有疑虑:我为什么不直接写个线段树呢?

这道题并没有完全体现ODT的代码优越性。我选出这道题只是单纯地因为它的官方数据可以卡掉set。对于不少题目,用线段树就需要维护繁多的标记,处理复杂的下放与上传。而ODT完全不需要这些。

八、更广泛的应用:骗分的有力武器

由于CF896C这种毒瘤题目只会在ynoi级别的题目中出现,珂朵莉树更多地被用于骗分。

UESTC的B站讲解(不用找了,这段视频已被lxl,yfz,mcfx,zcy所批判)里还有另两道题,一道是CF915E,另一道是BZOJ4293割草(权限题)。值得注意的是,在这两道题中使用ODT,由于数据不随机,视频中代码的复杂度是错误的。这两道题的主流做法都是线段树,珂朵莉树也可达到骗分的目的。但珂朵莉树仍能体现出代码复杂度较小、易查错、高效骗分的优势。CF915E的评测记录: https://www.luogu.org/record/show?rid=11431273

数据结构需要摸索,需要练习。否则就算是在考场上看到了珂朵莉树可骗分的题,也会被水淹没,也会不知所措。洛谷题库里还有不少珂朵莉树骗分的练手题,都有珂朵莉树的骗分题解:

void sort_range(int l,int r)
{
    int cnt[27];
    memset(cnt,0,sizeof(cnt));
    IT itr=split(r+1),itl=split(l);
    for(IT itl2=itl;itl2!=itr;++itl2)
    {
        cnt[itl2->v-'A']+=itl2->r-itl2->l+1;
    }
    s.erase(itl,itr);
    int pos=l;
    for(int i=0;i<26;++i)
    {
        if(cnt[i])
        {
            s.insert(node(pos,pos+cnt[i]-1,i+'A'));
            pos+=cnt[i];
        }
    }
}
int count_erase(int l,int r)
{
    int res=0;
    IT itr=split(r+1),itl=split(l);
    for(IT itl2=itl;itl2!=itr;++itl2)
    {
        if(itl2->v==true)
        {
            res+=itl2->r-itl2->l+1;
        }
    }
    s.erase(itl,itr);
    s.insert(node(l,r,false));
    return res;
}

void fix(int l,int r,int cnt)
{
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        if(itl->v==false)
        {
            if(itl->r-itl->l+1>=cnt)
            {
                if(itl->r-itl->l+1>cnt)
                {
                    int lrange=itl->l,rrange=itl->r;
                    s.erase(itl);
                    s.insert(node(lrange,lrange+cnt-1,true));
                    s.insert(node(lrange+cnt,rrange,false));
                }
                else
                {
                    itl->v=true;
                }
                return;
            }
            else
            {
                itl->v=true;
                cnt-=itl->r-itl->l+1;
            }
        }
    }
}

void recover(int l1,int r1,int l2,int r2)
{
    int cnt=count_erase(l1,r1);
    if(!cnt)
        return;
    fix(l2,r2,cnt);
}
typedef node Ret;
//直接把node的定义拿来用,l表示左端颜色,r表示右端颜色,v表示颜色段数
Ret operator + (Ret l,Ret r)
{
    return Ret(l.l?l.l:r.l,r.r?r.r:l.r,l.v+r.v-(l.r==r.l));
}
//重载运算符便于合并

Ret query(int l,int r)
{
    Ret ans=Ret(0);
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        ans=ans+Ret(itl->v,itl->v,1);
    }
    return ans;
}

int qRange(int x,int y)
{
    Ret lans=Ret(0),rans=Ret(0);
    //lans表示x一侧的答案,rans表示y一侧的答案。
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            lans=query(id[top[x]],id[x])+lans;
            x=fa[top[x]];
        }
        else
        {
            rans=query(id[top[y]],id[y])+rans;
            y=fa[top[y]];
        }
    }
    if(dep[x]>dep[y])
    {
        lans=query(id[y],id[x])+lans;
    }
    else
    {
        rans=query(id[x],id[y])+rans;
    }
    std::swap(lans.l,lans.r);
    //lans倒过来再加上rans
    return (lans+rans).v;
}

与染色一题大体相同,记录一下rotate和flip的情况,像染色一样去搞即可。

注意:以上题目中珂朵莉树都只是骗分手段,尽管可以依靠以上代码获得AC,但由于数据不是完全随机的,其复杂度都是错误的。

笔者在暑期的一场测试中使用过一次ODT,特判了出锅的数据后(这个锅不会影响到正常写法的线段树和分块,但会导致用std::set实现的珂朵莉树RE成60pts),成功骗得了88分,在时限开到2秒后可以获得96分,第22号测试点足足用了15秒,想必是出题人有意构造,卡掉骗分做法的。该题的大意是对一个初始为空集的数集做交、并、减、异或等操作。不难发现这些操作大部分可以用split和assign完成,小部分可以暴力解决。在该场比赛中,分块的分数多为76分,线段树的分数为96~100分。而ODT的代码量远小于分块和线段树(线段树标记越多越明显),为我解决同一场考试中的其他题目争取了时间。

九、结语(雾)

lxl是启明星,lxl是航标灯。如今,毒瘤数据结构已在lxl的领导下进入了深水区,表面海阔天空,却也暗潮涌动;看似河清海晏,实则泥沙俱下。一方面,信息学竞赛中的毒瘤日新月异;另一方面,骗分手段也是道高一尺,魔高一丈。9年前,李博杰的《骗分导论》横空出世,为OI界的骗分指明了方向。9年过去了,如今的骗分,已远非是当年一本区区200余页的骗分导论说得清,道得明的。珂朵莉树就是毒瘤正解在骗分之林中初绽的一朵奇葩,助我们在时间复杂度和代码复杂度间找到最好的平衡。珂朵莉树是潜移默化的,珂朵莉树是润物无声的。有暴力骗分武装头脑,珂朵莉树指导实践,就没有翻不过的山、迈不过的坎,就可以获得更加可观的暴力分。如果出版新的骗分导论,珂朵莉树必然是其中最值得学习的骗分技巧之一。这是广大OIer坚定的信念、共同的心声。

——洛谷人民日报(大雾)