珂朵莉树(Chtholly Tree)学习笔记

---

珂朵莉树原理

其原理在于运用一颗树（set，treap，splay......）其中要求所有元素有序，并且支持基本的操作（删除，添加，查找......）来实现区间压缩。

那么区间压缩的意义在于区间推平这是珂朵莉树的核心（如果没有这个操作实际上不一定需要这种算法）

可想而知它的操作在于对区间的分裂和合并操作

珂朵莉树的实现

在众多树中因为set这个c++自带，所以决定选择它。

结构

一个node结构体——把它叫区间(已typedef long long LL)

struct node

{

	int l,r;LL v;//这里官方写法加了一个mutable，看个人写法

	node(int L,int R,LL V):l(L),r(R),v(V){}

	bool operator < (const node& o) const

	{

		return l<o.l;

	}

};

声明集合

set<node>s;

初始化

for(int i=1;i<=n;++i)

    s.insert(i,i,val);

s.insert(n+1,n+1,0);//见下面中it!=s.end()的前提

分裂

#define it_ set<node>::iterator

it_ split(int pos)

{

	it_ it=s.lower_bound(node(pos));

	if(it!=s.end()&& it->l==pos) return it;

	--it;

	int ll=it->l,rr=it->r;

	LL vv=it->v;

	s.erase(it);

	s.insert(node(ll,pos-1,vv));

	return s.insert(node(pos,rr,vv)).first;

}

区间推平

void assign(int l,int r,LL val=0)

{

	it_ itl=split(l),itr=split(r+1);

	s.erase(itl,itr);

	s.insert(node(l,r,val));

}

如上。

---

栗例子

见cf896c

仅仅给出代码

#include <bits/stdc++.h>

#define it_ set<node>::iterator

// #define swap(X,Y) {int (tmp)=(X),(X)=(Y),(Y)=(tmp);}

using namespace std;

typedef long long LL;

const int M7=1e9+7;

const int maxn=1e5+5;

int n,m;

LL seed,vmax;

LL a[maxn];

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& o) const

	{

		return l<o.l;

	}

};

set<node>s;

it_ split(int pos)

{

	it_ it=s.lower_bound(node(pos));

	if(it!=s.end()&& it->l==pos) return it;

	--it;

	int ll=it->l,rr=it->r;

	LL vv=it->v;

	s.erase(it);

	s.insert(node(ll,pos-1,vv));

	return s.insert(node(pos,rr,vv)).first;

}

void assign(int l,int r,LL val=0)

{

	it_ itl=split(l),itr=split(r+1);

	s.erase(itl,itr);

	s.insert(node(l,r,val));

}

void add(int l,int r,LL val=0)

{

	it_ itl=split(l),itr=split(r+1);

	for(it_ i=itl;i!=itr;++i)

	{

		i->v+=val;

	}

}

LL so(int l,int r,int k)

{

	it_ itl=split(l),itr=split(r+1);

	vector<pair<LL,int>>v;

	v.clear();

	for(;itl!=itr;++itl)

	{

		v.push_back(pair<LL,int>(itl->v,itl->r-itl->l+1));

	}

	sort(v.begin(),v.end());

	for(vector<pair<LL,int>>::iterator it=v.begin();it!=v.end();++it)

	{

		k-=it->second;

		if(k<=0)return it->first;

	}

}

LL pow(LL a,LL b,LL mod)

{

	LL ret=1;a%=mod;

	while(b)

	{

		if(b&1) ret=ret*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return ret%mod;

}

LL ok(int l,int r,LL k,LL mod)

{

	it_ itl=split(l),itr=split(r+1);

	LL ans=0;

	for(;itl!=itr;++itl)

	{

		ans+=(LL)(itl->r-itl->l+1)*pow(itl->v,k,mod)%mod;

		ans%=mod;

	}

	return ans%mod;

}

LL rnd()

{

	LL ret=seed;

	seed=(seed*7+13)%M7;

	return ret;

}

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(0);

	cin>>n>>m>>seed>>vmax;

	for(int i=1;i<=n;++i)

	{

		a[i]=(rnd()%vmax)+1;

		s.insert(node(i,i,a[i]));

	}

	s.insert(node(n+1,n+1,0));

	for(int i=1;i<=m;++i)

	{

		int op=(rnd()%4)+1,

		l=(rnd()%n)+1,

		r=(rnd()%n)+1;LL x,y;

		if(l>r)

			swap(l,r);

		if(op==3)

			x=(rnd()%(LL)(r-l+1))+1;

		else

			x=(rnd()%vmax)+1;

		if(op==4)

			y=(rnd()%vmax)+1;

		if(op==1) add(l,r,x);

		else if(op==2) assign(l,r,x);

		else if(op==3) cout<<so(l,r,x)<<endl;

		else if(op==4) cout<<ok(l,r,x,y)<<endl;

	}

	return 0;

}