Coder-Strike 2014

codeforces.com/contest/421/problem/D

题意：
给定n个数对（a， b），现在求有多少个数对（x， y）（1 3?≤?n?≤?3·105

分析：
不妨设选定两个数x、y，那么这对的值应该是cnt[x] + cnt[y] - cnt[(x, y)]。思考方向：
1.考虑（x， y）：这样的复杂度是n*n的，且没办法降低，所以不可解
2.单独考虑一个x：现在一个明显的想法是二分找到所有满足cnt[x] + cnt[y] >= goal的个数，但是由于少减去了cnt[(x, y)]，所以答案会包括一部分不正确的。但是（x， y）的对数是有限的，所以我们可以枚举所有的（x， y），看看它是否算在了答案中且是否合法

const int MAXN = 310000;struct Node{    int n, num;    int operator, int&gt; 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 &gt; 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-&gt;first).first; b = (it-&gt;first).second;            if (cnt[a] + cnt[b] &gt;= k &amp;&amp; cnt[a] + cnt[b] - it-&gt;second   <br>  <br>  <p></p>