BZOJ 4129: Haruna’s Breakfast【树上带修莫队】

                                           4129: Haruna’s Breakfast

                                                               Time Limit: 10 Sec  Memory Limit: 128 MB

Description

 Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵

树上，每个结点都有一样食材，Shimakaze要考验一下她。

每个食材都有一个美味度，Shimakaze会进行两种操作：

1、修改某个结点的食材的美味度。

2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。

请你帮帮Haruna吧。

Input

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。

第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。

接下来n-1行，每行包括两个整数u，v，代表树上的一条边。

接下来m 行，每行包括三个整数

0 u x 代表将结点u的食材的美味度修改为 x。

1 u v 代表询问以u，v 为端点的链的mex值。

Output

对于每次询问，输出该链的mex值。

Sample Input

10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7

Sample Output

0
1
2
2
3

HINT

1<=n<=5*10^4

1<=m<=5*10^4

0<=ai<=10^9

 

【题目链接】 数颜色

【参考博客】 大米饼

【题意】

有一棵树，有多个询问和修改，可以单点修改一个节点的权值，询问(u,v)表示u到v的路径上，求出最小的没有出现的自然数。

【思路】

与普通带修莫队相比，主要是树上如何分块：做法是用栈维护当前节点作为父节点访问它的子节点，当从栈顶到父节点的距离大于blo时，弹出这部分元素分为一块。

 

#include <cstdio>
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef  long long ll;
const int maxn = 50005;
const ll mod = 1e9+7;
const int INF = 1e9;
const double eps = 1e-6;

int n,m,blo,tot,tt[maxn];
int a[maxn];
int fa[maxn][20],dep[maxn],head[maxn];
int be[maxn],vis[maxn],Ans[maxn];
int st[maxn],tag,top;

struct node
{
    int u,v,ti,id;
    node(int u=0,int v=0,int ti=0,int id=0):u(u),v(v),ti(ti),id(id){}
}q[maxn];

struct node2
{
    int pos,New,old;
    node2(int pos=0,int New=0,int old=0):pos(pos),New(New),old(old){}
}c[maxn];

bool cmp(node a,node b)
{
    return be[a.u]==be[b.u]?(be[a.v]==be[b.v]?a.ti<b.ti:be[a.v]<be[b.v]):be[a.u]<be[b.u];
}

struct mm
{
    int v,next;
}e[maxn*2];

void add(int u,int v)
{
    e[tot].v=v;
    e[tot].next=head[u];
    head[u]=tot++;
}

void dfs(int u)
{
    for(int i=1;i<=19;i++)
    {
        if((1<<i)>dep[u]) break;
        else fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    int bo=top;
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa[u][0]) continue;
        fa[v][0]=u,dep[v]=dep[u]+1;
        dfs(v);
        if(top-bo>=blo){tag++;while(top!=bo)be[st[top--]]=tag;}
    }
    st[++top]=u;
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    int tmp=dep[x]-dep[y];
    for(int i=0;i<=16;i++) if((1<<i)&tmp) x=fa[x][i];
    if(x==y) return x;
    for(int i=16;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    }
    return x==y?x:fa[x][0];
}

struct Datalock
{
    struct _blo{int l,r;}b[1005];
    int n,m,unit,Be[maxn],num[maxn],sum[1005];
    void init()
    {
        mst(num,0);
        mst(sum,0);
        unit=(int)sqrt(n*1.0),m=(n-1)/unit+1;
        for(int i=1;i<=n;i++) Be[i]=(i-1)/unit+1;
        for(int i=1;i<=m;i++) b[i].l=(i-1)*unit+1,b[i].r=min(i*unit,n);
    }
    void add(int x) {if(x<=n) sum[Be[x]]+=(++num[x])==1;}
    void del(int x) {if(x<=n) sum[Be[x]]-=(--num[x])==0;}
    int mex()
    {
        for(int i=1;i<=m;i++)
        {
            if(sum[i]!=b[i].r-b[i].l+1)
            {
                for(int j=b[i].l;j<=b[i].r;j++) if(!num[j]) return j;
                return -1;
            }
        }
    }
}Data;

void revise(int pos,int d)
{
    if(vis[pos]) Data.del(a[pos]),Data.add(d);
    a[pos]=d;
}

void run(int pos)
{
    if(vis[pos]) Data.del(a[pos]),vis[pos]=0;
    else Data.add(a[pos]),vis[pos]=1;
}

void move(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) run(x),x=fa[x][0];
    while(x!=y) run(x),run(y),x=fa[x][0],y=fa[y][0];
}

void modui(int kk)
{
    int nowT=0;
    int u=1,v=1;
    for(int i=0;i<kk;i++)
    {
        while(q[i].ti>nowT) nowT++,revise(c[nowT].pos,c[nowT].New);
        while(q[i].ti<nowT) revise(c[nowT].pos,c[nowT].old),nowT--;

        if(q[i].u!=u) move(u,q[i].u),u=q[i].u;
        if(q[i].v!=v) move(v,q[i].v),v=q[i].v;
        int tmp=LCA(u,v);run(tmp);
        Ans[q[i].id]=Data.mex()-1;run(tmp);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    blo=(int)pow(n,0.45);
    mst(head,-1);
    mst(vis,0);
    tot=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),tt[i]=++a[i];
    for(int i=2;i<=n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    tag=0;
    dfs(1);
    while(top)be[st[top--]]=tag;
    int cnt=0,t=0;
    for(int i=0;i<m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op) q[cnt]=node(x,y,t,cnt),cnt++;
        else {t++;c[t]=node2(x,y+1,tt[x]);tt[x]=y+1;}
    }
    Data.n=n+1;Data.init();
    sort(q,q+cnt,cmp),modui(cnt);
    for(int i=0;i<cnt;i++) printf("%d\n",Ans[i]);
}