Coder-Strike 2014

codeforces.com/contest/421/problem/D

Question:
Given n number pairs (a, b), now find How many number pairs (x, y) (1 3?≤?n?≤?3·105

Analysis:
Suppose two numbers x and y are selected, then the value of this pair should be cnt[x] cnt[y] - cnt[(x, y)]. Direction of thinking:
1. Consider (x, y): This complexity is n*n, and there is no way to reduce it, so it is unsolvable
2. Consider an x ​​alone: ​​Now an obvious idea is to find it by bisection All the numbers that satisfy cnt[x] cnt[y] >= goal, but since cnt[(x, y)] is subtracted, the answer will include some incorrect ones. But the logarithm of (x, y) is finite, so we can enumerate all (x, y) to see if it counts in the answer and is legal

const int MAXN = 310000;struct Node{    int n, num;    int operator, 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  <br> <br> <p></p>