【题解】P9067 [Ynoi Easy Round 2022] 虚空处刑

· · 题解

【原题链接】

题目分析

显然同色连通块的合并只会发生 O(n) 次，所以只要每次找到有用的合并就可以保证复杂度。而连通块大小容易用并查集维护。

对每个同色块 u 开一棵动态开点线段树，索引为 i 的叶子节点维护一个链表，储存 u 相邻的颜色为 i 的连通块。这样每次容易遍历需要合并的连通块，合并连通块的时候直接做线段树合并就行了，叶子节点的信息合并是 O(1) 的。

但是有个问题，更改一个同色块时也会影响相邻同色块储存的相邻同色快信息。显然我们不能去暴力更改影响。但是可以给这个做法打一个补丁：每个同色块维护儿子同色块的信息，父亲同色块的合并特殊处理。这样一次修改就至多影响父亲的信息了。

一些细节：更改颜色时没有必要做链表删除，在合并时判断是否真正需要合并就行了，以及注意一下链表中出现重复元素的问题。显然复杂度是不受影响的。

代码实现

#include <bits/stdc++.h>

// 快读

using namespace std;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

struct ListNode{ int val,nxt; }__list_t[4000005];
int __list_cnt;
class ListIter
{
 private:
    int id;
 public:
    ListIter(int _i=0): id(_i){}
    inline int operator *()const { return __list_t[id].val; }
    inline ListIter &operator ++() { return id=__list_t[id].nxt,*this; }
    inline bool operator !=(const ListIter &rhs)const { return id!=rhs.id; }
};
class MyList
{
 private:
    static constexpr ListNode *t=__list_t;
    friend class ListIter;
    int hd,tl;
 public:
    using iterator=ListIter;
    MyList(): hd(0),tl(0){}
    inline void push_back(int x) { t[++__list_cnt]=(ListNode){x,hd},hd=x=__list_cnt;if(!tl)tl=x; }
    inline void join(MyList &o) { if(o.hd) hd?(t[tl].nxt=o.hd,tl=o.tl):(hd=o.hd,tl=o.tl),o.hd=o.tl=0; }
    inline void clear() { hd=tl=0; }
    inline bool empty()const { return !hd; }
    inline iterator begin()const { return ListIter(hd); }
    inline iterator end()const { return ListIter(); }
};

int n,m,a[1000005];

struct TreeNode{ int lc,rc; };
union UnionNode{ MyList val;TreeNode ch;UnionNode(){} }t[40000005];
int sgt_cnt,rt[1000005];
#define LC t[i].ch.lc
#define RC t[i].ch.rc
void modify(int p,int x,int &i,int l=1,int r=n)
{
    if(!i) i=++sgt_cnt;
    if(l==r) return (x?t[i].val.push_back(x):t[i].val.clear()),void();
    int mid=(l+r)>>1;
    if(mid>=p) modify(p,x,LC,l,mid);
    else modify(p,x,RC,mid+1,r);
}
MyList &query(int p,int i,int l=1,int r=n)
{
    if(l==r) return t[i].val;
    int mid=(l+r)>>1;
    if(mid>=p) return query(p,LC,l,mid);
    else return query(p,RC,mid+1,r);
}
void merge(int &x,int &y,int l=1,int r=n)
{
    if(!x || !y) return x|=y,y=0,void();
    if(l==r) return t[x].val.join(t[y].val),y=0,void();
    int mid=(l+r)>>1;
    merge(t[x].ch.lc,t[y].ch.lc,l,mid);
    merge(t[x].ch.rc,t[y].ch.rc,mid+1,r);
    y=0;
}

struct Edge{ int to,nxt; }e[1000005];
int cnt,head[1000005];
inline void addEdge(int u,int v)
    { e[++cnt]=(Edge){v,head[u]},head[u]=cnt; }

int fa[1000005],siz[1000005],anc[1000005];
inline int findFa(int x)
    { return x!=fa[x]?fa[x]=findFa(fa[x]):x; }
inline void link(int x,int y)
    { x=findFa(x),y=findFa(y);if(x!=y)siz[x]+=siz[y],fa[y]=x; }
void dfs(int u,int fa=0)
{
    anc[u]=fa;
    if(a[u]==a[fa]) link(fa,u);
    for(int i=head[u],v;(v=e[i].to);i=e[i].nxt) dfs(v,u);
    for(int i=head[u],v;(v=e[i].to);i=e[i].nxt) if(a[u]!=a[v]) modify(a[v],v,rt[findFa(u)]);
}

int main()
{
    // freopen("input.in","r",stdin);
    // freopen("output.out","w",stdout);
    qin>>n>>m;
    for(int i=2,x;i<=n;i++) qin>>x,addEdge(x,i);
    for(int i=1;i<=n;i++) qin>>a[i];
    iota(fa+1,fa+n+1,1),fill(siz+1,siz+n+1,1),dfs(1);
    while(m--)
    {
        int opt,x,y;
        qin>>opt;
        if(opt==1)
        {
            qin>>x>>y,x=findFa(x);
            if(a[x]==y) continue;
            a[x]=y;
            auto &ls=query(y,rt[x]);
            for(auto i: ls) if(a[i]==y) merge(rt[x],rt[i]),link(x,i);
            int z=findFa(anc[x]);
            if(a[z]!=y) (z&&(modify(y,x,rt[z]),0));
            else merge(rt[z],rt[x]),link(z,x);
            modify(y,0,rt[findFa(x)]);
        }
        else qin>>x,qout.writeln(siz[findFa(x)]);
    }
    return 0;
}