祭典即将举行，编织结绳的工作正在紧张地开展着。而这天，泷和三叶交换了身体，三叶担心泷不会编结绳，在日记里留下了编织结绳的方法，并请你来帮助泷编好结绳。
将丝线汇集在一起，编织成形；扭曲，缠绕，有时又还原，再连接；那就是结，那就是时间。
结绳是神的思想的重要载体。编织结绳有两个基本操作：染色和交换。染色是为了寄托人民对美好生活的向往，而交换则是要在线与线之间、人与人之间建立联系，形成结，建立羁绊。
现在泷要编织由n条丝线组成的结绳。这nn条结绳紧紧排成一排，按位置把它们叫作第1,2,?,n条丝线。编织开始前，每条丝线有自己的颜色（用一个正整数来表示），第i(1≤i≤n)条丝线颜色为ci?。
三叶给泷的编织方法有m步，第j(1≤j≤m)步用44个正整数aj?,lj?,rj?,xj?来描述。aj?的值为1或2。
若aj?=1，则表示这步操作为染色，这时要把[lj,rj?]这个区间上的丝线全部染成xj?这种颜色，保证lj?≤rj?。
若aj?=2，则表示这步操作为交换，这时要把lj?位置上的丝线和rj?位置上的丝线交换。作为它们交换的纪念，交换的同时要把这两条丝线染成xj?这种颜色。注意，aj?=2时不保证lj?≤rj?，但保证lj?≠rj?。
两条丝线交换后会形成永久的联系。这种联系体现在，交换发生后，若其中任意一条丝线被染上了某种颜色，另一条丝线也会被同时染上相同的颜色。这种羁绊还具有传递性，即如果1与2建立了羁绊，2又3建立了羁绊，那么我们就认为1也与3建立了羁绊。注意，丝线不能与自己形成结。
注意，如果交换的两根丝线在交换前已经建立了联系，进行交换操作后它们的联系不会改变，但仍要对它们染色以示纪念。
为了检查编织的效果，泷想知道编织完毕后，每一个位置上丝线的颜色。此外，为了保证结绳的联系足够牢固，泷还需要知道与每条丝线建立联系的丝线的数目。你能帮助他吗？
输入格式：
输入共(m+2)行。
第1行有2个以空格分隔的正整数n,m，分别代表丝线的数目和编织步骤的数目。
第2行有n个以空格分隔的正整数，第i个正整数ci?表示编织开始前第i条丝线的颜色。
以下m行每行有4个以空格分隔的正整数aj?,lj?,rj?,xj?，描述编织的步骤，意义如上所述。
输出格式：
输出共2行。
第1行有n个以空格分隔的正整数，第ii个正整数ci′?代表编织完毕后第ii个位置上的丝线的颜色。
第2行有n个以空格分隔的非负整数，第ii个非负整数di?代表编织完毕后与第ii个位置上的丝线建立联系的丝线数目。
作为T1，就考了一个不裸的线段树，我觉得还是有点恐怖了。然而我似乎是忽略了题目顺序是按剧情来的...
但是也能一眼看出来是线段树+并查集，但是具体怎么实现呢？
我们把时间作为lazy标记，时间大的颜色会覆盖时间小的颜色，所以我们不需要完全更新每个区间。
对于一个区间[l,r]，直接区间修改[l,r]
对于一个交换操作，只更新l的颜色，并把l和r并入一个集合之中。
再最后搜索答案的时候，只需要把同一个集合中，时间最晚的那一次修改作为集合的颜色即可
#include<bits/stdc++.h> using namespace std; #define N 100100 #define ll long long #define lc (p<<1) #define rc (p<<1|1) #define mid (t[p].l+t[p].r>>1) int n,m; int fa[N],col[N],bel[N],siz[N],colt[N]; struct email { int l,r,c,ti; }t[N*4]; inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void pushnow(int p,int v) { if(t[p].ti>=t[v].ti) t[v].ti=t[p].ti,t[v].c=t[p].c; } void pushdown(int p) { if(t[p].ti) { pushnow(p,lc);pushnow(p,rc); t[p].ti=0; } } void update(int p,int ql,int qr,int color,int nowt) { if(ql<=t[p].l&&qr>=t[p].r) { t[p].ti=nowt;t[p].c=color; return ; } pushdown(p); if(ql<=mid)update(lc,ql,qr,color,nowt); if(qr>mid)update(rc,ql,qr,color,nowt); } void build(int p,int l,int r) { t[p].l=l,t[p].r=r; if(l==r) { t[p].c=col[l]; return; } int bm=l+r>>1; build(lc,l,mid);build(rc,mid+1,r); } void query(int p) { if(t[p].l==t[p].r) { bel[t[p].l]=find(t[p].l); siz[bel[t[p].l]]++; if(colt[bel[t[p].l]]<t[p].ti) { colt[bel[t[p].l]]=t[p].ti; col[bel[t[p].l]]=t[p].c; } return ; } pushdown(p); query(lc);query(rc); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&col[i]); for(int i=1;i<=n;i++)fa[i]=i; build(1,1,n); for(int i=1;i<=m;i++) { int op,li,ri,xi; scanf("%d%d%d%d",&op,&li,&ri,&xi); if(op==1) update(1,li,ri,xi,i); else { int fl=find(li),fr=find(ri); if(fl!=fr) fa[fl]=fr; update(1,li,li,xi,i); } } query(1); for(int i=1;i<=n;i++) printf("%d ",col[bel[i]]); printf("\n"); for(int i=1;i<=n;i++) printf("%d ",siz[bel[i]]-1); return 0; }
原文：https://www.cnblogs.com/NSD-email0820/p/9743513.html