貌似珂朵莉树是目前为止(我学过的)唯一一个可以维护区间x次方和查询的高效数据结构。

但是这玩意有个很大的毛病,就是它的高效建立在数据随机的前提下。

在数据随机的时候assign操作比较多,所以它的复杂度会趋近于mlogn(m为询问次数)。假如出题人想要卡珂朵莉树的话,那肯定是会T得没边。

因此不要指望什么题目都套珂朵莉树(虽然它能水过很多数据结构题),特别是在数据非随机的情况下不要使用。

当然,如果题目让你求区间x次方和而在题目条件下你想不出巧算,那写一颗珂朵莉树还是很OK的。


不得不说珂朵莉树的博客我也看了很多篇了,大家却一笔带过(可能是我太弱了)细节只讲大致框架,而某大佬在B站上的视频讲解被某不知名的管理员noip大佬喷了所以没敢去看,只好一个人颓代码。

我讲的也不一定多标准,有什么错误麻烦各位指正。

另:不太熟悉set的可以参考这篇博客


珂朵莉树的核心操作在于推平一个区间。

(貌似每篇博客都说这句话)

当然事实上珂朵莉树是将所有要操作的区间整合到一起去做的,实现也可以不依赖set,比如自己写一颗fhq Treap之类的。

先讲一下大体思路:

可以发现,这里面有一个操作是推平一整段区间。

因此我们让每一个节点维护一个区间,然后对于2号操作清空区间[l,r]里的所有区间,用一个大区间[l,r]取代他们。

对于1,3,4号操作,我们暴力地找到每一个[l,r]里面的区间,然后对它们各个进行操作。

时间复杂度的证明可以参考发明者的原话:传送门(注意是第五条)


珂朵莉树的节点是这样定义的:

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。


有了基本的节点之后,通过set建立一棵树。

(set是C++自带的平衡树,但是慢到一种境界。只有在刷时限给力的题目时推荐)

set<node> s;

然后是很核心的split操作,这个操作如同它的名字,将一个区间拆分开来。

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

IT代表的玩意建议用宏,手打可以让你怀疑人生。

第一行使用了lower_bound,这个函数的作用是求前驱。

然后我们先看是否需要split这个区间,如果不需要就直接返回it。

假如现在程序还在运行,那说明我们需要split。

因此pos肯定在上一个区间里(显然),那我们把前一个彻底抹掉,然后再插入两段区间。

现在看来我们什么事情都没有做,删掉了区间又把它放回来了。

注意,其实我们并不是什么事情都没有做,因为我们在这个过程中已经拿到了需要的东西:后半段区间的迭代器(什么用后面说)

最后的返回语句可能比较玄学,事实上,set的insert操作返回一个<iterator,bool>的pair,我们只拿走第一个。

split操作就这样结束了,它的复杂度应该是log级的(set通过红黑树实现,而那玩意(我没写过)的操作据说是近似logn的)。


同样核心的assign操作,是将一个区间的每一个值都设为一个值。

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

val默认为0(因为很多时候我们直接推平)。

首先我们拿到itl和itr,这两个东西分别是split(l)与split(r+1)的返回值,看起来可能不太好理解,但是画个图似乎挺明了的。

丑陋的配图

然后我们把中间的都删除(这是erase的另一种用法,删除区间内的所有元素),用一个大区间代替所有小区间。

没了,时间复杂度很能接受。


add操作,给区间每个数加上val。

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

像我们之前说的那样,对于[l,r]内的所有小区间,暴力遍历一遍,给他们每一个都加上val。

可能有人会问:不会有加重复或者漏加的情况吗?

事实上不会。

漏加这个很明显是没有的,而重复加之所以没有是因为

  1. 最开始没有重复。

  2. 每一次推平不会产生重复。


接下来是求区间k小值。

ll rank(int l,int r,int k){
    vector<pair<ll,int> >vp;vp.clear();
    IT itl=split(l),itr=split(r+1);
    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;
}

我们采取类似的思路:把[l,r]里面的所有元素取出来,扔到一个vector里面去。

然后给这个vector排个序。

便利一遍就可以找到最小值了。

最后的return -1ll;是特判找不到的情况,当然本题保证找得到。


最后一个操作是区间x次方和,这个也十分暴力:

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

对于[l,r]每一个元素都暴力x次方,这个过程通过快速幂实现。


然后珂朵莉树的操作基本就完了。

有人问我为什么代码都这么一样。

我也很无奈啊,只能说我学习的那篇博客和大家重复了qwq。