codeforces.com/contest/421/problem/D
Question:
Given n number pairs (a, b), now find How many number pairs (x, y) (1 <= x, y <= n) satisfy at least k number pairs. x, y satisfies a number pair (a, b) if and only if x, y appears in the number pair (a, b) at least once
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< (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;}
Statement:The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn