题解：CF421D Bug in Code

· · 题解

笑点解析：一开始读错题了，没读出一个人最多有 1 的贡献，导致我感觉这个题是橙题。

考虑维护每个数的出现次数 a_i，以及每个数出现时另一个数构成的可重集。那么枚举其中一个数，每次遍历这个集合中所有数，令其出现次数减去 1（因为它已经贡献过一次了不可能再贡献一次）。之后出现次数大于等于 P-a_i 的数个数就是答案。

上面那个东西容易用 BIT 维护，做完了。复杂度 O(n\log n)。

注意不计顺序，也就是前面扫过的数不要计算贡献。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned
#define inf (int)(1e18)
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf (int)(1e9)
#define infl (int)(1e18)
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
const int N=1e6+10,mod=998244353;
int a[N];
vector<int>vec[N];
int n,x;
struct bit
{
    int c[N];
    void add(int x,int v){x++;for(;x<=n+1;x+=lowbit(x)) c[x]+=v;}
    int sum(int x){x++;int s=0;for(;x;x-=lowbit(x)) s+=c[x];return s;}
}bit;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u]++,a[v]++;
        vec[u].pb(v),vec[v].pb(u);
    }
    for(int i=1;i<=n;i++) bit.add(a[i],1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(auto v:vec[i])
        {
            if(v<i) continue;
            bit.add(a[v],-1);
            a[v]--;
            bit.add(a[v],1);
        }
        bit.add(a[i],-1);
        if(x-a[i]-1<0) ans+=bit.sum(n);
        else ans+=bit.sum(n)-bit.sum(x-a[i]-1);
        for(auto v:vec[i])
        {
            if(v<i) continue;
            bit.add(a[v],-1);
            a[v]++;
            bit.add(a[v],1);
        }
    }
    cout<<ans;
    return 0;
}

:::