【题解】CF1479D Odd Mineral Resource

· · 题解

目录

题意简述

给定一棵 n 个节点的树，i 号节点的权值为 a_i。

有 q 次询问，每次询问给定 u,v,l,r，表示询问是否存在 c 满足 l \le c \le r 且 u,v 两点路径上恰好有奇数个权值为 c 的节点。若存在，输出任意一个满足条件的 c，否则输出 -1。

数据范围：n,q \le 3 \times 10^5，1 \le a_i \le n，1 \le l \le r \le n。

思路一

看完题面，很容易想到树上莫队，用以维护当前每种权值出现的奇偶性，但是如何求得区间 [l,r] 中某个出现奇数次的值呢？

大常数 O(n\sqrt{q}\log{n}+q\log{n}) 算法

我们可以将新增的出现奇数次的权值放进 set 里，将新增的出现偶数次的权值从 set 中删除，查询时二分查找即可。单次修改和单次查询都是大常数 O(\log{n}) 的，不足以通过此题。

小常数 O(n\sqrt{q}\log{n}+q\log{n}) 算法

我们也可以在树状数组上将新增的出现奇数次和偶数次的权值对应位置 +1 和 -1，单次修改是小常数 O(\log{n}) 的；查询时在树状数组上二分即可，时间复杂度为 O(\log^2{n}) 或 O(\log{n})（如果不会 O(\log{n}) 的做法，可以点此处学习）。

由于 q\log^2{n}<n\sqrt{q}\log{n}（即瓶颈为前半部分），加之常数问题，理论上来说跑得会比前一种快一些，但依然会 Time limit exceeded on test 7。

代码

由于是赛时写的，写得丑请见谅。（结构体变量 l,r,L,R 和局部变量 L,R,ll,rr 不要弄混了，本人因为弄混在赛时获得了 Wrong answer on pretest 1 的好成绩——当然这里已经修正）

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    const int buffer_size=1e5+5;
    char buf[buffer_size],*S,*T;
    bool flag_EOF;
    inline char read_char()
    {
        if(S==T)
            T=(S=buf)+fread(buf,1,buffer_size,stdin);
        return S!=T?*(S++):EOF;
    }
    inline int read_int()
    {
        int flag=1;
        char c=read_char();
        while(c<'0'||c>'9')
        {
            if(c==EOF)
            {
                flag_EOF=true;
                return 0;
            }
            flag=(c=='-'?-1:1);
            c=read_char();
        }
        int x=0;
        while(c>='0'&&c<='9')
        {
            x=x*10+(c^48);
            c=read_char();
        }
        return x*flag;
    }
    char st[13];
    int _top;
    inline void Write(int x)
    {
        if(!x)
        {
            putchar('0');
            return;
        }
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        while(x)
        {
            st[++_top]=x%10+'0';
            x/=10;
        }
        while(_top>0)
            putchar(st[_top--]);
    }
}
int n,m;
const int max_n=3e5+5;
vector<int> edge[max_n];
int id[max_n<<1],Time,dfn[max_n][2];
void dfs(int x,int fa)
{
    dfn[x][0]=++Time;
    id[Time]=x;
    for(int i=0;i<int(edge[x].size());++i)
    {
        int y=edge[x][i];
        if(y!=fa)
            dfs(y,x);
    }
    dfn[x][1]=++Time;
    id[Time]=x;
}
int dep[max_n],sz[max_n],son[max_n],fath[max_n];
void dfs1(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]=1;
    son[x]=-1;
    fath[x]=fa;
    int max_sz=0;
    for(int i=0;i<int(edge[x].size());++i)
    {
        int y=edge[x][i];
        if(y!=fa)
        {
            dfs1(y,x);
            sz[x]+=sz[y];
            if(sz[y]>max_sz)
            {
                max_sz=sz[y];
                son[x]=y;
            }
        }
    }
}
int _top[max_n];
void dfs2(int x,int top_now)
{
    _top[x]=top_now;
    if(son[x]!=-1)
        dfs2(son[x],top_now);
    for(int i=0;i<int(edge[x].size());++i)
    {
        int y=edge[x][i];
        if(y!=fath[x]&&y!=son[x])
            dfs2(y,y);
    }
}
inline int get_LCA(int x,int y)
{
    while(_top[x]!=_top[y])
    {
        if(dep[_top[x]]<dep[_top[y]])
            swap(x,y);
        x=fath[_top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
namespace BIT
{
    int c[max_n];
    inline void modify(int k,int v)
    {
        for(int i=k;i<=n;i+=i&(-i))
            c[i]+=v;
    }
    inline int query(int k)
    {
        int res=0;
        for(int i=k;i>0;i-=i&(-i))
            res+=c[i];
        return res;
    }
}
const int max_m=3e5+5;
int ans[max_m];
struct Query
{
    int l,blo,r,lca,L,R,id;
}q[max_m];
inline bool cmp(const Query &a,const Query &b)
{
    return a.blo!=b.blo?a.blo<b.blo:a.r<b.r;
}
int a[max_n];
bool odd[max_n];
inline void work(int x)
{
    if(odd[a[x]])
    {
        BIT::modify(a[x],-1);
        odd[a[x]]=false;
    }
    else
    {
        BIT::modify(a[x],1);
        odd[a[x]]=true;
    }
}
int main()
{
    n=IO::read_int(),m=IO::read_int();
    for(int i=1;i<=n;++i)
        a[i]=IO::read_int();
    for(int i=1;i<=n-1;++i)
    {
        int x=IO::read_int(),y=IO::read_int();
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,0);
    dfs1(1,0);
    dfs2(1,1);
    int s=int(2*n/sqrt(m));
    for(int i=1;i<=m;++i)
    {
        int u=IO::read_int(),v=IO::read_int(),l=IO::read_int(),r=IO::read_int();
        if(dfn[u][0]>dfn[v][0])
            swap(u,v);
        int p=get_LCA(u,v);
        if(p==u)
            q[i].l=dfn[u][0],q[i].r=dfn[v][0];
        else
            q[i].l=dfn[u][1],q[i].r=dfn[v][0],q[i].lca=p;
        q[i].L=l,q[i].R=r,q[i].id=i;
        q[i].blo=(q[i].l-1)/s+1;
    }
    sort(q+1,q+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i)
    {
        while(L<q[i].l)
            work(id[L++]);
        while(L>q[i].l)
            work(id[--L]);
        while(R<q[i].r)
            work(id[++R]);
        while(R>q[i].r)
            work(id[R--]);
        if(q[i].lca)
            work(q[i].lca);
        int v1=BIT::query(q[i].L-1);
        int v2=BIT::query(q[i].R);
        if(v1==v2)
            ans[q[i].id]=-1;
        else
        {
            int ll=q[i].L,rr=q[i].R,mid,res=q[i].R;
            while(ll<=rr)
            {
                mid=(ll+rr)>>1;
                if(BIT::query(mid)>=v1+1)
                    res=mid,rr=mid-1;
                else
                    ll=mid+1;
            }
            ans[q[i].id]=res;
        }
        if(q[i].lca)
            work(q[i].lca);
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

正解 O(n\sqrt{q}+q\sqrt{n})

注意到时间复杂度的瓶颈在于修改，即要求单次修改 O(1)，单次询问不超过 O(\sqrt{n})，使用分块即可。

具体来说，用一个 bool 数组记录每种权值是否出现奇数次，再用一个 int 数组记录每一块有多少个出现奇数次的权值。修改时把当前这种权值及其所在块修改；查询时暴力扫描左右两端的部分，中间块若出现个数 >0 则扫描。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int max_n=3e5+5;
vector<int> edge[max_n];
int id[max_n<<1],Time,dfn[max_n][2];
void dfs(int x,int fa)
{
    dfn[x][0]=++Time;
    id[Time]=x;
    for(int i=0;i<int(edge[x].size());++i)
    {
        int y=edge[x][i];
        if(y!=fa)
            dfs(y,x);
    }
    dfn[x][1]=++Time;
    id[Time]=x;
}
int dep[max_n],sz[max_n],son[max_n],fath[max_n];
void dfs1(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]=1;
    son[x]=-1;
    fath[x]=fa;
    int max_sz=0;
    for(int i=0;i<int(edge[x].size());++i)
    {
        int y=edge[x][i];
        if(y!=fa)
        {
            dfs1(y,x);
            sz[x]+=sz[y];
            if(sz[y]>max_sz)
            {
                max_sz=sz[y];
                son[x]=y;
            }
        }
    }
}
int _top[max_n];
void dfs2(int x,int top_now)
{
    _top[x]=top_now;
    if(son[x]!=-1)
        dfs2(son[x],top_now);
    for(int i=0;i<int(edge[x].size());++i)
    {
        int y=edge[x][i];
        if(y!=fath[x]&&y!=son[x])
            dfs2(y,y);
    }
}
inline int get_LCA(int x,int y)
{
    while(_top[x]!=_top[y])
    {
        if(dep[_top[x]]<dep[_top[y]])
            swap(x,y);
        x=fath[_top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
const int max_m=3e5+5;
int ans[max_m];
struct Query
{
    int l,blo,r,lca,L,R,id;
}q[max_m];
inline bool cmp(const Query &a,const Query &b)
{
    return a.blo!=b.blo?a.blo<b.blo:a.r<b.r;
}
int a[max_n];
bool odd[max_n];
int sn;
const int max_sqrt_n=548+5;
int cnt[max_sqrt_n];
inline void work(int x)
{
    if(odd[a[x]])
    {
        --cnt[(a[x]-1)/sn+1];
        odd[a[x]]=false;
    }
    else
    {
        ++cnt[(a[x]-1)/sn+1];
        odd[a[x]]=true;
    }
}
inline int query(int l,int r)
{
    int id_l=(l-1)/sn+1,id_r=(r-1)/sn+1;
    if(id_l==id_r)
    {
        for(int i=l;i<=r;++i)
        {
            if(odd[i])
                return i;
        }
        return -1;
    }
    for(int i=l;i<=id_l*sn;++i)
    {
        if(odd[i])
            return i;
    }
    for(int i=(id_r-1)*sn+1;i<=r;++i)
    {
        if(odd[i])
            return i;
    }
    for(int i=id_l+1;i<=id_r-1;++i)
    {
        if(cnt[i])
        {
            for(int j=(i-1)*sn+1;j<=i*sn;++j)
            {
                if(odd[j])
                    return j;
            }
        }
    }
    return -1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",a+i);
    for(int i=1;i<=n-1;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,0);
    dfs1(1,0);
    dfs2(1,1);
    sn=int(sqrt(n));
    int s=int(2*n/sqrt(m));
    for(int i=1;i<=m;++i)
    {
        int u,v,l,r;
        scanf("%d%d%d%d",&u,&v,&l,&r);
        if(dfn[u][0]>dfn[v][0])
            swap(u,v);
        int p=get_LCA(u,v);
        if(p==u)
            q[i].l=dfn[u][0],q[i].r=dfn[v][0];
        else
            q[i].l=dfn[u][1],q[i].r=dfn[v][0],q[i].lca=p;
        q[i].L=l,q[i].R=r,q[i].id=i;
        q[i].blo=(q[i].l-1)/s+1;
    }
    sort(q+1,q+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i)
    {
        while(L<q[i].l)
            work(id[L++]);
        while(L>q[i].l)
            work(id[--L]);
        while(R<q[i].r)
            work(id[++R]);
        while(R>q[i].r)
            work(id[R--]);
        if(q[i].lca)
            work(q[i].lca);
        ans[q[i].id]=query(q[i].L,q[i].R);
        if(q[i].lca)
            work(q[i].lca);
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

PS：出题人应该是想放这种解法过的，因为另外一种时间复杂度更优秀的正解只需 1s 左右，但时限是 5s，而这份代码最大用时 4742 ms。

思路二

分析 + 题解

题目的要求相当于“奇数次算出现，偶数次算没出现”，这跟异或的性质类似，考虑用异或值来刻画询问是否有解。

定义 f(u,v,l,r) 表示 u 到 v 路径上权值 \in [l,r] 的权值的异或和，则若无解，必有 f(u,v,l,r) = 0。进一步，若 f(u,v,l,r) \neq 0，必然有解。

但即使有解，f(u,v,l,r)=0 仍然有很大概率成立（或者说很容易构造这样的例子）。为了解决这个问题，我们将原来的 n 种权值映射到新的 n 种权值，使得“f(u,v,l,r)=0 等价于无解”有足够大的概率成立。

具体来说，设 X 是一组大小为 n 的值域为 [0,2^{64}) 的随机变量，将权值 i 映射为权值 X_i 即可使得：对于单次查询，上述式子成立的概率 p \ge 1-2^{-64}；对于 q 次查询，上述式子均成立的概率为：

\begin{aligned} Pr\big[\bigwedge_{i=1}^{q}A_i\big]&=1-Pr\big[\bigvee_{i=1}^{q}\overline{A}_i\big]\\ &\ge 1-\sum_{i=1}^{q}Pr[\overline{A}_i]\\ &=1-\sum_{i=1}^{q}(1-Pr[A_i])\\ &\ge 1-\sum_{i=1}^{q}(1-(1-2^{-64}))\\ &=1-2^{-64}q \end{aligned}

当 q \le 2^{20} 时，该概率不小于 1-2^{-64}q \ge 1-2^{-44}，近似于 1。

我们知道，原问题相当于求区间 [l,r] 中的某个 c 使得 f(u,v,c,c) \neq 0，那么如何维护 f 值呢？

先来一个常用套路，一条路径拆成四条节点到根的链：

f(u,v,l,r)=f(1,u,l,r) \oplus f(1,v,l,r) \oplus f(1,lca(u,v),l,r) \oplus f(1,father(lca(u,v)),l,r)

因此只需维护 f(1,x,l,r)，使用可持久化线段树，时间复杂度为 O(n\log{n}+q\log{n})。（根据“f(u,v,l,r)=0 等价于无解”这一性质，我们可以在线段树上二分求解，具体实现见代码）

PS：由于 f(1,lca(u,v),l,r) \oplus f(1,father(lca(u,v)),l,r)=f(lca(u,v),lca(u,v),l,r)，你也可以每个点额外再开一颗线段树，用于直接查询后两项。

代码

需要注意的是，查询时一旦找到答案，就不再继续求解，否则时间复杂度会变成 O(n\log{n}+q\log^2{n})。

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int max_n=3e5+5;
int End[max_n<<1],Last[max_n],Next[max_n<<1],e;
inline void add_edge(int x,int y)
{
    End[++e]=y;
    Next[e]=Last[x];
    Last[x]=e;
    End[++e]=x;
    Next[e]=Last[y];
    Last[y]=e;
}
int dep[max_n],fath[max_n],sz[max_n],son[max_n];
void dfs1(int x,int fa)
{
    dep[x]=dep[fa]+1;
    fath[x]=fa;
    sz[x]=1;
    son[x]=-1;
    int max_sz=0;
    for(int i=Last[x];i;i=Next[i])
    {
        int y=End[i];
        if(y!=fa)
        {
            dfs1(y,x);
            sz[x]+=sz[y];
            if(sz[y]>max_sz)
            {
                max_sz=sz[y];
                son[x]=y;
            }
        }
    }
}
int _top[max_n];
void dfs2(int x,int top_now)
{
    _top[x]=top_now;
    if(son[x]!=-1)
        dfs2(son[x],top_now);
    for(int i=Last[x];i;i=Next[i])
    {
        int y=End[i];
        if(y!=fath[x]&&y!=son[x])
            dfs2(y,y);
    }
}
inline int get_LCA(int x,int y)
{
    while(_top[x]!=_top[y])
    {
        if(dep[_top[x]]<dep[_top[y]])
            swap(x,y);
        x=fath[_top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int a[max_n];
unsigned long long X[max_n];
namespace SegmentTree
{
    const int max_sz=20*3e5+5;
    unsigned long long val[max_sz];
    int ls[max_sz],rs[max_sz],cnt_node;
    void modify(int old,int &p,int l,int r,int k,unsigned long long v)
    {
        p=++cnt_node;
        val[p]=val[old]^v,ls[p]=ls[old],rs[p]=rs[old];
        if(l<r)
        {
            int mid=(l+r)>>1;
            if(k<=mid)
                modify(ls[old],ls[p],l,mid,k,v);
            else
                modify(rs[old],rs[p],mid+1,r,k,v);
        }
    }
    int res;
    void query(int p1,int p2,int p3,int p4,int l,int r)
    {
        if(l==r)
        { 
            res=l;
            return;
        }
        int mid=(l+r)>>1;
        if(val[ls[p1]]^val[ls[p2]]^val[ls[p3]]^val[ls[p4]])
            query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid);
        else
            query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r);
    }
    void query(int p1,int p2,int p3,int p4,int l,int r,int a,int b)
    {
        if(a<=l&&r<=b)
        {
            if(val[p1]^val[p2]^val[p3]^val[p4])
                query(p1,p2,p3,p4,l,r);
            return;
        }
        int mid=(l+r)>>1;
        if(a<=mid)
            query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,a,b);
        if(b>mid&&res==-1)
            query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,a,b);
    }
}
int root[max_n];
void dfs(int x,int fa)
{
    SegmentTree::modify(root[fa],root[x],1,n,a[x],X[a[x]]);
    for(int i=Last[x];i;i=Next[i])
    {
        int y=End[i];
        if(y!=fa)
            dfs(y,x);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
        scanf("%d",a+i);
    for(int i=1;i<=n-1;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
    }
    dfs1(1,0);
    dfs2(1,1);
    srand(time(NULL));
    for(int i=1;i<=n;++i)
        X[i]=1ull*rand()<<60|1ull*rand()<<45|1ull*rand()<<30|1ull*rand()<<15|1ull*rand();
    dfs(1,0);
    while(q--)
    {
        int u,v,l,r;
        scanf("%d%d%d%d",&u,&v,&l,&r);
        int p=get_LCA(u,v);
        SegmentTree::res=-1;
        SegmentTree::query(root[u],root[v],root[p],root[fath[p]],1,n,l,r);
        printf("%d\n",SegmentTree::res);
    }
    return 0;
}

有关 X 的随机生成

上述代码中使用的方法是，将 5 个 rand() 函数通过移位进行叠加，即：

srand(time(NULL));
for(int i=1;i<=n;++i)
    X[i]=1ull*rand()<<60|1ull*rand()<<45|1ull*rand()<<30|1ull*rand()<<15|1ull*rand();

（在 Windows 下，rand() 的取值范围为 [0,2^{15})）

你也可以使用比较高级的随机数：

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
for(int i=1;i<=n;++i)
    X[i]=rd();

事实上，本人一开始使用的是下面这种方法，会被 test 7 的第 164990 个询问卡掉，答案不为 -1，但代码输出 -1。

srand(time(NULL));
for(int i=1;i<=n;++i)
    for(int j=0;j<64;++j)
        X[i]=X[i]<<1|(rand()&1);

（即从高到低每一个二进制位均为 rand()&1，我试过其它种子，都会被同样卡掉）

个人理解是因为 rand() 的均匀随机性不高，容易出现循环——这只是感性理解，如果你能给出更严谨的解答或构造这样的 Hack 数据，请务必私信告知我，我会将其添加至该篇文章，供大家学习。