题解：CF421D Bug in Code

· · 题解

哇去怎么做了一晚上虽然是一边看可塑一边做的（）

duel 随到的，结果嫌麻烦毙掉了正解，写出来的双指针 TLE 了 /ng

还好我和 KDL 都读错题了，最后平掉。

简要题意：

给你 n 个无序二元组和一个参数 P，定义一个无序二元组 (x,y) 合法当且仅当包含 x 的二元组集与包含 y 的二元组集的并集大小不小于 P。

WA on #5 警示：支持数看的是鸭鸭数量而不是投票数量，一对放逐鸭同时受到一只鸭的投票，这只鸭的贡献只是 1 哦。

首先我们考虑开桶存每只鸭的吃票数量。

接着对于每个票型的情况开桶做后缀和。

这样我们确认其中一个数字时，合法二元组的数量就可以 O(1) 计算了。

具体的，我们将当前票数距离胜诉的数量放到后缀和中查找，所有不小于距离胜诉票数的票型就都可以是合法解。

小心不要越界，同时特判不能一只鸭放逐两次。

如果一只鸭就能胜诉，那么剩下 n-1 只鸭都可选。

但这样会算重，刚好把每一个 (x,y) 对应的 (y,x) 也都算进去了。我们要的是无序对，于是将答案折半即可。

诶诶好像忘了些什么，不是取并集吗，你这样不是直接将票数简单相加了？

于是对于每一个可能会因为取并集而减少票数的二元组，我们要拎出来再判断一次修改答案。

注意到只有存在一只鸭鸭把当前二元组中的两位全部举报时，才有可能因取并集而少票。

于是根据每一个鸭鸭的举报信息反过来进行判断，我们就可以做到 O(n)。

我偷懒上了个 map，所以是 O(n\log n) 的，也能过就是了。

做完了。

#include<bits/stdc++.h>
#define int long long
#define mk make_pair
using namespace std;
int read(){
    int sum=0,fish=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')fish=-1,c=getchar();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=getchar();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
int a[300005],ans1,ans2;
int b[300005];
map<pair<int,int>,int>mp;
signed main(){
    int n=read(),p=read();
    for(int i=1;i<=n;i++){
        int u=read(),v=read();
        a[u]++,a[v]++;
        int U=max(u,v);
        int V=min(u,v);
        mp[mk(U,V)]++;
    }
    for(int i=1;i<=n;i++)b[a[i]]++;
    for(int i=n;i;i--)b[i]+=b[i+1];
    for(int i=1;i<=n;i++)
    if(a[i]<p)ans1+=b[p-a[i]]-(a[i]*2>=p);
    else ans1+=n-1;
    ans1>>=1;
    for(auto i:mp){
        int qwq=a[i.first.first]+a[i.first.second];
        ans2-=(qwq-i.second<p&&qwq>=p);
    }
    print(ans1+ans2);
    return 0;
}
/*
时光流转
愿你与珍爱之人
能够再次重逢
*/