题解 P8250 交友问题

· · 题解

题目传送门

前置知识：

根号分治。

简要题意：

分析：

记点 u 的度数为 deg_u。

记询问 u,v 的答案为 g_{u,v}，则 g_{u,v} 即为 deg_u 减去 u 与 v 的公共相邻点个数，若 u 与 v 相邻，再减去 1。考虑如何求 deg_u-g_{u,v}，即 u 与 v 的公共相邻点个数，若 u 与 v 相邻，再加上 1。

考虑暴力。对于单次询问，找出所有与 u 相邻的节点并将其打上标记；再找出所有与 v 相邻的点，统计其中有标记的点的数量，即 u 与 v 公共相邻点的数量；若 v 有标记，再加上 1。放一个代码片段方便理解。

memset(vis, 0, sizeof vis);
for(int z: ver[u]) {
    vis[z]=1;
}
int ans=vis[v];
for(int z: ver[v]) {
    ans+=vis[z];
}
printf("%d\n", deg[u]-ans);

单次询问更优的实现（对标记“懒”清空）可以做到 \mathcal O(deg_u+deg_v)=\mathcal O(m)，总复杂度 \mathcal O(mq)，期望 20pts。实测 88pts。

考虑优化。如果有两个询问完全相同，则不重复计算；即对询问去重。同时，对于同一个 x，我们统一处理所有 u=x 的询问。这些询问只需打一次标记，复杂度 \mathcal O(deg_x)；遍历所有 v 及其相邻边复杂度 \mathcal O(m)。对于所有的 x，总复杂度 \mathcal O(\sum_x(deg_x+m)+q)=\mathcal O(nm+q)，期望还是 20pts。实测 100pts。

上述过程中我们可以处理 \mathcal O(n^2) 个询问，而总共只需要处理 q 个询问。继续考虑优化。注意到 deg_u-g_{u,v} 中，u 和 v 的地位是相等的，不妨让 u 成为其中 deg 较大者。于是，当 deg_u<B 时，一次询问的复杂度为 \mathcal O(deg_u+deg_v)=\mathcal O(B)；当 deg_u\ge B 时，因为 \sum deg=2m，所以最多存在 \lfloor\frac {2m}B\rfloor 个不同的 u，按照上述优化遍历所有不同的 u 对应的 v 及其相邻边的复杂度为 \mathcal O(\frac mB\times m)。总复杂度 \mathcal O(qB+\frac{m^2}B)。

这个上界对所有的正实数 B 都成立。可以取 B=\frac m{\sqrt q}，此时的上界是 \mathcal O(m\sqrt q)。在非特殊构造的数据下很难达到这个上界，期望 100pts。实测 100pts。

需要注意的是，这一步的优化保证了 deg_u\ge deg_v，而优化 1 没有，所以不能直接对优化 1 套用这里的复杂度分析。

由于对两种点的做法是一样的，所以代码比较简单。因为用了快排去重，所以代码的复杂度是 \mathcal O(n+m\sqrt q+q\log q)。空间复杂度 \mathcal O(n+m+q)。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;
const int mN=2e5+9, mM=7e5+9;
int n, m, q, deg[mN];

vector<int> ver[mN];

int ans[mN];
vector<pair<int, int> > qn[mN];

int vis[mN];

int main() {

    scanf("%d%d%d", &n, &m, &q);
    rep(i, 1, m) {
        int x, y;
        scanf("%d%d", &x, &y);
        ++deg[x], ++deg[y];
        ver[x].push_back(y), ver[y].push_back(x);
    }
    rep(i, 1, q) {
        int x, y;
        scanf("%d%d", &x, &y);
        ans[i]=deg[x];  //ans 的剩余部分（deg[x]-g(x, y)）中，x y 地位相等 
        if(deg[x]<deg[y]) swap(x, y);   //保证 x 的 deg 更大 
        qn[x].push_back({y, i});
    }

    rep(x, 1, n) {
        sort(qn[x].begin(), qn[x].end());   //为了去重

        for(int y: ver[x]) {
            vis[y]=x;
        }
        int lst=0, lstans=0;
        //lst 记录上一个询问的 y, lstans 记录上一个询问的 deg[x]-g(x, y)
        for(auto ask: qn[x]) {
            const int y=ask.first, id=ask.second;
            if(y==lst) {
                ans[id]-=lstans;
                continue;
            }
            lstans=vis[y]==x;
            for(int z: ver[y]) {
                lstans+=vis[z]==x;
            }
            ans[id]-=lstans;
            lst=y;
        }
    }
    rep(i, 1, q) printf("%d\n", ans[i]);
    return 0;
}