コーダーストライク 2014

codeforces.com/contest/421/problem/D

質問:
n 個の数値ペア (a, b) が与えられた場合、数値ペア (x, y) がいくつあるかを求めます (1 3?≤?n?≤?3・105

分析:
2 つの数値 x と y が選択されたと仮定すると、このペアの値は cnt[x] + cnt[y] - cnt[(x, y)] となるはずです。思考の方向:
1. (x, y) を考えます: この複雑さは n*n であり、それを減らす方法がないため、解決できません
2. x だけを考えてください: さて、明らかなアイデアは次のとおりです。 cnt[ x] + cnt[y] >= ゴール数を満たすすべての項目を見つけるには、cnt[(x, y)] が減算されるため、答えにはいくつかの間違った項目が含まれます。しかし、(x, y) の対数は有限であるため、すべての (x, y) を列挙して、それが答えに含まれ、正当であるかどうかを確認できます

const int MAXN = 310000;struct Node{    int n, num;    int operator< (const Node& a) const    {        return num < a.num;    }} ipt[MAXN];int cnt[MAXN];int cmp(Node& a, int b){    return a.num < b;}int main(){//    freopen("in.txt", "r", stdin);    int n, k, a, b;    while (~RII(n, k))    {        CLR(cnt, 0);        map<pair<int, int>, int> mp;        FE(i, 1, n) ipt[i].n = i;        FE(i, 1, n) ipt[i].num = 0;        REP(i, n)        {            RI(a); ipt[a].num++; cnt[a]++;            RI(b); ipt[b].num++; cnt[b]++;            if (a > b) swap(a, b);            mp[MP(a, b)]++;        }        sort(ipt + 1, ipt + n + 1);        LL ans = 0;        FE(i, 1, n)        {            int ind = lower_bound(ipt + i + 1, ipt + n + 1, k - ipt[i].num, cmp) - ipt;            ans += n - ind + 1;        }        FC(it, mp)        {            a = (it->first).first; b = (it->first).second;            if (cnt[a] + cnt[b] >= k && cnt[a] + cnt[b] - it->second < k)                ans--;        }        cout << ans << endl;    }    return 0;}