【洛谷比赛】你的名字T1 线索

题面

祭典即将举行，编织结绳的工作正在紧张地开展着。而这天，泷和三叶交换了身体，三叶担心泷不会编结绳，在日记里留下了编织结绳的方法，并请你来帮助泷编好结绳。

将丝线汇集在一起，编织成形；扭曲，缠绕，有时又还原，再连接；那就是结，那就是时间。

结绳是神的思想的重要载体。编织结绳有两个基本操作：染色和交换。染色是为了寄托人民对美好生活的向往，而交换则是要在线与线之间、人与人之间建立联系，形成结，建立羁绊。

现在泷要编织由

三叶给泷的编织方法有

若

两条丝线交换后会形成永久的联系。这种联系体现在，交换发生后，若其中任意一条丝线被染上了某种颜色，另一条丝线也会被同时染上相同的颜色。这种羁绊还具有传递性，即如果

注意，如果交换的两根丝线在交换前已经建立了联系，进行交换操作后它们的联系不会改变，但仍要对它们染色以示纪念。

为了检查编织的效果，泷想知道编织完毕后，每一个位置上丝线的颜色。此外，为了保证结绳的联系足够牢固，泷还需要知道与每条丝线建立联系的丝线的数目。你能帮助他吗？

输入格式：

输入共

输出格式：

输出共

#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("
");
    for(int i=1;i<=n;i++)
        printf("%d ",siz[bel[i]]-1);
    return 0;
}

“Make my parents proud,and impress the girl I like.”

【洛谷比赛】你的名字T1 线索

题面

分析

代码