首页 📚学习笔记

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,那样的话就是数组了,没意义)
1710567-20200806192238802-69003481.png

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呢
1710567-20200806192347394-771988919.png
1710567-20200806192427811-1657051595.png
此时,我们分裂r:L-R,r就是mid,因为我们分裂是[L,mid-1]和[mid,R],所以分裂后就变成了
1710567-20200806192602391-1019955121.png
然后删除后返回的又是下一个区间[mid,R],删除的时候因为只会删除到前一个区间,所以最后就变成了这样
1710567-20200806192818332-56505395.png
这这这,明显不是我们想要的嘛,所以传入参数的时候要+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;
}

友情提醒

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




文章评论

    摸鱼酱 访客ChromeWindows
    2020-11-26 17:11   回复

    tql!

目录