浅谈珂朵莉树
什么是珂朵莉树
珂朵莉树，又称\(Old Driver Tree(ODT)\)（老司机树）。
是一种基于\(set\)的暴力数据结构。
因此，再学习珂朵莉树之前，要掌握一些\(set\)和迭代器的知识
珂朵莉树的适用范围
线段树能干的它都能干（只要你不怕T）
使一整段区间内的东西变得一样，数据随机
比如下面这一道题
起源题：CF896C
题目描述
分析
如果只有前\(3\)个操作，那么别的数据结构似乎还可以使用
但是第\(4\)个操作是把区间中的每一个数拿出来进行运算
这样的操作其它数据结构很难胜任
这时我们就要用到珂朵莉树
定义
珂朵莉树是把连续的一段值相同的区间当作一个节点对待
因此节点定义如下
struct asd{
ll l,r;
//节点的左右端点
mutable ll val;
//节点的权值，如果不加mutable则在初始化后无法进行修改
bool operator < (const asd& A)const{
return l<A.l;
}
//按照左端点从小到大的顺序排序
asd(ll aa,ll bb,ll cc){
l=aa,r=bb,val=cc;
}
asd(ll aa){
l=aa;
}
};
核心操作 Split
这个操作的主要作用是将一个区间拆分开
比如我们要查询区间\([3,7]\)，但是\(3\)到\(7\)并不是一个节点，因此我们要把它们从原有的节点中拆分出来
#define sit set<asd>::iterator
首先，我们要宏定义\(set\)的迭代器
如果你不怕麻烦每次手打也可以
然后，我们再通过\(set\)建立一棵树
set<asd> s;
(set是C++自带的平衡树，这就是珂朵莉树是一棵树的原因）
最后是代码
sit Split(ll wz){
//返回值类型为迭代器
sit it=s.lower_bound(asd(wz));
//查找第一个左端点编号大于等于wz的节点
if(it!=s.end() && it->l==wz) return it;
//如果该节点的左端点是我们要分裂的节点，直接返回
it--;
//否则分裂上一个
ll l=it->l,r=it->r,val=it->val;
s.erase(it);
//将该节点拆分为两个
s.insert(asd(l,wz-1,val));
return s.insert(asd(wz,r,val)).first;
//返回分裂位置的迭代器
}
复杂度的保证Assign
将一个区间推平，赋成相同的值
void Assign(ll l,ll r,ll val){
sit it2=Split(r+1),it1=Split(l);
s.erase(it1,it2);
//删除区间[l,r+1)中所有的节点
s.insert(asd(l,r,val));
//插入新节点
}
其它操作
一个比一个暴力
区间加
把\([l,r]\)中的节点取出，分别加上就好了
这里有一个细节必须注意，必须先声明\(it2\)再声明\(it1\)
否则根据\(split\)中的\(erase\)操作，迭代器\(it1\)可能会失效。
（因为\(it1\)所属的节点可能被删除了）
void ad(ll l,ll r,ll val){
sit it2=Split(r+1),it1=Split(l);
for(sit it=it1;it!=it2;++it){
it->val+=val;
}
}
区间第k小
把\([l,r]\)中的节点取出,\(sort\)一下就行了
ll kth(ll l,ll r,ll k){
sit it2=Split(r+1),it1=Split(l);
vector<pair<ll,ll> >a;
a.clear();
for(sit it=it1;it!=it2;it++){
a.push_back(make_pair(it->val,it->r-it->l+1));
}
sort(a.begin(),a.end());
for(ll i=0;i<a.size();i++){
k-=a[i].second;
if(k<=0) return a[i].first;
}
}
区间幂次和
暴力维护+快速幂
ll ksm(ll ds,ll zs,ll mod){
ll now=ds%mod,ans=1;
while(zs){
if(zs&1) ans=ans*now%mod;
now=now*now%mod;
zs>>=1;
}
return ans%mod;
}
ll cx(ll l,ll r,ll x,ll y){
sit it2=Split(r+1),it1=Split(l);
ll ans=0;
for(sit it=it1;it!=it2;it++){
ans=(ans+(it->r-it->l+1)*ksm(it->val,x,y)%y)%y;
}
return ans;
}
完整代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sit set<asd>::iterator
const ll maxn=1e6+5;
struct asd{
ll l,r;
mutable ll val;
bool operator < (const asd& A)const{
return l<A.l;
}
asd(ll aa,ll bb,ll cc){
l=aa,r=bb,val=cc;
}
asd(ll aa){
l=aa;
}
};
set<asd> s;
sit Split(ll wz){
sit it=s.lower_bound(asd(wz));
if(it!=s.end() && it->l==wz) return it;
it--;
ll l=it->l,r=it->r,val=it->val;
s.erase(it);
s.insert(asd(l,wz-1,val));
return s.insert(asd(wz,r,val)).first;
}
void Assign(ll l,ll r,ll val){
sit it2=Split(r+1),it1=Split(l);
s.erase(it1,it2);
s.insert(asd(l,r,val));
}
void ad(ll l,ll r,ll val){
sit it2=Split(r+1),it1=Split(l);
for(sit it=it1;it!=it2;++it){
it->val+=val;
}
}
ll kth(ll l,ll r,ll k){
sit it2=Split(r+1),it1=Split(l);
vector<pair<ll,ll> >a;
a.clear();
for(sit it=it1;it!=it2;it++){
a.push_back(make_pair(it->val,it->r-it->l+1));
}
sort(a.begin(),a.end());
for(ll i=0;i<a.size();i++){
k-=a[i].second;
if(k<=0) return a[i].first;
}
}
ll ksm(ll ds,ll zs,ll mod){
ll now=ds%mod,ans=1;
while(zs){
if(zs&1) ans=ans*now%mod;
now=now*now%mod;
zs>>=1;
}
return ans%mod;
}
ll cx(ll l,ll r,ll x,ll y){
sit it2=Split(r+1),it1=Split(l);
ll ans=0;
for(sit it=it1;it!=it2;it++){
ans=(ans+(it->r-it->l+1)*ksm(it->val,x,y)%y)%y;
}
return ans;
}
ll n,m,mmax,seed;
ll rnd(){
ll ret=seed;
seed=(seed*7+13)%1000000007;
return ret;
}
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&seed,&mmax);
for(ll i=1;i<=n;i++){
ll aa=rnd()%mmax+1;
s.insert(asd(i,i,aa));
}
s.insert(asd(n+1,n+1,0));
for(ll i=1;i<=m;i++){
ll l,r,x,y;
ll 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()%mmax+1;
if(op==4) y=rnd()%mmax+1;
if(op==1) ad(l,r,x);
else if(op==2) Assign(l,r,x);
else if(op==3) printf("%lld\n",kth(l,r,x));
else printf("%lld\n",cx(l,r,x,y));
}
return 0;
}
复杂度证明
传送门
其它题目
CF343D Water Tree(珂朵莉树上树)
CF915E Physical Education Lessons（正解为动态开点线段树）
P4979 矿洞：坍塌
P1558 色板游戏
P3740 贴海报
P5350 序列
P1204 挤牛奶Milking Cows