CF 771 E. Colorful Operations(珂朵莉树+线段树)

传送门
这个题我第一眼望过去还以为CF终于出了一个数据结构题，然而实际上这就是一个数据结构题

题意：

维护一个长度为n的序列，序列的每一个元素大小\(a[i]\)初始为\(0\)，颜色初始为\(1\).
有三个操作执行\(q\)次
1.把\([l,r]\)涂成颜色\(c\)
2.把所有颜色为\(c\)的元素加上\(x\)
3.输出\(a[i]\)
其中\(n、q \leq 10^{6}\)
数据随机

题解：

借助此题学习一下珂朵莉树。
它不是一个数据结构而是一种方法

其大致的思想就是把一个序列的元素用一个三元组\(node(l,r,val)\)表示，然后对于操作暴力解决。储存这个三元组一般时候set。

因为在数据随机的情况下这样的一个序列平均是只用\(log(n)\)个三元组表示的状态(不会证明)

对于这道题来说：
记录一个\(lazy\)标记，\(lazy[c]\)表示对颜色\(c\)的元素操作的总和。

对于操作1，利用珂朵莉树的思想暴力修改(时间复杂度\(O(logn)\))。同时对于所有的\(a[i]\)加上\(lazy[col\_pre]-lazy[col\_now]\)由于在使用珂朵莉树的技巧之后每一个元素有同一个颜色，所以这一步实际上就是区间加，使用线段树实现(时间复杂度为\(O(log^2n)\))。

对于操作2，直接修改\(lazy[c]\)。

对于操作3，\(query(i)+lazy[col(i)]\)，前半部分是线段树的查询操作，\(col(i)\)可以对\(set\)用\(lower_bound\)在\(log\)的时间得到。

珂朵莉树的具体实现

\(set\)的一些知识
1.\(set.end()\)并不是\(set\)中最后一个元素的迭代器，其数值上等于\(set.size()\)。
2.\(set.erase(a,b)\)可以删除迭代器\(a\)，\(b\)之间的所有元素。

\(set\)的定义

struct node{
	int l,r;
	mutable int col;
	node(int L,int R,int COL){
		l=L,r=R,col=COL;
	} 
};
bool operator <(node a,node b){
	return a.l st;

\(split\)

set::iterator split(int pos){
	auto it=st.lower_bound(node(pos,pos,pos));
	if(it!=st.end()&&it->l==pos)return it;
	it--;
	node tmp=*it;
	st.erase(it);
	st.insert(node(tmp.l,pos-1,tmp.col));
	return st.insert(node(pos,tmp.r,tmp.col)).first;
}

\(split(pos)\)的作用是将\(pos\)所在的\(node\)分成一个以\(pos\)为开始的\(node\)和另一个\(node\)并会返回一个迭代器（一个指针），指向\(pos\)所在的\(node\)

执行\(split(r+1)\)和\(split(l)\)就可以将区间\([l,r]\)左右边界划出。

\(assign\)

void assign(int l,int r,int col){
	auto itr=split(r+1),itl=split(l); 
	for(auto i=itl;i!=itr;i++)
		add(1,n,i->l,i->r,1,Lazy[i->col]-Lazy[col]);
	st.erase(itl,itr);
	st.insert(node(l,r,col));
}

把\([l,r]\)合并成一个\(node\)并且完成维护
注意这里一定要先\(split(r+1)\)在\(split(l)\)，否则\(itl\)会丢失。

\(find\_col\)

int get_col(int x){
	auto it=st.lower_bound(node(x,x,x));
	if(it!=st.end()&&it->l==x)return it->col;
	it--;
	return it->col;
}

完整代码

#include
#include
#include
#include
#include
#include
using namespace std;
#define mid (L+R>>1)
#define ls (now<<1)
#define rs (now<<1|1)
const int N=1010000;
int read(){
	int sum=0,f=1;;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum*f;
}
long long sum[N*8],lazy[N*8],Lazy[N];
int n;
char s[10];
void update(int now){
	sum[now]=sum[ls]+sum[rs];
}
void pushdown(int L,int R,int now){
	if(lazy[now]==0)return;
	lazy[ls]+=lazy[now];
	lazy[rs]+=lazy[now];
	sum[ls]+=(mid-L+1)*lazy[now];
	sum[rs]+=(R-mid)*lazy[now];
	lazy[now]=0;
}
void add(int L,int R,int l,int r,int now,long long w){
	pushdown(L,R,now);
	if(L==l&&r==R){
		lazy[now]+=w;
		sum[now]+=(r-l+1)*w;
		return ;
	}
	if(l>mid)add(mid+1,R,l,r,rs,w);
	else if(r<=mid)add(L,mid,l,r,ls,w);
	else add(L,mid,l,mid,ls,w),add(mid+1,R,mid+1,r,rs,w);
	update(now); 
}
long long query(int L,int R,int x,int now){
	pushdown(L,R,now);
	if(L==R)return sum[now];
	if(x>mid)return query(mid+1,R,x,rs);
	else return query(L,mid,x,ls);
}
struct node{
	int l,r;
	mutable int col;
	node(int L,int R,int COL){
		l=L,r=R,col=COL;
	} 
};
bool operator <(node a,node b){
	return a.l st;
set::iterator split(int pos){
	auto it=st.lower_bound(node(pos,pos,pos));
	if(it!=st.end()&&it->l==pos)return it;
	it--;
	node tmp=*it;
	st.erase(it);
	st.insert(node(tmp.l,pos-1,tmp.col));
	return st.insert(node(pos,tmp.r,tmp.col)).first;
}
void assign(int l,int r,int col){
	auto itr=split(r+1),itl=split(l); 
	for(auto i=itl;i!=itr;i++)
		add(1,n,i->l,i->r,1,Lazy[i->col]-Lazy[col]);
	st.erase(itl,itr);
	st.insert(node(l,r,col));
}
int get_col(int x){
	auto it=st.lower_bound(node(x,x,x));
	if(it!=st.end()&&it->l==x)return it->col;
	it--;
	return it->col;
}
int main(){
	int q;
	n=read(),q=read();
	st.insert(node(1,n,1));
	while(q--){
		scanf("%s",s+1);
		getchar();
		if(s[1]=='C'){
			int l=read(),r=read(),c=read();
			assign(l,r,c);
		}
		if(s[1]=='A'){
			int c=read(),w=read();
			Lazy[c]+=w;
		}
		if(s[1]=='Q'){
			int x=read();
			printf("%lld\n",query(1,n,x,1)+Lazy[get_col(x)]);
		}
	}
	return 0;
}