搜 索

珂朵莉树

  • 551阅读
  • 2020年08月06日
  • 1评论
首页 / 学习笔记 / 正文

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

友情提醒

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

无标签
评论区
摸鱼酱 2020年11月26日 17:11
回复

tql!

avatar