小时候听说过珂朵莉树的大名,奈何当时没有专业知识看不懂。最近正好想起来了,来补上这个遗憾。
珂朵莉树(Chtholly Tree)又叫老司机树(ODT,Old Driver Tree)。多年前,一位用户 Old Driver 在通过本题 Willem, Chtholly and Seniorious 时给出了不同于线段树的暴力解法,也就是今天的 ODT。它以
s
e
t
set
set 为容器,使用
s
p
l
i
t
split
split 和
a
s
s
♂
i
g
n
ass♂ign
ass♂ign 两个核心函数,以及极其暴力的思想来实现。思路清晰简单,码量少(相对于线段树)。
不过珂朵莉树还是很容易卡掉的,在面对随机数据和优化一些东西的时候才比较不容易被卡。不过这个好写确实是好写,有时间可以看看 不会花太多时间的 。
珂朵莉树讲解
梦的开始 珂朵莉树板题
这个题由于是使用随机数据生成器来生成数据,所以数据和操作都是随机的,有
1
4
\frac14
41 的概率会将区间直接赋值为一个数,正好对应
a
s
s
i
g
n
assign
assign 函数可以把区间合并成一个点的功能,大大降低时间复杂度。因此可以使用珂朵莉树。
code:
三个注意点:
一:
val 定义时需要使用 mutable 来修饰,表示是可变的数据,不然一些版本会报错: [Error] assignment of member 'ODT::Node::val' in read-only object (我估计应该是)一些版本不允许迭代器直接修改参数值,也就是迭代器有 const 属性
二:
讲解的博客中也提到了,SIT it2=split(r+1),it1=split(l);中顺序不应改变,先 split(r+1),再 split(l)。否则如果
l
l
l 和
r
+
1
r+1
r+1 在同一个节点上,就会导致 split(l) 指向的节点被删掉,迭代器失效。
一般来说,如果删除的是set中迭代器指向的元素,那么这个迭代器将会失效。如果删除的是其他元素,通常来说,set中的其他迭代器应该保持有效。但是注意,进行容器修改操作后,所有迭代器都可能失效,迭代器失效通常与容器的结构变化有关。
三:
build() 函数中的 s.insert(Node(n+1,n+1,0)); 语句应当尽量写上。否则当 split(n+1) 的时候就会加入两个节点,范围分别是
[
l
,
n
]
,
[
n
+
1
,
n
]
[l,n],[n+1,n]
[l,n],[n+1,n]。
而且加入这个语句后,s.lower_bound() 一定不会访问到 s.end() 可以少写点判断代码。
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll n,m,seed,vm;
ll rnd(){
ll ret=seed;
seed=(7ll*seed+13)%1000000007ll;
return ret;
}
ll qpow(ll a,ll b,ll mod){
ll ans=1,base=a;
while(b){
if(b&1){
ans*=base;
ans%=mod;
}
base*=base;
base%=mod;
b>>=1;
}
return ans;
}
struct ODT{
#define SIT set
struct Node{
int l,r;
mutable ll val;
Node(int l,int r=-1,ll val=0):l(l),r(r),val(val){};
bool operator<(const Node x)const{
return l } }; set void build(int n){ for(int i=1;i<=n;i++) s.insert(Node(i,i,rnd()%vm+1)); s.insert(Node(n+1,n+1,0)); } SIT split(int pos){ SIT it=s.lower_bound(Node(pos)); if(it!=s.end() && it->l==pos){ return it; } it--; int l=it->l,r=it->r; ll val=it->val; s.erase(it); s.insert(Node(l,pos-1,val)); return s.insert(Node(pos,r,val)).first; } void assign(int l,int r,ll x){ SIT it2=split(r+1),it1=split(l); s.erase(it1,it2); s.insert(Node(l,r,x)); } void add(int l,int r,ll x){ SIT it2=split(r+1),it1=split(l); for(;it1!=it2;it1++) it1->val+=x; } ll rk(int l,int r,ll k){ SIT it2=split(r+1),it1=split(l); vector t.clear(); for(;it1!=it2;it1++) t.push_back(pair sort(t.begin(),t.end()); for(auto x:t){ if(x.second>=k)return x.first; else k-=x.second; } } ll pw(int l,int r,ll x,ll mod){ SIT it2=split(r+1),it1=split(l); ll ans=0; for(;it1!=it2;it1++){ ans=(ans+1ll*(it1->r-it1->l+1)*qpow(it1->val%mod,x,mod)%mod)%mod; } return ans; } void print(){ for(auto x:s){ printf("[%d,%d] val=%d\n",x.l,x.r,x.val); } puts(""); } #undef SIT }tr; int main(){ cin>>n>>m>>seed>>vm; tr.build(n); // tr.print(); for(int i=1;i<=m;i++){ ll 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()%vm+1; if(op==4)y=rnd()%vm+1; if(op==1){ tr.add(l,r,x); } else if(op==2){ tr.assign(l,r,x); } else if(op==3){ cout< } else { cout< } // tr.print(); } return 0; } 文章来源
发表评论