Luobuyu's Blog

0%

1782. 统计点对的数目

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 7.3k 阅读时长 ≈ 7 分钟
使用乘法原理技巧，类似离线做法了。

1782.统计点对的数目

题目描述：

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：

  • a < b
  • cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。

请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。

请注意，图中可能会有 多重边 。

数据范围：

$2\le n \le 2\times10^4;1\le m \le 10^5;1\le q\le 20$

题解：

可以发现是 $deg[a] + deg[b] - cnt[edges[a,b]]$ ，其中去除边可以后续处理。可以先求出来 $deg[a] + deg[b] > q$ 的部分。对 $deg$ 排序，然后使用双指针 $l=0, r = n - 1$ 。

  • 当 $deg[l] + deg[r] \le q$ 时， $l = l + 1$ ；一直移动 $l$ 直到 $deg[l] + deg[r] \gt q$
  • 当 $deg[l] + deg[r] \gt q$ 时， $[l, r)$ 之间的与 $r$ 相加都满足。因此答案加上 $r-l$ 。同时将 $r$ 向前移动一次， $r = r - 1$ 。

求出 $q$ 的答案之后，需要减去边的数量。可以遍历 $cnts[edges]$ 哈希表。找到满足 $deg[u] + deg[v] \gt q $ 并且 $deg[u] + deg[v] - cnts[u\rightarrow v] \le q$ 的，减去这一对对答案的贡献， $ans = ans - 1$ 。

也可以考虑类似离线的做法。如果能够处理出来后缀和，那么就直接输出就行。首先先计算出 $freq\_deg$ ，也就是 $deg$ 的频率，就是每个数字出现的次数，那么这样就可以快速的求出 $cnts[deg[u] + deg[v]]$ 了。对于所有的桶 $freq\_deg_i$ ，首先自己桶内的元素可以相加得到 $cnts[2 \times freq\_deg_i]$ ，并且次数等于 $\frac{size_i(size_i - 1)}{2}$ ，对于任意的不相同的两个桶，可以得到 $cnts[freq\_deg_i + freq\_deg_j] = size_i\times size_j$ 。

假设每一个 $deg_i$ 都不一样，那么 $1 + 2 + 3 +\cdots + x = \frac{x (x + 1)}{2}\le 2\times m$ 。可以求出来 $x$ 的上界约为 $\sqrt{4m}$ 。那么意味着 $deg$ 中最多有 $O(\sqrt m)$ 个不同的数字，这样的话使用二重循环遍历求出 $cnts$ ，而且只有 $O(m)$ 的复杂度。与之前的排序相比快了许多。

求出 $cnts$ 数组之后，对于存在边 $[u\rightarrow v]$ 的，假设边数为 $s$ ，那么 $cnts[deg[u] + deg[v]]$ 这个桶需要减去 $[u,v]$ 这一对的贡献，其实就是减 $1$ ， $cnts[deg[u] + deg[v] - s]$ 需要加上 $[u,v]$ 这一对的贡献，其实就是加 $1$ 。

最后求一个 $cnts$ 的后缀和，就可以得到 $cnts_i = q$ 表示大于等于 $q$ 的对数。由于答案要求严格大于，因此需要 $cnts[q + 1]$ 。并且需要判断一下 $q + 1$ 是不是太大了，超过了 $cnts$ 的大小。其中 $cnts$ 的大小与 $max\_deg \times 2$ 有关，因为是 $deg$ 加出来的，而且要包含 $max\_deg \times 2$ ，因此大小为 $max\_deg * 2 + 1$ 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 2e4 + 1;
    int deg[maxn] = {};
    int id[maxn];

    unordered_map<int, int> mp;
    vector<int> countPairs(int n, vector<vector<int>> &edges, vector<int> &queries)
    {
        int m = edges.size();
        for (int i = 0, u, v; i < m; ++i)
        {
            u = edges[i][0] - 1;
            v = edges[i][1] - 1;
            deg[u]++;
            deg[v]++;
            if (u > v)
                swap(u, v);
            mp[u * n + v]++;
        }
        for(int i = 0; i < n; ++i) id[i] = i;
        sort(id, id + n, [&](const int &x, const int &y)
             { return deg[x] < deg[y]; });

        for (auto &q : queries)
        {
            int ans = 0;
            int l = 0, r = n - 1, u, v;
            while (l < r)
            {
                u = id[l], v = id[r];
                if (deg[u] + deg[v] <= q)
                    ++l;
                else
                {
                    ans += r - l;
                    r--;
                }
            }
            for (auto &kv : mp)
            {
                int u = kv.first / n;
                int v = kv.first % n;
                // u = id[u], v = id[v];
                int tot = deg[u] + deg[v];
                if (tot > q && tot - kv.second <= q)
                {
                    ans--;
                }
            }
            q = ans;
        }
        return queries;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 2e4 + 1;
    const static int maxm = 1e5 + 1;
    int deg[maxn] = {};
    int id[maxn];
    int cnts[maxm * 2] = {};
    unordered_map<int, int> mp;
    vector<int> countPairs(int n, vector<vector<int>> &edges, vector<int> &queries)
    {
        int m = edges.size();
        int max_deg = 0;
        for (int i = 0, u, v; i < m; ++i)
        {
            u = edges[i][0] - 1;
            v = edges[i][1] - 1;
            deg[u]++;
            deg[v]++;
            if (u > v)
                swap(u, v);
            mp[u * n + v]++;
        }
        unordered_map<int, int> freq_deg;
        for (int i = 0; i < n; ++i)
        {
            freq_deg[deg[i]]++;
            max_deg = max(max_deg, deg[i]);
        }
        // 计算cnts[deg[u] + deg[v]]次数
        int cnts_size = max_deg * 2 + 1;
        for (auto &kv1 : freq_deg)
        {
            for (auto &kv2 : freq_deg)
            {
                if (kv1.first > kv2.first)
                    continue;
                if (kv1.first == kv2.first)
                {
                    cnts[kv1.first * 2] += kv1.second * (kv1.second - 1) / 2;
                }
                else
                {
                    cnts[kv1.first + kv2.first] += kv1.second * kv2.second;
                }
            }
        }
        // 去掉重边
        for (auto &kv : mp)
        {
            int u = kv.first / n;
            int v = kv.first % n;
            int tot = deg[u] + deg[v];
            cnts[tot]--;
            cnts[tot - kv.second]++;
        }
        // cnts 后缀和
        for (int i = cnts_size - 1; i >= 0; --i)
        {
            cnts[i] += cnts[i + 1];
        }
        for (auto &q : queries)
        {
            if (q + 1 < cnts_size)
            {
                q = cnts[q + 1];
            }
            else
                q = 0;
        }

        return queries;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
namespace FAST_IO
{
    static string buf_line;
    static int _i;
    static int _n;
    static char _ch;
    template <class T>
    inline bool read(T &x)
    {
        T flag = 1;
        x = 0;
        if (_i >= _n)
            return false;
        _ch = buf_line[_i++];
        while (_ch < '0' || _ch > '9')
        {
            if (_ch == '-')
                flag = -1;
            _ch = buf_line[_i++];
        }
        while (_ch >= '0' && _ch <= '9')
        {
            x = (x << 3) + (x << 1) + (_ch ^ 48), _ch = buf_line[_i++];
        }
        x *= flag;
        return true;
    }

    template <class T, class... _T>
    inline bool read(T &x, _T &...y)
    {
        return read(x), read(y...);
    }

    inline bool getline()
    {
        if (!getline(cin, buf_line))
            return false;
        _i = 0, _n = buf_line.length();
        return true;
    }
    template <class T>
    inline void show(T *a, int n)
    {
        cout << "[";
        for (int i = 0; i < n; ++i)
        {
            if (i != 0)
                cout << ",";
            cout << a[i];
        }
        cout << "]";
    }

    bool endofl()
    {
        if (_i >= _n)
            return true;
        if (_i == 0)
            return false;
        if (buf_line[_i - 1] == ']')
        {
            _i++;
            return true;
        }
        return false;
    }

    template <class T, std::size_t Num>
    inline void show(T a[][Num], int n, int m)
    {
        cout << "[";
        for (int i = 0; i < n; ++i)
        {
            if (i != 0)
                cout << ",";
            show(a[i], m);
        }
        cout << "]";
    }

} // namespace FAST_IO
using namespace FAST_IO;

int init = []
{
    /*********** fast_read ***************/
    freopen("user.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    /*************************************/
    const static int maxn = 2e4 + 1;
    const static int maxm = 1e5 + 1;
    static int deg[maxn] = {};
    static int cnts[maxm * 2] = {};
    unordered_map<int, int> mp;
    int n = 0, m, k, u, v, max_deg, cnts_size = 0;
    int queries[21];
    while (true)
    {
        if (!getline())
            break;
        mp.clear();
        for(int i = 0; i < n; ++i) deg[i] = 0;
        for(int i = 0; i < cnts_size; ++i) cnts[i] = 0;
        read(n);
        getline();
        for (m = 0; !endofl(); ++m)
        {
            read(u, v);
            u--;
            v--;
            deg[u]++;
            deg[v]++;
            if (u > v)
                swap(u, v);
            mp[u * n + v]++;
            endofl();
        }
        getline();
        for (k = 0; !endofl(); ++k)
        {
            read(queries[k]);
        }
        max_deg = 0;
        unordered_map<int, int> freq_deg;
        for (int i = 0; i < n; ++i)
        {
            freq_deg[deg[i]]++;
            max_deg = max(max_deg, deg[i]);
        }
        // 计算cnts[deg[u] + deg[v]]次数
        cnts_size = max_deg * 2 + 1;
        for (auto &kv1 : freq_deg)
        {
            for (auto &kv2 : freq_deg)
            {
                if (kv1.first > kv2.first)
                    continue;
                if (kv1.first == kv2.first)
                {
                    cnts[kv1.first * 2] += kv1.second * (kv1.second - 1) / 2;
                }
                else
                {
                    cnts[kv1.first + kv2.first] += kv1.second * kv2.second;
                }
            }
        }
        // 去掉重边
        for (auto &kv : mp)
        {
            int u = kv.first / n;
            int v = kv.first % n;
            int tot = deg[u] + deg[v];
            cnts[tot]--;
            cnts[tot - kv.second]++;
        }
        // cnts 后缀和
        for (int i = cnts_size - 1; i >= 0; --i)
        {
            cnts[i] += cnts[i + 1];
        }
        cout << "[";
        for (int i = 0; i < k; ++i)
        {
            int &q = queries[i];
            if (q + 1 < cnts_size)
            {
                q = cnts[q + 1];
            }
            else
                q = 0;
            if (i == 0)
                cout << q;
            else
                cout << "," << q;
        }
        cout << "]\n";
    }
    exit(0);
    return 0;
}();

class Solution
{
public:
    vector<int> countPairs(int n, vector<vector<int>> &edges, vector<int> &queries)
    {
        return queries;
    }
};