CF421D Bug in Code 题解

题意：

最近，在 “低聚果糖” 代码公司发现了一个严重的 bug！”低聚果糖” 公司的负责人 cxy 想找到罪魁祸首并惩罚他。为了这个，她组合了一场会议，主题是：谁写出了 bug？会议上一共有 $n$ 个程序员，其中每个人都说：“我知道，一定是 $x$ 或 $y$ 之一！”

cxy 决定选择两名嫌疑人并请到他的办公室。自然地，她需要考虑这 $n$ 个人的观点。她想要选择这样两个人 $u, v$，满足 $n$ 个人的至少 $p$ 个人同意。一个人同意指的是，他认为 (是嫌犯) 的两个人中，至少有一个是 $u$ 或 $v$。cxy 想知道，一共有多少种方案选择两名嫌疑人？

输入格式：

第一行包含两个非负整数 $n, p~(3 \leq n \leq 3 \times 10^5, 0 \leq p \leq n)$ ，表示 “低聚果糖” 公司中程序员的数量和需要同意的人的最小数目。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i~(1 \leq x_i, y_i \leq n)$，保证 $x_i, y_i, i$ 互不相同，表示第 $i$ 个程序员认为的嫌犯编号。

输出格式：

输出一行一个整数，表示选择两名嫌疑人的总方案数。注意，选择的两个人是无序的，即 $(1, 2)$ 和 $(2, 1)$ 被看作是同一种方案。

如果某个人认为 $(x,y)$ 为嫌犯，则连一条 $(x,y)$ 的无向边。

则题目转化为找到有多少对 $(u,v)$ 满足 $d(u) + d(v) \ge p$ ，其中 $d(u)$ 表示 $u$ 的度数。

具体地，移项得 $d(u) \ge p-d(v)$ 。

我们可以把结点按 $d$ 排序，然后二分算出每个 $u$ 能够产生贡献的 $v$ 的个数。

但是事实上，这么算会多算答案，因为 $(u,v)$ 间的重边只能算一次，而重边会导致 $d(u),d(v)$ 变化。

我们假设 $(u,v)$ 间有 $k$ 条重边，则多计算的点对 $(u,v)$ 满足

$d(u) + d(v)-k < p \le d(u) + d(v) \tag{1}$

考虑怎么找到这样的点对。直接 $O(n^2)$ 枚举肯定是不行滴。

注意到这个边数仅为 $O(n)$ ，因此实际上被算重的点对是很少的，即 $O(n)$ 的。

考虑把所有边去重以后，在计算二分计算答案后，枚举与 $u$ 相邻的所有点，并去掉所有满足 $(1)$ 式的 $v$ 的贡献。

这样的复杂度仍是 $O(n \log n)$ 的，因为只有 $n$ 条边，每个结点至多被访问 $2$ 次。

然后就是一些细节问题了

比如 $(u,u)$ 是不合法的，要特判掉，还有最后答案要的是无序点对数，所以答案要除以 $2$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5+15))
#define M ((int)(6e5+15))

int n,p,pos,ans,o[N],in[N],head[N];
struct Edge{int u,v,w=1,next;} e[M];
bool operator<(Edge a,Edge b)
{ return a.u == b.u ? a.v < b.v : a.u < b.u; }
bool operator==(Edge a,Edge b)
{ return a.u == b.u && a.v == b.v; }
int cmp(int a,int b) { return in[a] > in[b]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> p;
    for(int i=1,u,v; i<=n; i++)
    {
        cin >> u >> v;
        e[i * 2 - 1] = {u,v};
        e[i * 2] = {v,u};
        ++in[u]; ++in[v]; o[i]=i;
    }
    sort(o+1, o+1+n, cmp);
    sort(e+1, e+2*n+1);
    for(int i=1; i<=2*n; i++)
        e[i] == e[i-1] ? (void)++e[pos].w : (void)(e[++pos]=e[i]);
    for(int i=1; i<=pos; i++) e[i].next=head[e[i].u], head[e[i].u]=i;
    for(int u=1; u<=n; u++)
    {
        in[0] = p-in[u];
        int r = upper_bound(o+1, o+1+n, 0, cmp) - o - 1;
        r -= (in[u]*2 >= p);
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            r -= (in[u] + in[v] >= p && in[u] + in[v] - e[i].w < p);
        }
        ans += r;
    }
    cout << (ans/2) << '\n';
    return 0;
}