文章	评论	标签
21	9	6

ODT（Old Driver Tree，珂朵莉树）

名字挺奇怪的（指老司机树）

最开始起源于 CF896C，本来使用线段树做的，但是有一位大神用了一种我们从未见过的方法过掉了，所以我们就为这种方式命名了

至于为什么是树呢，因为它主要是 set，set 又是平衡树实现的，所以就假装他是树吧（虽然 set 有点慢，但你也可以自己手写二叉平衡树来优化）

前置知识

会用 STL 的 set，并且有手就行

核心思想

把数值相同的，相邻的数据合并在一起并存在 set 里，当然如果极端情况，不相邻的话，和数组差不多了

用途

解决有区间赋值的东西（因为这样相邻的相同的就比较多），并且数据随机的情况下（只要出题人想，你能 T 飞）时间复杂度比较可观

用 set 实现的珂朵莉树的复杂度为 O(NloglogN) ，而用链表实现的复杂度为 $O(N\log N)$。

以下以原题为例 CF896C Willem, Chtholly and Seniorious

具体实现

结点保存

因为我们有时候 set 里的值会改变（区间加法）但是 set 里面的值本来是无法改动的，所以我们引入了 mutable 就可以改动 set 的元素啦（就和 const 是反着来的）

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 &x)const{// 重载运算符 
        return l<x.l;
    }
};

当然，要加其他数据都可以

分裂

这里就是珂朵莉树的核心操作了（就是裂开）
因为当我们做操作的时候，左右结点很难都是正好落在连续区间的端点上，所以有时候我们必须得把它分成两个区间，然后方便集体做操作（不要说直接从 l 开始到 r，那样的话就是数组了，没意义）

IT split(int mid){// 从 mid 分开 
    IT it=s.lower_bound(node(mid));// 查找第一个大于等于的区间 
    if(it!=s.end()&&it->l==mid)return it;// 如果等于，说明正好落在端点上，就不用分裂 
    it--;// 否则，就是大于，所以在前一个区间 
    int l=it->l,r=it->r;
    ll v=it->v;
    s.erase(it);// 删除区间 
    s.insert(node(l,mid-1,v));// 分成两半 
    return s.insert(node(mid,r,v)).first;//set 的 insert 返回的是 pair，其中前一个代表当前的指针 
}

区间赋值

也是珂朵莉树的一大核心操作（你只分不合，set 分分钟 BOOM！！！）。还是那句话，左右端点不确定，所以先分裂

void assign(int L,int R,int v){IT r=split(R+1),l=split(L);// 分裂开 
    s.erase(l,r);// 区间删除，只会删除到 r - 1 的地方 
    s.insert(node(L,R,v));// 加入区间 
}

为什么传入的时候是 R + 1 呢


此时，我们分裂 r：L-R，r 就是 mid，因为我们分裂是 [L,mid-1] 和[mid,R]，所以分裂后就变成了

然后删除后返回的又是下一个区间 [mid,R]，删除的时候因为只会删除到前一个区间，所以最后就变成了这样

这这这，明显不是我们想要的嘛， 所以传入参数的时候要 +1
剩下的区间加啊，第 k 小啊，什么次方和啊，分分分，暴力就完事儿了

区间加法

void add(int L,int R,int v){IT r=split(R+1),l=split(L);// 分分分 
    for(;l!=r;l++)// 对于每一块的值加上去就行了（也就体现了 mutable） 
        l->v+=v;
}

区间第 k 小

ll kth(int L,int R,int k){IT r=split(R+1),l=split(L);// 分分分 
    vector<pair<ll,int> > v;// 排序暴力找就完事儿了 
    v.clear();
    for(;l!=r;l++)v.push_back(pair<ll,int>(l->v,l->r-l->l+1));
    sort(v.begin(),v.end());// 排个序 
    for(vector<pair<ll,int> >::iterator i=v.begin();i!=v.end();i++)// 暴力找 
    {
        k-=i->second;
        if(k<=0)return i->first;
     } 
     
}

Code

#include<bits/stdc++.h>
#define ll long long
#define IT set<node>::iterator
const int N=100010;
using namespace std;
int n,m,vmax;
int a[N];
ll seed;
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 &x)const{return l<x.l;}
};
set<node> s;
ll rnd(){
    ll ans=seed;
    seed=(seed*7+13)%1000000007;
    return ans;
}
ll qpow(ll x,ll y,ll p){
    x%=p;
    ll ans=1;
    while(y)
    {if(y&1)(ans*=x)%=p;
        y>>=1;
        (x*=x)%=p;
    }
    return ans;
}
IT split(int mid){IT it=s.lower_bound(node(mid));
    if(it!=s.end()&&it->l==mid)return it;
    it--;
    int l=it->l,r=it->r;
    ll v=it->v;
    s.erase(it);
    s.insert(node(l,mid-1,v));
    return s.insert(node(mid,r,v)).first;

}
void add(int L,int R,int v){IT r=split(R+1),l=split(L);
    for(;l!=r;l++)
        l->v+=v;
}
void assign(int L,int R,int v){IT r=split(R+1),l=split(L);
    s.erase(l,r);
    s.insert(node(L,R,v));
}
ll kth(int L,int R,int k){IT r=split(R+1),l=split(L);
    vector<pair<ll,int> > v;
    v.clear();
    for(;l!=r;l++)v.push_back(pair<ll,int>(l->v,l->r-l->l+1));
    sort(v.begin(),v.end());
    for(vector<pair<ll,int> >::iterator i=v.begin();i!=v.end();i++)
    {
        k-=i->second;
        if(k<=0)return i->first;
     }

}
ll sum(int L,int R,int x,int y){IT r=split(R+1),l=split(L);
    ll ans=0;
    for (;l!=r;l++)
        ans=((ans+(ll)(l->r-l->l+1)*qpow(l->v,(ll)x,(ll)y))%y+y)%y;
    return ans;
}
int main()
{scanf("%d%d%lld%d",&n,&m,&seed,&vmax);
    for(int i=1;i<=n;i++)a[i]=rnd()%vmax+1,s.insert(node(i,i,a[i]));
    while(m--)
    {
        int op,l,r,x,y;
        op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1;
        if(l>r)swap(l,r);
        if(op==3)x=rnd()%(r-l+1)+1;
        else x=rnd()%vmax+1;
        if(op==4)y=rnd()%vmax+1;

        switch(op)
        {
            case 1:{add(l,r,x);
                break;
            }
            case 2:{assign(l,r,x);
                break;
            }
            case 3:{cout<<kth(l,r,x)<<endl;
                break;
            }
            case 4:{cout<<sum(l,r,x,y)<<endl;
                break;
            }
        }
    }
    return 0;
}

友情提醒

实在想不出来正解了，才用珂朵莉树骗骗分，一般情况下还是正解。但珂朵莉树代码短，调试方便，不得不吹，实乃骗分利器！

珂朵莉树

华恋