501000045 - Old Driver Tree

珂朵莉树是一类依据区间推平，set 保证复杂度的数据结构，一般适用于区间赋值数多的题目。

1. 存储序列

珂朵莉树将序列分成包含连续相同值的若干段使用 set 来存储。set 在随机数据下时间复杂度期望为 O(n \log^2 n)，接近线性，用链表存储的珂朵莉树时间复杂度期望为 O(n\log n)。值得注意的是，如果数据不随机，珂朵莉树可以轻易地被卡成 O(n^2)。

以下给出序列的储存方式。注意通过排序使得 set 内数组有序。

struct node {
	int l,r;
  	mutable int v;
  	//这里少了一些东西
};
set<node>s;

2. 区间赋值

显然随机数据下，随机出来的 l,r 相隔不会很近，所以 set 内的元素个数不会太多。

当然，在修改时珂朵莉树内不一定恰好有元素的左端点和右端点分别为 l,r，所以需要对 set 中的元素进行分割。例如，将[a,b] 分为 [a,l-1] 和 [l,b]，这样就能方便地进行修改。

我们使用 lower_bound 快速找到 l,r 所在的区间，然后对其进行分割即可。参考代码如下。注意代码有一处问题，需要自行修改。

inline st split(int pos) {
	st it=lower_bound(s.begin(),s.end(),(node){pos,0,0});
	if(it!=s.end() && it->l==pos) return it;
	it--;
	if(it->r<pos) return s.end();
	int l=it->l,r=it->r,v=it->v;
	s.erase(it),s.insert((node){l,pos-1,v});
	return s.insert((node){pos,r,v}).first;
}

同理，很容易写出区间赋值的代码：

inline void assign(int l,int r,int x) {
	st pr=split(r+1),pl=split(l);
	s.erase(pl,pr),s.insert((node){l,r,x});
}

3.区间查询

同理。

inline int query(int l,int r,int x) {
	int ans=0;
	st qr=split(r+1),ql=split(l);
	for(;ql!=qr;ql++) if((*ql).v==x) ans+=(*ql).r-(*ql).l+1;
	return ans;
}

学习完 ODT 后，你需要完成如下题目： 给出一个长为 n 的数列，以及 m 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数 a_i，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 个整数 l,r,c ，表示询问区间 [l,r] 中值为 c 的数的个数，并把区间 [l,r] 的所有元素改为 c。

输出包含 m 行，每行一个整数，为每次询问结果。

对于全部数据：1\leq n,m\leq 2\times {10}^5,1\leq l,r\leq n,-10^{18}\le c,a_i \le 10^{18}.