嘘~ 正在从服务器偷取页面 . . .

浅谈珂朵莉树(ODT)

算法 数据结构
OI
发布日期:   2021-08-15
更新日期:   2023-01-04
文章字数:   5.4k

浅谈珂朵莉树(ODT)

前言

珂学家狂喜（

一、珂朵莉树来源

珂朵莉树，原名老司机树（Old Driver Tree），在某场CF比赛中提出

因为题目背景是《末日时在做什么？有没有空？可以来拯救吗？》中的珂朵莉，所以就叫珂朵莉树了

二、珂朵莉树

题目链接：CF896C Willem, Chtholly and Seniorious

题目要求维护一种数据结构，支持以下操作

  1. 将 \([l,r]\) 区间内所有数加上 \(x\)
  2. 将 \([l,r]\) 区间内所有数改成 \(x\)
  3. 求 \([l,r]\) 区间第 \(k\) 小的数
  4. 求 \([l,r]\) 区间内所有数的 \(x\) 次方的和取模 \(y\)

值得注意的是，数据为随机数据，说明没有故意构造卡的数据

1.珂朵莉树有什么用？

最主要的就是区间内的推平操作了，即本题中的操作 \(2\)

当然还有别的操作，那就不是最主要的了

2.原理是什么？

写在前面：这个数据结构唯一前置知识就只有set

a.存储

我们可以把区间看作若干个结点，每个结点都有自己的左端点 \(l\) 、右端点 \(r\) 以及值 \(v\)

显然，一开始的时候每个结点的 \(l=r=idx\) ， \(idx\) 指该元素在数组中的下标

我们可以把这些结点按左端点顺序存储在一个set里

struct node
{
	int l,r; // 左、右端点
	mutable int v; // 值
	const bool operator<(const node &o)const
	{
		return l<o.l;
	}
};

注意 int v前的关键字 mutable，这个关键字和const恰好相反，意思是使v始终允许修改，即使它是个常量

那么我们为什么要多次一举呢？过会再说（

b.分割结点

显然每次推平操作并不能保证区间左、右端点恰好就在一个结点上，因此我们还需要对结点进行分割

考虑查找一个结点，使得其左端点恰好为 \(pos\) ，\(pos\) 指某次操作中的一个分割点

我们可以用set中的lower_bound()函数来找到第一个左端点大于等于 \(pos\) 的结点

（注：因为我们是按左端点顺序排序的）

这个lower_bound()会返回一个set的常量迭代器

现在我们找到了一个结点，那么会出现以下三种情况

第一种情况： \(pos\) 恰好为一个结点的左端点，直接返回这个端点的迭代器（显然前提是这个结点不是s.end()）

那么其他情况得到的这个结点的左端点一定比 \(pos\) 大

因此可以尝试分割前一个结点，即把迭代器it--

第二种情况：这个结点的右端点小于 \(pos\) ，由于结点的端点一定是连续的，说明 \(pos\) 是新加入的结点，直接 return s.end()

第三种情况：最普遍的情况，找到了一个结点恰好包含 \(pos\) ，因为我们要的是以 \(pos\) 为左端点的结点，显然我们要把这个结点分割成 \(node\{l,pos-1,v\}\) 和 \(node\{pos,r,v\}\)

set<node>::iterator split(R int pos)
{
	set<node>::iterator it=s.lower_bound({pos});
	if(it!=s.end()&&it->l==pos)return it; // 情况1
	it--;
	if(it->r<pos)return s.end(); // 情况2
	R int l=it->l,r=it->r,v=it->v; // 情况3
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v}).first; 
    // insert函数的返回值是pair类型的，而它的first恰好使我们需要的（新插入结点的指针）
}

c.推平

解决了区间的端点问题，我们只要获取要求修改区间左、右端点的结点，把这一段删除，再插入要求赋的值和修改区间的左、右端点作为新的结点

注意一定要先找右端点所在结点，再找左端点所在结点

为什么？因为我们再分割结点时大概率删除了部分结点，并加入新的结点，如果我们先找左端点所在结点，再找右端点所在结点，很有左端点所在结点的迭代器已经失效了

例如有一个结点 \(node\{l=1,r=5\}\) ，修改区间的左端点为 \(1\) ，右端点为 \(3\)

按先左再右的顺序，我们先会得到左端点所在结点

\(node\{l=1,r=5\}\)

显然如果我们找右端点所在结点，会将左端点所在结点进行分割，那么原来的结点就没了，迭代器失效，然后RE

inline void assign(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l); // 找结点
	s.erase(itl,itr); // 删掉[itl,itr)中所有结点
	s.insert({l,r,k}); // 插入新结点
}

d.剩余操作

区间加，十分暴力，十分简单，我们只要找到左、右端点所在结点，然后直接把每个结点修改就行

现在知道为什么要写mutable了吧！因为split()返回的是常量迭代器

inline void add(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(R set<node>::iterator it=itl; it!=itr; it++)
		it->v+=k; // 直接加
}

区间第 \(k\) 小数，我们只要把区间内的所有结点取出来从大到小排序即可

注意每个结点指代的可能是一段区间，而我们要求的是第 \(k\) 小的数，因此每遍历一个结点，如果 \(k\) 大于该结点指代的区间长，则让 \(k\) 减去该结点指代的区间长，否则第 \(k\) 小的数就在该结点区间内，直接输出即可

struct Rank
{
	int num,cnt;
	const bool operator<(const Rank &o)const
	{
		return num<o.num;
	}
};
inline int rnk(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	vector<Rank> v;
	for(R set<node>::iterator it=itl; it!=itr; it++)
		v.push_back({it->v,it->r - it->l +1}); // 记录结点
	sort(v.begin(),v.end());
	for(R int i=0; i<v.size(); i++)
		if(v[i].cnt<k)k-=v[i].cnt; // 减去区间长
		else return v[i].num;
	return -1; // 这句显然在数据合法时没有任何用
}

区间求和，只要遍历一下，加一下乘一下取模一下就好

inline int sum(R int l,R int r,R int x,R int y)
{
	R int ans=0;
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl; it!=itr; it++)
		ans=(ans%y+qpow(it->v,x,y)%y*(it->r-it->l+1)%y)%y; // 快速幂qpow()就不贴了
	return ans;
}

3.复杂度分析

set实现的珂朵莉树复杂度为 \(O(n\log^2n)\)

不过本人不是很会分析，这篇文章分析证明的很好，大家可以看看

完整代码 （注：原题的随机数据是给定 \(seed\) 等自行生成）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define mod (int)(1e9+7)
#define MAXN (int)(1e5+5)
int n,m,seed,vmax;
int qpow(R int a,R int b,R int p)
{
	R int ans=1,base=a;
	while(b)
	{
		if(b&1)ans=(ans%p*base%p)%p;
		base=(base%p*base%p)%p;
		b>>=1;
	}
	return ans%p;
}
struct node
{
	int l,r;
	mutable int v;
	const bool operator<(const node &o)const
	{
		return l<o.l;
	}
};
int rnd()
{
	R int ret=seed;
	seed=(seed*7+13)%mod;
	return ret;
}
int a[MAXN];
set<node> s;
set<node>::iterator split(R int pos)
{
	set<node>::iterator it=s.lower_bound({pos});
	if(it!=s.end()&&it->l==pos) return it;
	it--;
	if(it->r<pos)return s.end();
	R int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v}).first;
}
inline void add(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(R set<node>::iterator it=itl; it!=itr; it++)
		it->v+=k;
}
inline void assign(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	s.erase(itl,itr);//[itl,itr)
	s.insert({l,r,k});
}
struct Rank
{
	int num,cnt;
	const bool operator<(const Rank &o)const
	{
		return num<o.num;
	}
};
inline int rnk(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	vector<Rank> v;
	for(R set<node>::iterator it=itl; it!=itr; it++)
		v.push_back({it->v,it->r - it->l +1});
	sort(v.begin(),v.end());
	for(R int i=0; i<v.size(); i++)
		if(v[i].cnt<k)k-=v[i].cnt;
		else return v[i].num;
	return -1;
}
inline int sum(R int l,R int r,R int x,R int y)
{
	R int ans=0;
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl; it!=itr; it++)
		ans=(ans%y+qpow(it->v,x,y)%y*(it->r-it->l+1)%y)%y;
	return ans;
}
signed main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
	for(R int i=1; i<=n; i++)
	{
		a[i]=(rnd()%vmax)+1;
		s.insert({i,i,a[i]});
	}
	for(R int i=1; i<=m; i++)
	{
		R 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;}
		if(op==1)
			add(l,r,x);
		else if(op==2)
			assign(l,r,x);
		else if(op==3)
			printf("%lld\n",rnk(l,r,x));
		else printf("%lld\n",sum(l,r,x,y));
	}
	return 0;
}
/*
*	在太阳西斜的这个世界里，置身天上之森，
*	等这场战争结束之后，不归之人与望眼欲穿的人们，
*	人人本着正义之名，长存不灭的过去，逐渐消逝的未来，
*	我回来了，纵使日薄西山，即便看不到未来，
*	此时此刻的光辉，盼君勿忘
*
*							————世上最幸福的女孩
*/

三、珂朵莉树例题

（注：都是洛谷上的题~）

1.P4979 矿洞：坍塌

题目链接：P4979 矿洞：坍塌

题意：要求维护一个数据结构，支持对给定字符串进行如下操作

A x y op表示替换材料，将 \(x\) 到 \(y(1\le x\le y\le N)\) 区间内的材料替换为op，op为\(A,B,C\) 三种材料字符中的一个

B x y表示是否询问，即询问 \(x\) 到 \(y(1\le x\le y\le N)\)区间内的材料是否合法，合法输出Yes，不合法输出No

合法指该区间连续且材料相等，并且该区间前一个和后一个材料不相同

几乎是板子题，没什么特别的，只要跟题目意思写查询操作就行

不过要注意的是，出题人卡了无优化的ODT

那么怎么优化呢？我们只要在每次查询时将相同值的相邻结点合并即可

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(5e5+5)
int n,Q;
char a[MAXN];
struct node
{
	int l,r;
	mutable char v;
	const bool operator<(const node &o)const
	{
		return l<o.l;
	}
};
set<node>s;
set<node>::iterator split(R int pos)
{
	set<node>::iterator it=s.lower_bound({pos});
	if(it!=s.end()&&it->l==pos)return it;
	it--;
	if(it->r<pos)return s.end();
	R int l=it->l,r=it->r;
	R char v=it->v;
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v}).first;
}
inline void assign(R int l,R int r,R char k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert({l,r,k});
}
inline void query(R int l,R int r)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	if(l!=r)
	{
		set<node>::iterator it=itl,last=itl;
		it++;
		for(; it!=itr; it++,last++)
			if(it->v!=last->v)
			{
				puts("No");
				R int _l=itl->l,_r=last->r;
				R char _v=last->v;
				s.erase(itl,it);
				s.insert({_l,_r,_v});
				return;
			}
	}
	R char _v=itl->v;
	s.erase(itl,itr);
	s.insert({l,r,_v});
	if(l==1||r==n){puts("Yes");return;}
	set<node>::iterator ib=split(r+1),ia=split(l-1);
	puts((ia->v!=ib->v)?"Yes":"No");
}
signed main()
{
	scanf("%lld %s\n",&n,a+1);
	for(R int i=1; i<=n; i++)
	{
		R int l=i,r=i;
		while(a[l]==a[i])r=++i;
		s.insert({l,r,a[--i]});
	}
	scanf("%lld\n",&Q);
	while(Q--)
	{
		R int l,r;
		R char op,k;
		scanf("%c",&op);
		if(op=='A')
		{
			scanf("%lld %lld %c\n",&l,&r,&k);
			assign(l,r,k);
		}else
		{
			scanf("%lld %lld\n",&l,&r);
			query(l,r);
		}
	}
	return 0;
}

2.P5350 序列

题目链接：P5350 序列

题意：要求维护一个数据结构，支持对给定数组进行以下操作

1 l r求 \([l,r]\) 的区间和

2 l r v将 \([l,r]\) 赋值为 \(v\)

3 l r v将 \([l,r]\) 加上 \(v\)

4 l1 r1 l2 r2将 \([l_1,r_1]\) 复制到 \([l_2,r_2]\)

5 l1 r1 l2 r2将 \([l_1,r_1]\) 和 \([l_2,r_2]\) 交换

6 l r将 \([l,r]\)翻转

我直呼神仙题

本题前三个操作就是基本操作

后三个操作值得探讨

首先是将 \([l_1,r_1]\) 中所有数复制到 \([l_2,r_2]\)

我们可以把 \([l_1,r_1]\) 中所有结点记录，然后直接用这些结点推平 \([l_2,r_2]\)

struct THR
{
	int l,r,v;
};
void copy(R int l1,R int r1,R int l2,R int r2)
{
	set<node>::iterator itr=split(r1+1),itl=split(l1);
	vector<THR>vec;
	R int tmp=l2-l1;
	for(set<node>::iterator it=itl; it!=itr; it++)
		vec.push_back({it->l+tmp,it->r+tmp,it->v});
	for(R int i=0; i<vec.size(); i++)
		assign(vec[i].l,vec[i].r,vec[i].v);
}

其次是将 \([l_1,r_1]\) 和 \([l_2,r_2]\) 交换

我比较懒，直接把 \([l_1,r_1]\) 复制到 \([n+1,n+r_1-l_1+1]\)

然后就像当年 int c=a;a=b;b=c;一样交换就行了

void Swap(R int l1,R int r1,R int l2,R int r2)
{
	copy(l1,r1,n+1,n+r1-l1+1);
	copy(l2,r2,l1,r1);
	copy(n+1,n+r1-l1+1,l2,r2);
}

最后是区间翻转操作

这个不难，记录每个结点，然后改下左右端点插入就好

void rev(R int l,R int r)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	vector<THR>vec;
	for(set<node>::iterator it=itl; it!=itr; it++)
		vec.push_back({it->l,it->r,it->v});
	R int cnt=r;
	s.erase(itl,itr);
	for(R int i=0; i<vec.size(); i++)
	{
		s.insert({cnt-(vec[i].r-vec[i].l),cnt,vec[i].v});
		cnt-=(vec[i].r-vec[i].l+1);
	}
}

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(3e5+5)
#define mod (int)(1e9+7)
template<typename T>inline void read(R T &k)
{
	R char ch=getchar();R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	k=x*f;
}
int n,m;
int a[MAXN];
struct node
{
	int l,r;
	mutable int v;
	const bool operator<(const node &o)const
	{
		return l<o.l;
	}
};
set<node> s;
set<node>::iterator split(R int pos)
{
	set<node>::iterator it=s.lower_bound({pos});
	if(it!=s.end()&&it->l==pos)return it;
	it--;
	if(it->r<pos)return s.end();
	R int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v}).first;
}
void assign(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert({l,r,k});
}
int sum(R int l,R int r)
{
	R int ans=0;
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl; it!=itr; it++)
		ans=(ans+(it->v*(it->r-it->l+1)%mod)%mod)%mod;
	return ans;
}
struct THR
{
	int l,r,v;
};
void add(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl; it!=itr; it++)
		it->v=(it->v+k)%mod;
}
void copy(R int l1,R int r1,R int l2,R int r2)
{
	set<node>::iterator itr=split(r1+1),itl=split(l1);
	vector<THR>vec;
	R int tmp=l2-l1;
	for(set<node>::iterator it=itl; it!=itr; it++)
		vec.push_back({it->l+tmp,it->r+tmp,it->v});
	for(R int i=0; i<vec.size(); i++)
		assign(vec[i].l,vec[i].r,vec[i].v);
}
void Swap(R int l1,R int r1,R int l2,R int r2)
{
	copy(l1,r1,n+1,n+r1-l1+1);
	copy(l2,r2,l1,r1);
	copy(n+1,n+r1-l1+1,l2,r2);
}
void rev(R int l,R int r)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	vector<THR>vec;
	for(set<node>::iterator it=itl; it!=itr; it++)
		vec.push_back({it->l,it->r,it->v});
	R int cnt=r;
	s.erase(itl,itr);
	for(R int i=0; i<vec.size(); i++)
	{
		s.insert({cnt-(vec[i].r-vec[i].l),cnt,vec[i].v});
		cnt-=(vec[i].r-vec[i].l+1);
	}
}
signed main()
{
	read(n);read(m);
	for(R int i=1; i<=n; i++)
		read(a[i]),s.insert({i,i,a[i]});
	while(m--)
	{
		R int op,l1,l2,r1,r2,v;
		read(op);read(l1);read(r1);
		if(op==1)printf("%lld\n",sum(l1,r1)); // 求和
		else if(op==2){read(v);assign(l1,r1,v);} // 赋值
		else if(op==3){read(v);add(l1,r1,v);} // 区间加
		else if(op==4){read(l2);read(r2);copy(l1,r1,l2,r2);} // 复制
		else if(op==5){read(l2);read(r2);Swap(l1,r1,l2,r2);} // 交换
		else {rev(l1,r1);} // 翻转
	}
	set<node>::iterator it=s.begin();
	R int idx=0;
	for(;it!=s.end();it++)
	{
		for(R int i=it->l; i<=it->r&&idx<n; idx++,i++)
			printf("%lld%c",it->v," \n"[idx==n-1]);
	}
	return 0;
}

3.CF343D Water Tree

题目链接：CF343D Water Tree

题意：给出一棵以 \(1\) 为根节点的 \(n\) 个节点的有根树。每个点有一个权值，初始为 \(0\) ，支持以下操作

1 u将点 \(u\) 和其子树上的所有节点的权值改为 \(1\)

2 u将点 \(u\) 到 \(1\) 的路径上的所有节点的权值改为 \(0\)

3 u询问 \(u\) 的权值

简单的树链剖分+珂朵莉树

单点查询只要lower_bound()就行了

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(5e5+5)
int n,m;
int a[MAXN];
int fa[MAXN],son[MAXN],siz[MAXN];
int dep[MAXN],idx,top[MAXN],id[MAXN];
template<typename T>inline void read(R T &k)
{
	R char ch=getchar();R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	k=x*f;
}
struct Edge
{
	int u,v,next;
}e[MAXN<<1];
struct node
{
	int l,r;
	mutable int v;
	const bool operator<(const node &o)const
	{
		return l<o.l;
	}
};
set<node> s;
int head[MAXN],pos=1;
set<node>::iterator split(R int pos)
{
	set<node>::iterator it=s.lower_bound({pos});
	if(it!=s.end()&&it->l==pos)return it;
	--it;
	if(it->r<pos)return s.end();
	R int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v}).first;
}
void assign(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert({l,r,k});
}
void add(R int u,R int v)
{
	e[pos]={u,v,head[u]};
	head[u]=pos++;
}
void dfs(R int u,R int f,R int d)
{
	dep[u]=d;
	fa[u]=f;
	siz[u]=1;
	R int mx=-1;
	for(R int i=head[u]; i; i=e[i].next)
	{
		R int v=e[i].v;
		if(v==f)continue;
		dfs(v,u,d+1);
		siz[u]+=siz[v];
		if(siz[v]>mx)mx=siz[v],son[u]=v;
	}
}
void dfs(R int u,R int ftop)
{
	top[u]=ftop;
	id[u]=++idx;
	a[idx]=0;
	if(!son[u])return;
	dfs(son[u],ftop);
	for(R int i=head[u]; i; i=e[i].next)
	{
		R int v=e[i].v;
		if(v==fa[u]||v==son[u])continue;
		dfs(v,v);
	}
}
void upRange(R int x,R int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		assign(id[top[x]],id[x],0);
		x=fa[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	assign(id[x],id[y],0);
}
void upSon(R int u){assign(id[u],id[u]+siz[u]-1,1);}
int query(R int u)
{
	set<node>::iterator pos=s.lower_bound({id[u]});
	if(pos==s.end()||pos->l>id[u])--pos;
	return pos->v;
}
signed main()
{
	read(n);
	for(R int i=1,u,v; i<=n-1; i++)
	{
		read(u);read(v);
		add(u,v);add(v,u);
	}
	dfs(1,0,1);
	dfs(1,1);
	for(R int i=1; i<=n; i++)
		s.insert({i,i,0});
	read(m);
	while(m--)
	{
		R int op,k;
		read(op);read(k);
		if(op==1)upSon(k);
		if(op==2)upRange(1,k);
		if(op==3)printf("%lld\n",query(k));
	}
	return 0;
}

4.CF915E Physical Education Lessons

题目链接：CF915E Physical Education Lessons

题意：区间赋值为 \(1\) 或 \(0\) ，求 \(1\) 个数 （我用 \(1\) 表示题目中的工作日）

这题比板子题还要简单

唯一要注意的是每次输出结果不能去扫一遍（复杂度爆炸），而是在每次修改时统计

直接贴代码了（

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,Q,ans;
template<typename T>inline void read(R T &k)
{
	R char ch=getchar(); R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-');f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	k=x*f;
}
struct node
{
	int l,r;
	mutable int v;
	const bool operator<(const node &o)const
	{
		return l<o.l;
	}
};
set<node>s;
set<node>::iterator split(R int pos)
{
	set<node>::iterator it=s.lower_bound({pos});
	if(it!=s.end()&&it->l==pos)return it;
	--it;
	if(it->r<pos)return s.end();
	R int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v}).first;
}
void assign(R int l,R int r,R int k)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl; it!=itr; it++)
		ans-=it->v*(it->r-it->l+1);
	s.erase(itl,itr);
	s.insert({l,r,k});
	printf("%lld\n",ans+=k*(r-l+1));
}
signed main()
{
	read(n);read(Q);
	ans=n;
	s.insert({1,n,1});
	while(Q--)
	{
		R int op,l,r;
		read(l);read(r);read(op);
		assign(l,r,op-1);
	}
	return 0;
}

总结

本文简单介绍了珂朵莉树

顺便讲了几道简单的例题

题外话

作为珂学家，怎么能少了这环节呢（

upd.20230104 已经用 AI 修复过了，现在更加高清了~😚

再来一个（

如果幸福有颜色的话，那一定是终末之红染尽的蓝色！

文章作者: q779
文章链接: https://q779.cn/2021/08/15/qian-tan-ke-duo-li-shu-odt/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
算法 数据结构
评论
  目录