Gym - 100962F： Frank Sinatra （树上莫队+bitset）

题意：给定一棵树，带边权。然后Q次询问，每次给出(u,v)，求这个路径上最小的未出现的边权。

思路：树上莫队，求mex可以用分块或者bitset，前者可能会快一点。莫队过程：求出欧拉序，即记录dfs的in和out时间戳。然后摊平成数组，在数组上进行莫队。

一般的莫队需要单独考虑LCA，因为LCA不在这个区间里。但是由于这里是边权，用儿子代替边权，所以LCA本来就不用考虑。

这个序列里，有效的部分是出现奇数次的，所以用vis记录奇偶性，如果是奇，表示加；偶表示删。

如果想再快一点，可以把bitset改为分块；以及，用王室联邦分块法（即后序遍历，这样可以保证一个块更近一些）。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

bitset<maxn>S; int num[maxn],val[maxn],ans[maxn];

int Laxt[maxn],Next[maxn],To[maxn],len[maxn],cnt;

int p[maxn],L[maxn],R[maxn],times,B,N,Q,vis[maxn];

struct in{

    int l,r,id;

    bool friend operator <(in w,in v){

        if(w.l/B!=v.l/B) return w.l<v.l;

        return w.r<v.r;

    }

}s[maxn];

void add(int u,int v,int w)

{

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; len[cnt]=w;

}

void dfs(int u,int f)

{

    p[++times]=u; L[u]=times;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i]; if(v==f) continue;

        val[v]=len[i]; dfs(v,u);

    }

    p[++times]=u; R[u]=times;

}

void fcy(int pos)

{

    pos=p[pos];

    if(val[pos]>N) return ;

    vis[pos]^=;

    if(vis[pos]) {

        num[val[pos]]++;

        if(num[val[pos]]==) S[val[pos]]=;

    }

    else {

        num[val[pos]]--;

        if(num[val[pos]]==) S[val[pos]]=;

    }

}

void solve()

{

    sort(s+,s+Q+);

    int l=s[].l,r=s[].l-;

    rep(i,,Q){

        while(l<s[i].l) fcy(l++);

        while(l>s[i].l) fcy(--l);

        while(r<s[i].r) fcy(++r);

        while(r>s[i].r) fcy(r--);

        ans[s[i].id]=S._Find_first();

    }

}

int main()

{

    int u,v,w;

    S.set(); //没出现的就是1

    scanf("%d%d",&N,&Q);

    B=(int)sqrt(N+N);

    rep(i,,N-){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    dfs(,); val[]=N+;

    rep(i,,Q) {

        scanf("%d%d",&u,&v);

        if(L[u]>L[v]) swap(u,v);

        s[i].l=R[u]; s[i].r=L[v]; s[i].id=i;

    }

    solve();

    rep(i,,Q) printf("%d\n",ans[i]);

    return ;

}

王室联邦写法：但跑出来这个更慢？

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

bitset<maxn>S; int num[maxn],val[maxn],ans[maxn];

int Laxt[maxn],Next[maxn],To[maxn],len[maxn],cnt;

int p[maxn],L[maxn],R[maxn],times,B,N,Q,vis[maxn];

int q[maxn],top,g[maxn],group;

struct in{

    int l,r,id;

    bool friend operator <(in w,in v){

        if(g[p[w.l]]!=g[p[v.l]]) return g[p[w.l]]<g[p[v.l]];

        return g[p[w.r]]<g[p[v.r]];

    }

}s[maxn];

void add(int u,int v,int w)

{

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; len[cnt]=w;

}

void dfs(int u,int f)

{

    p[++times]=u; L[u]=times;

    int now=top;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i]; if(v==f) continue;

        val[v]=len[i]; dfs(v,u);

        if(top-now>=B){

            group++;

            while(top!=now) g[q[top--]]=group;

        }

    }

    q[++top]=u;

    p[++times]=u; R[u]=times;

}

void fcy(int pos)

{

    pos=p[pos];

    if(val[pos]>N) return ;

    vis[pos]^=;

    if(vis[pos]) {

        num[val[pos]]++;

        if(num[val[pos]]==) S[val[pos]]=;

    }

    else {

        num[val[pos]]--;

        if(num[val[pos]]==) S[val[pos]]=;

    }

}

void solve()

{

    sort(s+,s+Q+);

    int l=s[].l,r=s[].l-;

    rep(i,,Q){

        while(l<s[i].l) fcy(l++);

        while(l>s[i].l) fcy(--l);

        while(r<s[i].r) fcy(++r);

        while(r>s[i].r) fcy(r--);

        ans[s[i].id]=S._Find_first();

    }

}

int main()

{

    int u,v,w;

    S.set(); //没出现的就是1

    scanf("%d%d",&N,&Q);

    B=(int)sqrt(N+N);

    rep(i,,N-){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    dfs(,); val[]=N+;

    while(top) g[q[top--]]=group;

    rep(i,,Q) {

        scanf("%d%d",&u,&v);

        if(L[u]>L[v]) swap(u,v);

        s[i].l=R[u]; s[i].r=L[v]; s[i].id=i;

    }

    solve();

    rep(i,,Q) printf("%d\n",ans[i]);

    return ;

}

巴特西

Gym - 100962F： Frank Sinatra （树上莫队+bitset）

最新文章

热门文章