#C241126B. 大艺术家

标签（Label）

启发式合并

网址（Website）

题目详情 - 大艺术家 - Super

题解 - 大艺术家 - Super

题目（Problem）

输入数据 1

6 6 5
1 2 1 2 1 2
1 6
5 5
4 5
3 5
2 5
1 5
5 2
4 3
2 1
3 4
1 5

输出数据 1

【样例1解释】

$L_i$ 依次为 $7,0,0,2,4,5$。

【样例2】

见选手目录下的 $artist/artist4.in$ 与 $artist/artist4.ans$。

该样例满足测试点 $1\sim2$ 的限制。

在选手目录下的 $artist/detailed_artist2.ans$ 中含有该样例不加密的答案。

【样例3】

见选手目录下的 $artist/artist3.in$ 与 $artist/artist5.ans$。

该样例满足测试点 $6\sim8$ 的限制。

【样例4】

见选手目录下的 $artist/artist4.in$ 与 $artist/artist4.ans$。

该样例满足测试点 $12\sim15$ 的限制。

【样例5】

见选手目录下的 $artist/artist5.in$ 与 $artist/artist5.ans$。

该样例满足测试点 $18\sim20$ 的限制。

题解（Solution）

首先，由于不相交和包含的条件，以及 $\text{A}$ 性质，想到了转图论。又因为多种颜色，又要计算不同颜色个数，想到了启发式合并。

那就直接建区间树，先将对应元素放在最小的区间里面，这个可以用线段树区间赋值来求出每个点对应的最小的区间 $id$ 。后面修改元素的时候就用一个 unordered_map 来存储，如果当前区间已经互不相同，就直接删除这个区间，并且把这个区间的元素弄到更大的包含它区间里面，这个地方使用启发式合并，可以做到 $O(n\log n)$ 的时间，由于 unordered_map 的常数，此题开了 $2$ 秒，还是能过。

时间复杂度 $O(n\log n)$ ，算上常数可以按 $O(n\log^2 n)$ 计算。

出题者题解

代码（Code）

100分

#include<bits/stdc++.h>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<unordered_map>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) For(i,1,b) cerr<<a[i]<<' ';cerr<<'\n';
using namespace std;
#define P pair<int,int> 
#define x first
#define y second
#define in(x,l,r) (l<=x&&x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x; 
}template<typename G>void write(G x){
	if(x<0) putchar('-'), write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f;
constexpr int N = 501234;
bool ST;

int n,m,q,ans,as[N];
int c[N],id[N];
P p[N];

namespace tree{
	#define mid ((l+r)>>1)
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct Tr{int col,tag;}tr[N<<2|3];
	inline void pushtag(int p,int v){tr[p]={v,v};}
	void pushdown(int p){
		if(~tr[p].tag){pushtag(ls,tr[p].tag), pushtag(rs,tr[p].tag), tr[p].tag=-1;}}
	void update(int p,int l,int r,int L,int R,int v){
		if(L<=l && r<=R) return pushtag(p,v);
		if(l^r) pushdown(p);
		if(L<=mid) update(ls,l,mid,L,R,v);
		if(R>mid) update(rs,mid+1,r,L,R,v);
	}void update(P p,int v){update(1,1,n,p.x,p.y,v);}
	int ask(int p,int l,int r,int x){
		if(l==r) return tr[p].col; if(l^r) pushdown(p);
		return x <= mid ? ask(ls,l,mid,x) : ask(rs,mid+1,r,x);
	}int ask(int x){return ask(1,1,n,x);}
}

int st[N],tp;
int fa[N];

unordered_map<int,int> mp[N];
int dif[N];
inline void ins(int i,int c,int v=1){
	if(mp[i][c]==0 && v) dif[i]++;
	mp[i][c] += v;
}
inline void del(int i,int c,int v=1){
	mp[i][c] -= v;
	if(mp[i][c]==0) dif[i]--;
}
void merge(int i,int j){//ºÏ³Éµ½jÉÏ 
	if(mp[i].size() > mp[j].size()){swap(mp[i],mp[j]), swap(dif[i],dif[j]);}
	for(auto p:mp[i]){
		int c=p.x,v=p.y;
		ins(j,c,v);
	}mp[i].clear(),dif[i]=0;
}

void Solve(){
	n=rd(),m=rd(),q=rd();For(i,1,n) c[i]=rd();
	For(i,1,m) p[i] = {rd(),rd()};
	iota(id+1,id+m+1,1);
	sort(id+1, id+m+1, [&](int a,int b){
		P x=p[a], y=p[b]; return x.x^y.x ? x.x<y.x : x.y>y.y;});
	sort(p+1, p+m+1, [&](P x,P y){return x.x^y.x ? x.x<y.x : x.y>y.y;});
	For(i,1,m) as[i] = m+id[i];
	
	For(i,1,m){
		tree::update(p[i],i);
		while(tp && p[st[tp]].y < p[i].x) tp--;
		if(tp) fa[i] = st[tp];
		st[++tp] = i;
	}
	
	For(i,1,n) ins(tree::ask(i), c[i]);
	
	for(int i=1,j=1;i<=m;j=++i){
		while(j && dif[j] == p[j].y-p[j].x+1){
			as[j]=0, 
			merge(j,fa[j]);
			tree::update(p[j],fa[j]);
			j = fa[j];//Ë³±ã¼ì²é¸¸Ç×¿É²»¿ÉÒÔ 
		}
	}
	
	For(t,1,q){
		int x=rd(), y=rd(), i=tree::ask(1,1,n,x);
		del(i, c[x]), ins(i, y), c[x] = y;
		while(i && dif[i] == p[i].y-p[i].x+1){
			as[i]=t, 
			merge(i, fa[i]);
			tree::update(p[i],fa[i]);
			i = fa[i];//Ë³±ã¼ì²é¸¸Ç×¿É²»¿ÉÒÔ 
		}
	}
	For(i,1,m) ans ^= as[i];
	write(ans), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("artist.in","r",stdin);
	freopen("artist.out","w",stdout);
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}