ZigZagK

Never give up fighting!

[随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解

题目概述

给出一棵 \(n​\) 个节点的树,每个节点有权值,一条路径上的对称数定义为最小的出现次数为偶数(包括 \(0​\) )的数,现在给出 \(m​\) 个询问 \((x,y)​\) 表示询问 \((x,y)​\) 路径上的对称数。

解题报告

奇数次偶数次想到异或,我们先给每个权值配对上一个随机数,然后求出路径上的异或值(主席树),就可以得到这条路径上的权值信息。不过这样还是没法做,但是我们发现这样可以判断一段权值范围内是否均为奇数次。

所以考虑二分 \(mid\) ,验证 \([1,mid]\) 是否存在偶数次(不是均为奇数次)就行了。


如果你用二分+主席树查询,效率为 \(O(mlog_2^2n)\) ,然后你就会成功TLE……正确姿势是在主席树上二分,其实也不难理解,就是验证 \(mid\) 然后往左走或者往右走,这样就是 \(O(mlog_2n)\) 了。

ps:有一种特殊数据:树退化成链,且链上权值涵盖所有权值,这样就会导致在主席树上无法查找到答案,所以主席树右边界要多开 \(1\) ,没有注意到导致我WA了若干发TAT。

示例程序

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000,maxa=200001,maxt=1e7,Log=18;

int te,n,m,a[maxn+5],fa[maxn+5][Log+5],dep[maxn+5];ULL ha[maxa+5],pre[maxa+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5],lca;
int len,ro[maxn+5],ls[maxt+5],rs[maxt+5];ULL sum[maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline ULL Rand(){
    static ULL now;now=((ULL)rand()<<48)+((ULL)rand()<<32)+((ULL)rand()<<16)+rand();
    now+=((ULL)(rand()&1)<<47)+((ULL)(rand()&1)<<31)+((ULL)(rand()&1)<<15);return now;
}
#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
#define newnode(l,r,s) (ls[len]=(l),rs[len]=(r),sum[len]=(s),len++)
int Build(int L,int R){
    int now=newnode(0,0,0);if (L==R) return now;int mid=L+(R-L>>1);
    ls[now]=Build(L,mid);rs[now]=Build(mid+1,R);return now;
}
int Insert(int p,int pos,ULL k,int l=1,int r=maxa){
    int now=newnode(ls[p],rs[p],sum[p]^k);if (l==r) return now;int mid=l+(r-l>>1);
    if (pos<=mid) ls[now]=Insert(ls[p],pos,k,l,mid); else rs[now]=Insert(rs[p],pos,k,mid+1,r);return now;
}
int Find(int A,int B,ULL SA=0,ULL SB=0,int l=1,int r=maxa){
    if (l==r) return l;int mid=l+(r-l>>1);ULL now=SA^sum[ls[A]]^SB^sum[ls[B]]^(a[lca]>mid?0:ha[a[lca]]);
    if (now^pre[mid]) return Find(ls[A],ls[B],SA,SB,l,mid);
    return Find(rs[A],rs[B],SA^sum[ls[A]],SB^sum[ls[B]],mid+1,r);
}
void Dfs(int x,int pre=0){
    ro[x]=Insert(ro[pre],a[x],ha[a[x]]);fa[x][0]=pre;dep[x]=dep[pre]+1;
    for (int j=1;j<=Log;j++) fa[x][j]=fa[fa[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int j=Log;~j&&dep[x]>dep[y];j--) if (dep[fa[x][j]]>=dep[y]) x=fa[x][j];
    if (x==y) return x;
    for (int j=Log;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
    return fa[x][0];
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    srand(19260817);for (int i=1;i<=200000;i++) ha[i]=Rand(),pre[i]=pre[i-1]^ha[i];
    for (readi(te);te;te--){
        len=0;E=0;memset(lnk,0,sizeof(lnk));
        readi(n);readi(m);for (int i=1;i<=n;i++) readi(a[i]);
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
        ro[0]=Build(1,maxa);Dfs(1);
        for (int t=1,x,y;t<=m;t++){
            readi(x);readi(y);lca=LCA(x,y);
            printf("%d\n",Find(ro[x],ro[y]));
        }
    }
    return 0;
}
点赞

发表评论

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

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]