分析

树上带修莫队+权值分块。
有了前两天做题的经验这题已经很好打了，但是一个细节打反了让我调了好久。
过了这题可能意味着我的莫队算法已经养成了自己的风格了。

总结一下莫队算法：
普通莫队\(N^{\frac{1}{2}}\)一块，按左端点所属块与右端点排序，复杂度\(O(N^{\frac{3}{2}})\)，处理直接移动区间端点。
带修莫队\(N^{\frac{2}{3}}\)一块，按左端点所属块、右端点所属块、时间排序，复杂度\(O(N^{\frac{5}{3}})\)，处理先移动时间，再移动区间端点。修改操作用链表存历史版本，在当前区间内才改。
树上莫队用欧拉序，用树剖求lca，两次出现不计算，lca特殊算。

代码

#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
    T data=0;
    int w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch==‘-‘)
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=10*data+ch-‘0‘,ch=getchar();
    return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;

const int MAXN=1e5+7;
int n,m;
int a[MAXN];
int block,belong[MAXN];
int l[MAXN],r[MAXN];

struct Edge
{
    int to,nx;
}E[MAXN];
int head[MAXN],ecnt;

void addedge(int x,int y)
{
    E[++ecnt].to=y;
    E[ecnt].nx=head[x],head[x]=ecnt;
}

int dep[MAXN],fa[MAXN],sz[MAXN],son[MAXN],top[MAXN];
int st[MAXN],ed[MAXN],clk;
int pot[MAXN];

void dfs1(int x,int f)
{
//  cerr<<"dfsing "<<x<<endl;
    dep[x]=dep[f]+1,fa[x]=f,sz[x]=1;
    st[x]=++clk,pot[clk]=x;
    for(int i=head[x];i;i=E[i].nx)
    {
        int y=E[i].to;
        if(y==f)
            continue;
        dfs1(y,x);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])
            son[x]=y;
    }
    ed[x]=++clk,pot[clk]=x;
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    if(!son[x])
        return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=E[i].nx)
    {
        int y=E[i].to;
        if(y==fa[x]||y==son[x])
            continue;
        dfs2(y,y);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

struct Quiz
{
    int l,r,f;
    int t,id;
    bool operator<(const Quiz&rhs)const
    {
        if(belong[l]^belong[rhs.l])
            return l<rhs.l;
        else if(belong[r]^belong[rhs.r])
            return r<rhs.r;
        else
            return t<rhs.t;
    }
}Q[MAXN];
int idxQ,ans[MAXN];
int idxC,tim[MAXN],pos[MAXN],val[MAXN],pre[MAXN],now[MAXN];


int qc,ql,qr;
int used[MAXN],cnt[MAXN],bloans[MAXN];

void change_add(int v)
{
    if(v>n)
        return;
    if(++cnt[v]==1)
        ++bloans[belong[v]];
}

void change_del(int v)
{
    if(v>n)
        return;
    if(--cnt[v]==0)
        --bloans[belong[v]];
}

void change(int p)
{
    used[p]?change_del(a[p]):change_add(a[p]); // edit 1
    used[p]^=1;
}

void modify_add(int cur)
{
    if(used[pos[cur]])
    {
        change_del(a[pos[cur]]);
    }
    a[pos[cur]]=val[cur];
    if(used[pos[cur]])
    {
        change_add(a[pos[cur]]);
    }
}

void modify_del(int cur)
{
    if(used[pos[cur]])
    {
        change_del(a[pos[cur]]);
    }
    a[pos[cur]]=pre[cur];
    if(used[pos[cur]])
    {
        change_add(a[pos[cur]]);
    }
}

void modify(int t)
{
    while(qc<idxC&&tim[qc+1]<=t)
        modify_add(++qc);
    while(qc&&tim[qc]>t)
        modify_del(qc--);
}

int query()
{
    if(!cnt[0])
        return 0;
    int i;
    for(i=1;i<=(n-1)/block+1;++i)
        if(bloans[i]!=(r[i]-l[i]+1))
            break;
    int t=i;
    for(i=l[t];i<=r[t];++i)
        if(!cnt[i])
            return i;
    return n;
}

int main()
{
//  freopen("BZOJ4129.in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);read(m);
    block=pow(n,2.0/3);
    for(int i=1;i<=n;++i)
        now[i]=read(a[i]);
    for(int i=1;i<=2*n;++i)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=(n-1)/block+1;++i)
        l[i]=(i-1)*block+1,r[i]=min(i*block,n);
    for(int i=1;i<n;++i)
    {
        int x,y;
        read(x);read(y);
        addedge(x,y);
        addedge(y,x);
    }
//  cerr<<"ecnt="<<ecnt<<endl;
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;++i)
    {
        int opt;
        read(opt);
        if(opt==0)
        {
            int u,x;
            read(u);read(x);
            tim[++idxC]=i;
            pos[idxC]=u,val[idxC]=x;
            pre[idxC]=now[u],now[u]=x;
        }
        else
        {
            int u,v;
            read(u);read(v);
            Q[++idxQ].t=i,Q[idxQ].id=idxQ;
            if(st[u]>st[v])
                swap(u,v);
            int f=lca(u,v);
            if(u==f)
                Q[idxQ].l=st[u],Q[idxQ].r=st[v];
            else
                Q[idxQ].l=ed[u],Q[idxQ].r=st[v],Q[idxQ].f=f;
        }
//      cerr<<i<<" opt="<<opt<<endl;
    }
    sort(Q+1,Q+idxQ+1);
    ql=1,qr=0,qc=0;
    for(int i=1;i<=idxQ;++i)
    {
//      cerr<<"processing "<<Q[i].id<<endl;
        modify(Q[i].t);
//      cerr<<"qc="<<qc<<endl;
        while(ql>Q[i].l)
            change(pot[--ql]);
        while(qr<Q[i].r)
            change(pot[++qr]);
        while(ql<Q[i].l)
            change(pot[ql++]);
        while(qr>Q[i].r)
            change(pot[qr--]);
        if(Q[i].f)
            change(Q[i].f);
        ans[Q[i].id]=query();
        if(Q[i].f)
            change(Q[i].f);
    }
    for(int i=1;i<=idxQ;++i)
        printf("%d\n",ans[i]);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

BZOJ4129 Haruna’s Breakfast

原文：https://www.cnblogs.com/autoint/p/9563072.html