牛客小白月赛52 E.分组求对数和(二分&容斥)

先用数组存所有数，然后再用二维vector存每个组的数。

根据容斥思想，对于每个数就先二分找到所有满足的个数然后减掉自己组里的。

自己组里的就是在对应的vector里的二分。

时间复杂度：$O(mlogm)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

int n, k;

vector<int> ve[1000009], a;
void solved() {
    
    scanf("%d%d", &n, &k);
    int m;
    for(int i = 0; i < n; i ++) {
    
        scanf("%d", &m);
        int x;
        while(m --) {
    
            scanf("%d", &x);
            ve[i].push_back(x);
            a.push_back(x);
        }
        sort(ve[i].begin(), ve[i].end());
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    for(int i = 0; i < n; i ++) {
    
        m = ve[i].size();
        for(int j = 0; j < m; j ++) {
    
            int x = ve[i][j], y = k - x;
            ans += 
            (a.end() - upper_bound(a.begin(), a.end(), y - 1)) - 
            (ve[i].end() - upper_bound(ve[i].begin(), ve[i].end(), y - 1));
        }
    }
    ans /= 2;
    cout << ans % 998244353;
}
int main() {
    
    // int ttx; cin >> ttx; while(ttx --) 
        solved();
    return 0;
}