珂朵莉树

珂朵莉树（老司机树/ODT）是一种由李欣隆发明的暴力数据结构，在随机数据下表现良好。珂朵莉树主要用于有着大量区间推平操作的题目，但是在构造数据下表现十分不好。如果区间推平操作较多，则单一操作的时间复杂度为 \(O(\log_2n)\)。在特殊构造下，单一操作则会退化成 \(O(n\log^2_2n)\)。

前置芝士

set 的应用。懂得 set 的迭代器用法。

做法

首先珂朵莉树的前提条件就是基于推平操作。也就是将 \([l,r]\) 全部修改成 \(x\)。所以最终整个序列会变成一个一个段，每个段的元素值均为 \(x\)。我们要做的就是维护这个东西。

所以我们首先要定义一个结构体，里面存 \(l,r,x\)。代表区间 \([l,r]\) 内的元素均为 \(x\)。注意，\(x\) 在实际定义时需要加上 mutable 前缀，只有这样我们才能够直接在之后定义的 set 里修改 \(x\)。

之后我们考虑怎么维护这个珂朵莉树。首先定义一个set来存这些区间，因为set 内部有排序功能所以区间是有连续性的，方便我们进行修改。

struct node{
    ll l,r;
    mutable ll x;
    node(ll _l,ll _r=0,ll _x=true){
        l=_l;
        r=_r;
        x=_x;
    }
    bool operator<(const node&K)const{
        return l<K.l;
    }
};
set<node>odt;

然后我们考虑一个分离操作 \(f(x)\) 代表把一个区间范围包含了 \(x\) 的区间分成 \([l,x-1]\) 和 \([x,r]\)。这是因为实际操作时的询问不一定完全包含一个元素相同的区间，可能一个经过了修改还有一个是没有经过修改的，所以要分割。

auto split(ll x){
    auto num=odt.lower_bound(node(x));
    if(num!=odt.end()&&num->l==x){
        return num;//如果 x 已经是一个区间的左端点了则直接返回这个区间。
    }
    num--;//否则 x 一定被上一个区间包含（除了下面这种情况）
    if(num->r<x){
        return odt.end();//如果 x 超过了全部的区间，则 [x,r] 不存在
    }
    ll l=num->l,r=num->r;
    ll X=num->x;
    odt.erase(num);
    odt.insert(node(l,x-1,X));
    return odt.insert(node(x,r,X)).first;//返回 [x,r] 的迭代器
}

之后是推平操作的实现。

void assign(ll l,ll r,bool work){
    auto itr= split(r+1),itl= split(l);//注意这里要先分割 r+1，否则可能 re
    odt.erase(itl,itr);//删除原范围里面的所有段
    odt.insert(node(l,r,work));//添加一个完整的新区间
}

之后所有的操作我们都做类似这样的处理：

void op(ll l,ll r,给定其他参数){
    auto itr= split(r+1),itl= split(l);
    while(itl!=itr){
        暴力执行要求操作
        itl++;
    }
}

这样子珂朵莉树就完成了。考虑到区间推平操作在随机数据下一定是范围大且数量算多的，所以这样的随机数据可以让set里面的元素数量不会很多。这样可以感性理解。具体的证明可以看这里。

例题

CF915E Physical Education Lessons

题目大意

对于一个长度为 \(n\) 且只含 \(0\) 或 \(1\) 的数组 \(a\)（初始全为 \(1\)），有 \(q\) 次操作，每次操作有两种：

• \(1,l,r\) 时将 \([l,r]\) 全部变为 \(0\)。
• \(2,l,r\) 时将 \([l,r]\) 全部变为 \(1\)。

对于每一个操作输出 \(a\) 还有几个 \(1\)。
\(1\leq n\leq 10^9,1\leq q\leq3\cdot 10^5\)
\(1\leq l,r\leq n\)

解法

首先因为本题只含有区间推平操作，所以可以使用珂朵莉树。
首先推平操作就是模版，具体对于几个 \(1\) 的维护可以在推平操作中直接枚举段落，然后如果此段的 \(x=1\)，则答案加上 \(r-l+1\) 即可。

代码

#include <iostream>
#include <set>
using namespace std;
typedef long long ll;
struct node {
	ll l,r;
	mutable bool work;
	node(ll _l,ll _r=0,bool _work=true) {
		l=_l;
		r=_r;
		work=_work;
	}
	bool operator<(const node&K)const {
		return l<K.l;
	}
}
;
set<node>odt;
auto split(ll x) {
	auto num=odt.lower_bound(node(x));
	if(num!=odt.end()&&num->l==x) {
		return num;
	}
	num--;
	if(num->r<x) {
		return odt.end();
	}
	ll l=num->l,r=num->r;
	bool work=num->work;
	odt.erase(num);
	odt.insert(node(l,x-1,work));
	return odt.insert(node(x,r,work)).first;
}
ll ans=0;
void assign(ll l,ll r,bool work) {
	auto itr= split(r+1),itl= split(l);
	auto it=itl;
	while(it!=itr) {
		if(it->work) {
			ans-=(it->r-it->l+1);
		}
		it++;
	}
	odt.erase(itl,itr);
	odt.insert(node(l,r,work));
	if(work) {
		ans+=r-l+1;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	ll n,q;
	cin>>n;
	cin>>q;
	ans=n;
	odt.insert(node(1,n,true));
	while(q--) {
		ll l,r,k;
		cin>>l>>r>>k;
		assign(l,r,k!=1);
		cout<<ans<<"\n";
	}
	return 0;
}

CF896C Willem, Chtholly and Seniorious

这是珂朵莉树最开始的起源，但是具体做法也差不多一样。

题目大意

有一个长度为 \(n\) 的序列，请你写一种数据结构，共有 \(m\) 次操作，每一次操作你需要支持：

• \(1\) \(l\) \(r\) \(x\) ：将\([l,r]\) 区间所有数加上\(x\)
• \(2\) \(l\) \(r\) \(x\) ：将\([l,r]\) 区间所有数改成\(x\)
• \(3\) \(l\) \(r\) \(x\) ：输出将\([l,r]\) 区间从小到大排序后的第\(x\) 个数是的多少(即区间第\(x\) 小，数字大小相同算多次，保证 \(1\leq\) \(x\) \(\leq\) \(r-l+1\) )
• \(4\) \(l\) \(r\) \(x\) \(y\) ：输出\([l,r]\) 区间每个数字的\(x\) 次方的和模\(y\) 的值(即(\(\sum^r_{i=l}a_i^x\) ) \(\mod y\) )

保证数据随机生成
\(1\leq n,m\leq10^5,1\leq x,y\leq 10^9\)。
\(1\leq l,r\leq n\)

思路

对于第一种操作，我们直接枚举区间并加即可。

void op1(ll l,ll r,ll x) {
	auto itr= split(r+1),itl= split(l);
	while(itl!=itr) {
		itl->x+=x;
		itl++;
	}
}

第二种操作暴力推平即可。

第三种操作我们考虑把所有 \([l,r]\) 内的区间都存下来，然后排序并累计个数即可。

pair<ll,ll>num[MAXN];
ll op3(ll l,ll r,ll x) {
	auto itr= split(r+1),itl= split(l);
	ll sz=0;
	while(itl!=itr) {
		num[++sz]= {
			itl->x,itl->r-itl->l+1
		}
		;
		itl++;
	}
	sort(num+1,num+sz+1);
	ll v=0;
	while(x>0) {
		++v;
		x-=num[v].second;
	}
	return num[v].first;
}

第四种就快速幂直接乘跟加即可。但是注意快速幂的底数要取模 ，否则会溢出。

ll op4(ll l,ll r,ll x,ll y) {
	ll ans=0;
	auto itr= split(r+1),itl= split(l);
	while(itl!=itr) {
		ll val=ksm(itl->x,x,y);
		val=val*((itl->r-itl->l+1)%y);
		val%=y;
		ans=(ans+val)%y;
		itl++;
	}
	return ans;
}

代码

#include <iostream>
#include <algorithm>
#include <set>
#define int long long
using namespace std;
typedef long long ll;
struct node {
	ll l,r;
	mutable ll x;
	node(ll _l,ll _r=0,ll _x=true) {
		l=_l;
		r=_r;
		x=_x;
	}
	bool operator<(const node&K)const {
		return l<K.l;
	}
}
;
set<node>odt;
auto split(ll x) {
	auto num=odt.lower_bound(node(x));
	if(num!=odt.end()&&num->l==x) {
		return num;
	}
	num--;
	if(num->r<x) {
		return odt.end();
	}
	ll l=num->l,r=num->r;
	ll X=num->x;
	odt.erase(num);
	odt.insert(node(l,x-1,X));
	return odt.insert(node(x,r,X)).first;
}
void op2(ll l,ll r,ll X) {
	auto itr= split(r+1),itl= split(l);
	odt.erase(itl,itr);
	odt.insert(node(l,r,X));
}
void op1(ll l,ll r,ll x) {
	auto itr= split(r+1),itl= split(l);
	while(itl!=itr) {
		itl->x+=x;
		itl++;
	}
}
const ll MAXN=1e5+5;
pair<ll,ll>num[MAXN];
ll op3(ll l,ll r,ll x) {
	auto itr= split(r+1),itl= split(l);
	ll sz=0;
	while(itl!=itr) {
		num[++sz]= {
			itl->x,itl->r-itl->l+1
		}
		;
		itl++;
	}
	sort(num+1,num+sz+1);
	ll v=0;
	while(x>0) {
		++v;
		x-=num[v].second;
	}
	return num[v].first;
}
ll ksm(ll a,ll b,ll k) {
	a%=k;
	ll ans=1;
	while(b) {
		if(b&1) {
			ans=(ans*a)%k;
		}
		a=(a*a)%k;
		b>>=1;
	}
	return ans%k;
}
ll op4(ll l,ll r,ll x,ll y) {
	ll ans=0;
	auto itr= split(r+1),itl= split(l);
	while(itl!=itr) {
		ll val=ksm(itl->x,x,y);
		val=val*((itl->r-itl->l+1)%y);
		val%=y;
		ans=(ans+val)%y;
		itl++;
	}
	return ans;
}
ll n,m,seed,vmax;
ll rnd() {
	ll ret=seed;
	seed=(seed*7+13)%1000000007;
	return ret;
}
signed main() {
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin>>n>>m>>seed>>vmax;
	for (int i=1;i<=n;++i) {
		ll v=(rnd()%vmax)+1;
		odt.insert(node(i,i,v));
	}
	while(m--) {
		ll op=(rnd()%4+1),l=(rnd()%n)+1,r=(rnd()%n)+1;
		if(l>r) {
			swap(l,r);
		}
		ll x;
		if (op == 3) {
			x = (rnd() % (r - l + 1)) + 1;
		} else {
			x = (rnd() % vmax) +1;
		}
		ll y=0;
		if (op == 4) {
			y = (rnd()%vmax) +1;
		}
		if(op==1) {
			op1(l,r,x);
		} else if(op==2) {
			op2(l,r,x);
		} else if(op==3) {
			cout<<op3(l,r,x)<<"\n";
		} else {
			cout<<op4(l,r,x,y)<<"\n";
		}
	}
	return 0;
}