「题解注释」P7518 [省选联考 2021 A/B 卷] 宝石

联合省选 2021 宝石 题解 - hezlik 的博客 - 洛谷博客 (luogu.com.cn)

耗时：一晚上+半个上午

代码注释：

#include<bits/stdc++.h>
using namespace std;

const int N=500000,C=21;

int Ri(){
  int x=0,y=1;
  char c=getchar();
  for (;c<'0'||c>'9';c=getchar()) if (c=='-') y=-1;
  for (;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';
  return x*y;
}

int n,m,sk,a[N+9],pre[N+9],suf[N+9],pos[N+9];
struct side{
  int y,next;
}e[N+9];
int lin[N+9],cs;

void Ins(int x,int y){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}
void Ins2(int x,int y){Ins(x,y);Ins(y,x);}

int fa[N+9],son[N+9],dep[N+9],siz[N+9],top[N+9];
int fir,up1[N+9],up[N+9][C],now[N+9];

void Dfs_ord0(int k,int fat){
  if (now[suf[a[k]]]) up[k][0]=now[suf[a[k]]]; // 上面第一个前驱元素的位置
  for (int i=1;i<C;++i) up[k][i]=up[up[k][i-1]][i-1]; // 倍增处理
  int t=now[a[k]]; // 先存下之前的值
  now[a[k]]=k; // 更新 now 数组
  if (now[fir]) up1[k]=now[fir]; // 记录开始位置
  fa[k]=fat; // 记录父亲
  dep[k]=dep[fat]+1; // 更新深度
  siz[k]=1; // 记录大小
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fat){  
      Dfs_ord0(e[i].y,k);
      siz[k]+=siz[e[i].y];
      if (siz[e[i].y]>siz[son[k]]) son[k]=e[i].y; // （猜测）轻重链剖分
    }
  now[a[k]]=t; // 回溯
}

void Dfs_ord1(int k,int t){ // 处理链顶，轻重链剖分
  top[k]=t;
  if (son[k]) Dfs_ord1(son[k],t);
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fa[k]&&e[i].y^son[k]) Dfs_ord1(e[i].y,e[i].y);
}

int Query_lca(int x,int y){ // 找 lca
  for (;top[x]^top[y];x=fa[top[x]])
    if (dep[top[x]]<dep[top[y]]) swap(x,y);
  return dep[x]<dep[y]?x:y;
}

int cq,ans[N+9];
vector<int>qc[N+9],qid[N+9],q[N+9];

int uni[N+9],sz[N+9],col[N+9],rot[N+9];

int Query_uni(int k){return k==uni[k]?k:Query_uni(uni[k]);} // 找祖先

void Dfs_ans(int k){
  for (int vs=qc[k].size(),i=0;i<vs;++i){
    int c=qc[k][i],t=qid[k][i];
    uni[t]=t; // 并查集祖先
    sz[t]=1; // 并查集大小
    col[t]=c; // 并查集颜色，该颜色为下一个要查找的颜色
    rot[c]?(uni[t]=rot[c],++sz[rot[c]]):rot[c]=t; // 合并
  }
  int x=rot[a[k]]; // 当前颜色的祖先
  rot[a[k]]=0; // 这个颜色已经被收入囊中了
  int c=suf[a[k]],y=rot[c]; // c 后继颜色，y 是 c 的祖先
  if (x){
    if (!y) rot[c]=x,col[x]=c; // 没有下一个颜色的祖先
    else if (sz[x]<sz[y]){ // 启发式合并
      uni[x]=y;
      sz[y]+=sz[x];
    }else{
      uni[y]=rot[c]=x;
      sz[x]+=sz[y];
      col[x]=c; // 此时的颜色为 c
    }
  }
  for (int vs=q[k].size(),i=0;i<vs;++i){
    int t=col[Query_uni(q[k][i])]; // 查询当前询问的问题的祖先的颜色
    ans[q[k][i]]=t?pos[t]-1:sk;
  }
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fa[k]) Dfs_ans(e[i].y);
  if (x){ // 以下全为撤销操作
    if (!y) rot[c]=0,col[x]=a[k];
    else if (rot[c]==y){
      uni[x]=x;
      sz[y]-=sz[x];
    }else{
      uni[y]=rot[c]=y;
      sz[x]-=sz[y];
      col[x]=a[k];
    }
  }
  rot[a[k]]=x;
  for (int vs=qc[k].size(),i=0;i<vs;++i){
    int c=qc[k][i],t=qid[k][i];
    rot[c]==t?rot[c]=0:--sz[uni[t]];
  }
}

int main(){
  n=Ri();m=Ri();sk=Ri();
  for (int i=1;i<=sk;++i) a[i]=Ri();
  fir=a[1];
  for (int i=1;i<=sk;++i){
    pre[a[i]]=a[i-1]; // 记录前驱
    suf[a[i]]=a[i+1]; // 记录后继
    pos[a[i]]=i; // 记录位置
  }
  for (int i = 1; i <= sk; ++ i) {
    cout << pre[a[i]] << ' ' << suf[a[i]] << "col" << '\n';
  }
  for (int i=1;i<=n;++i) a[i]=Ri();
  for (int i=1;i<n;++i){
    int x,y;
    x=Ri();y=Ri();
    Ins2(x,y);
  }
  Dfs_ord0(1,0);
  Dfs_ord1(1,1);
  cq=Ri();
  for (int i=1;i<=cq;++i){
    int x,y,z;
    x=Ri();y=Ri();
    z=Query_lca(x,y);
    if (dep[up1[x]]<=dep[z]){
      qc[z].push_back(fir); // 下一个要找哪个类型的宝石
      qid[z].push_back(i); // 存储问题的编号
      q[y].push_back(i);
    } else{
      int t=up1[x];
      for (int j=C-1;j>=0;--j)
        if (dep[up[t][j]]>dep[z]) t=up[t][j]; // 跳倍增环节
      t=a[t];
      if (suf[t]){ // 当前元素有后继
        qc[z].push_back(suf[t]); // 下一个要找哪个类型的宝石
        qid[z].push_back(i); // 存储问题的编号
        q[y].push_back(i);
      }else ans[i]=m; // 记录答案
    }
  }
  Dfs_ans(1);
  for (int i=1;i<=cq;++i)
    printf("%d\n",ans[i]);
  return 0;
}