BZOJ-4129: Haruna’s Breakfast

[文章目录]

Description

一棵树上,每个结点都有一样食材,每个食材都有一个美味度,Shimakaze会进行两种操作:
1、修改某个结点的食材的美味度。
2、对于某条链,询问这条链的美味度集合中,最小的未出现的自然数是多少。即mex值。请你帮帮Haruna吧。
1<=n<=5*10^4,1<=m<=5*10^4,0<=ai<=10^9

树上莫队+分块
将树分为块,每块直径不超过,对于每个询问,按照两端点所在块的编号排序,相同编号的按照时间从小到大排序。
用桶维护每个权值出现的次数,统计块内最小没出现的数,每次询问的时候扫所有的块即可。O(1)修改 O(√n)查询
复杂度

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50100 
int n,m,a[N],blo;
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x]; 
    head[x]=cnt;
}
int fa[N],dep[N],pos[N],rm[N<<1][20],tim,Log[N<<1];
int nb,bl[N],sta[N],top,siz[N];
void dfs(int x,int pre)
{
    fa[x]=pre; dep[x]=dep[pre]+1; rm[pos[x]=++tim][0]=x;
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        dfs(to[i],x); rm[++tim][0]=x; siz[x]+=siz[to[i]];
        if(siz[x]>=blo)
        {
            ++nb; siz[x]=0;
            while(top) bl[sta[top--]]=nb;
        }
    }
    sta[++top]=x; siz[x]++;
}
int lca(int x,int y)
{
    x=pos[x],y=pos[y]; if(x>y) swap(x,y);
    int lo=Log[y-x+1];
    return dep[rm[x][lo]] < dep[rm[y-(1<<lo)+1][lo]] ?
        rm[x][lo] : rm[y-(1<<lo)+1][lo];
}
int chp[N],chb[N],cha[N];
struct node
{
    int id,x,y,b1,b2,t;
    node(){}
    node(int _id,int _x,int _y,int _t)
    {
        id=_id,x=_x,y=_y,t=_t;
        b1=bl[x],b2=bl[y];
    }
    bool operator <(const node &z)const {return b1==z.b1 ? (b2==z.b2 ? t<z.t : b2<z.b2) : b1<z.b1;}
}q[N];
int id,sb[N],lz[N],Siz,ans[N];
bool vis[N];
inline void add(int x){if(x<=n) lz[x/Siz]+=!sb[x],sb[x]++;}
inline void del(int x){if(x<=n) sb[x]--,lz[x/Siz]-=!sb[x];}
inline int getans()
{
    int i=0; while(lz[i]==Siz) ++i;
    i=i*Siz; while(sb[i]) ++i;
    return i;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(blo=1;blo*blo*blo<=n;++blo);
    for(Siz=1;Siz*Siz<=n;++Siz);
    blo=(blo-1)*(blo-1);
    int i,j,x,y;
    for(i=1;i<=n;++i) scanf("%d",a+i);
    for(i=2;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,0);
    if(top) {++nb; while(top) bl[sta[top--]]=nb;}
    for(i=2;i<=tim;++i) Log[i]=Log[i>>1]+1;
    for(i=1;i<=Log[tim];++i)
        for(j=1;j+(1<<i)-1<=tim;++j)
            rm[j][i]= dep[ rm[j][i-1] ] < dep[ rm[j+(1<<(i-1))][i-1] ] ?
                rm[j][i-1] : rm[j+(1<<(i-1))][i-1];
    // for(i=1;i<=n;++i)
    //  for(j=1;j<=n;++j)
    //      printf("%d%c",lca(i,j),j==n?'\n':' ');
    int sw; tim=0;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&sw,&x,&y);
        if(sw==0) ++tim,chp[tim]=x,chb[tim]=a[x],a[x]=cha[tim]=y;
        else ++id,q[id]=node(id,x,y,tim);
    }
    sort(q+1,q+id+1); x=y=1; add(a[1]); vis[1]=1; int z;
    for(i=1;i<=id;++i)
    {
        if(x!=q[i].x)
        {
            z=lca(x,q[i].x);
            while(x!=z)
            {
                if(vis[fa[x]]) del(a[x]),vis[x]=0;
                else add(a[fa[x]]),vis[fa[x]]=1;
                x=fa[x];
            }
            for(x=q[i].x;x!=z;x=fa[x]) sta[++top]=x;
            x=z;
            while(top)
            {
                if(vis[sta[top]]) del(a[x]),vis[x]=0;
                else add(a[sta[top]]),vis[sta[top]]=1;
                x=sta[top--];
            }
        }
        if(y!=q[i].y)
        {
            z=lca(y,q[i].y);
            while(y!=z)
            {
                if(vis[fa[y]]) del(a[y]),vis[y]=0;
                else add(a[fa[y]]),vis[fa[y]]=1;
                y=fa[y];
            }
            for(y=q[i].y;y!=z;y=fa[y]) sta[++top]=y;
            y=z;
            while(top)
            {
                if(vis[sta[top]]) del(a[y]),vis[y]=0;
                else add(a[sta[top]]),vis[sta[top]]=1;
                y=sta[top--];
            }
        }
        while(tim<q[i].t)
        {
            ++tim;
            if(vis[chp[tim]]) del(a[chp[tim]]),add(a[chp[tim]]=cha[tim]);
            else a[chp[tim]]=cha[tim];
        }
        while(tim>q[i].t)
        {
            if(vis[chp[tim]]) del(a[chp[tim]]),add(a[chp[tim]]=chb[tim]);
            else a[chp[tim]]=chb[tim];
            --tim;
        }
        ans[q[i].id]=getans();
    }
    for(i=1;i<=id;++i) printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注