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;
}