P7518 [省选联考 2021 A/B 卷] 宝石解题报告

解题报告

P7518 [省选联考 2021 A/B 卷] 宝石解题报告：

更好的阅读体验

题意

给定一颗$n$个点的带点权的树，以及一个长度为$c$的匹配序列，（点权与序列的值域为$[1,m]$），$q$次询问，每次询问$x$到$y$的有向路径与匹配序列匹配的最长前缀的长度。

$1\leqslant n,q\leqslant 2\times 10^5,1\leqslant c\leqslant m\leqslant 5\times 10^4$。

分析

考场写了一个5k的树分块$O((n+q+m\alpha(n))\sqrt{n})$的做法，然后被卡常卡成$35pts$就很离谱。

（该部分可略过）
在树上撒$\sqrt{n}$个关键点，每个点与其祖先里的关键点距离为$\sqrt{n}$，然后发现可以把询问的路径分成$4$个散块和$2$个整块，散块暴力跳（记得把$lca$到另一端的路径反向，我因为反向调了一个多小时），整块可以预处理第$i$个关键点跳到祖先关键点这一条链，从位置$j$开始匹配能匹配到哪里，不难发现（我想了十几分钟）可以用并查集维护所有位置同时进行匹配，同样还要反过来做一遍。
具体地，可以把整块对应的链上权值序列当成一个普通的序列，与长度为m的串进行匹配，然后对于每个位置可以维护它在匹配的过程中到了哪一个位置，不难发现把相同的位置在匹配的过程中会不断合并，那么直接上并查集就好了。

然后发现$O(n\log n+q\log n\log m)$的树上倍增好想好写的一批。

首先进行一次转化，把点权转化为在序列中的位置，这样好做一些。

考虑预处理$x$向上跳第一个点权为$c$的点的位置，这是一个经典问题，在树上用主席树完成就好了，时空复杂度均为$O(n\log m)$。

然后再按照树上倍增的套路预处理一个$inc_{x,k}$表示$x$向上跳，从当前点权$w_x$匹配到$w_x+2^k$的位置，以及$dec_{x,k}$表示$x$向上跳，从当前点权$w_x$反向匹配到$w_x-2^k$的位置。我们首先用主席树帮忙处理出$inc_{x,0}$与$dec_{x,0}$，然后直接合并就好了。

对于询问$(x,y)$，设$z=lca(x,y)$，考虑让$x$跳到第一个点权为$1$的点开始匹配（需要特判一下跳出$x\rightarrow z$这一条链的情况），然后用树上倍增暴力跳$inc$数组直到跳出$x\rightarrow z$这一条链。

之后，我们发现$y$不能进行类似的操作，因为我们不知道结尾的点权为多少，不难发现答案具有可二分性，直接二分最后的位置，然后按照上面的方法跳$dec$就好了。

时间复杂度：$O(n\log n+q\log n\log m)$。

代码

常数似乎很大。

#include<stdio.h>
const int maxm=50005,maxn=200005,maxe=maxn<<1,maxk=25;
int n,m,c,e,q,tot;
int p[maxm],w[maxn],start[maxn],to[maxe],then[maxe],fore[maxn][maxk],dep[maxn],pos[maxm];
int lc[maxn*maxk],rc[maxn*maxk],res[maxn*maxk],rt[maxn],inc[maxn][maxk],dec[maxn][maxk];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void build(int l,int r,int &now){
    if(now==0)
        now=++tot;
    if(l==r){
        res[now]=-1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,lc[now]),build(mid+1,r,rc[now]);
}
inline int newnode(int x){
    tot++,lc[tot]=lc[x],rc[tot]=rc[x],res[tot]=res[x];
    return tot;
}
void update(int l,int r,int &now,int pos,int v){
    now=newnode(now);
    if(l==r){
        res[now]=v;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
        update(l,mid,lc[now],pos,v);
    else update(mid+1,r,rc[now],pos,v);
}
int query(int l,int r,int now,int pos){
    if(l==r)
        return res[now];
    int mid=(l+r)>>1;
    if(pos<=mid)
        return query(l,mid,lc[now],pos);
    return query(mid+1,r,rc[now],pos);
}
void dfs(int x,int last){
    dep[x]=dep[last]+1,fore[x][0]=last,rt[x]=rt[last];
    if(w[x]!=-1)
        update(1,c,rt[x],w[x],x);
    inc[x][0]=(w[x]==-1||w[x]==c)? -1:query(1,c,rt[x],w[x]+1);
    dec[x][0]=(w[x]==-1||w[x]==1)? -1:query(1,c,rt[x],w[x]-1);
    for(int i=1;i<=20;i++){
        fore[x][i]=fore[fore[x][i-1]][i-1];
        inc[x][i]=inc[x][i-1]==-1? -1:inc[inc[x][i-1]][i-1];
        dec[x][i]=dec[x][i-1]==-1? -1:dec[dec[x][i-1]][i-1];
    }
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])
        a+=b,b=a-b,a-=b;
    for(int i=20;i>=0;i--)
        if(dep[fore[a][i]]>=dep[b])
            a=fore[a][i];
    if(a==b)
        return a;
    for(int i=20;i>=0;i--)
        if(fore[a][i]!=fore[b][i])
            a=fore[a][i],b=fore[b][i];
    return fore[a][0];
}
int check(int x,int z,int now,int goal){
    x=query(1,c,rt[x],goal);
    if(x==-1||dep[x]<dep[z])
        return 0;
    for(int i=20;i>=0;i--)
        if(dec[x][i]!=-1&&dep[dec[x][i]]>dep[z])
            x=dec[x][i];
    return w[x]<=now;
}
int main(){
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=m;i++)
        pos[i]=-1;
    for(int i=1;i<=c;i++)
        scanf("%d",&p[i]),pos[p[i]]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]),w[i]=pos[w[i]];
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    build(1,c,rt[0]),dfs(1,0);
    scanf("%d",&q);
    while(q--){
        int x,y,z,res=0;
        scanf("%d%d",&x,&y),z=lca(x,y);
        x=query(1,c,rt[x],1);
        if(x!=-1&&dep[x]>=dep[z]){
            for(int i=20;i>=0;i--)
                if(inc[x][i]!=-1&&dep[inc[x][i]]>=dep[z])
                    x=inc[x][i];
            res=w[x];
        }
        int L=res,R=c+1;
        while(L+1<R){
            int mid=(L+R)>>1;
            if(check(y,z,res+1,mid))
                L=mid;
            else R=mid;
        }
        printf("%d\n",L);
    }
    return 0;
}

省选联考A卷全部题解可见：2021省选联考A卷解题报告