A Peaceful Journey

fantastic inspirations

0%

基于数据矛盾性的暴力优化

发表于 更新于 分类于

一、题目引入

前情提要：今天打了ccpc的网络赛，最后大败而归。😭😭😭
让我绝望的是到最后G题一直TLE，赛后发现自己的做法缺少了一个关键的细节。于是写博客记录一下此题及其使用的思想。

题目：G 序列与整数对

题目大意：有一个长度为n的序列A，q次询问，每次询问给出两个整数<x,y>，问A中存在多少个<x,y>。
数据范围：$1 <= n,q <= 10^5， 1 <= x,y <= 10^9$。

二、解题思路

1.赛时思路

  • 初始思路（暴力）
    一开始想到的是先暴力枚举。在遍历{$a_i$}时，记录下ai出现的位置，存储在一个数组中。然后在输入x,y后，遍历x的位置数组，找在当前x位置后第一次出现的y的位置，即可算出有多少对${x,y}$。
    简单分析一下时间复杂度。频度最大的操作是每次查询中遍历x的位置数组 + 查询满足条件的y。这里查找肯定用二分，因此时间复杂度为$O(qn\log{n})$，显然会超时。

  • 暴力基础上的优化思路
    我们发现导致超时的数据有以下特征：
    {$a_i$}中的数字种类单一，每个数字出现了很多次，因此x的位置数组很大，每次查询操作中，基本上都是 $O(n\log{n})$级别的。不过好消息是有效查询减少了（定义有效查询为x和y均在数组中出现过且$x \neq y$）。

    相反，若{$a_i$}中的数字离散程度较大，每个数字出现次数少，那么每次查询中，遍历完位置数组只有常数级别复杂度。

    针对第一种情况的数据，我们做了记忆化处理。把${x, y}$对应的答案存储下来，在下次出现的时候直接输出即可。如此，可以大大降低时间复杂度，大概为$O(\frac{q}{c}n\log{n})$（这里c是个常数，在不同数据中会有变化）

2.赛后的思路优化

  • 上一步优化了时间复杂度，实际上在较坏的情况下常数c可能很小，导致优化效果并不好，举个例子：
    $n = q = 10^5$的时候，我给5e4个1，剩下5e4个数都不一样
    若接下来的5e4次查询中，x都是1，y都不一样，那么每次查询还是要把x的位置序列都遍历一遍，即使二分查找的时间复杂度完全可以忽略不计，但总共有5e4*5e4次操作，依然超时。
    问题很明显，我们应该选择x和y中出现次数少的来遍历，防止遍历复杂度过高。

  • 分析时间复杂度
    首先列一张表，拆解时间复杂度$O(qn\log{n})$的组成部分

    组成部分 代表含义
    $q$ 有效查询次数$Q<q$
    $n$ 一次查询中遍历某个数出现位置的时间复杂度$t_1<n$
    $logn$ 二分查找另一个数位置的时间复杂度$t_2<logn≈10$

    所以在估计数量级之前的复杂度为$O(Qt_1t_2)$。事实上$Q,t1,t2$不可能同时取到最大值，三者是相互制约的。
    假设$n$个数中共有$m$个不同的数，每个数的出现次数从小到大排列为$b_1,b_2,b_3……,b_m$。易知$\sum_{i=1}^{m}b_i = n$，$Q$最大可以取到$A_{m}^{2}$，而且不会超过$q$，即$Q=min(A_{m}^{2},q)$。

    ① $m < \sqrt{q}$

    最坏情况下，我们需要把所有可能的${ b_i,b_j}$都暴力计算一遍，即$Q = A_m^2$。对于每一对${ b_i,b_j}$，我们都要遍历其中出现次数少的数的位置。由此可得总时间复杂度为$O(\sum_{i=1}^{m}b_i(m-i)log{b_j})<O(mlogb_j·\sum_{i=1}^{m}b_i)<O(n\sqrt{q}logn)$

    ② $m > \sqrt{q}$

    对于一个出现次数为$b_i$的数$x$，如果需要遍历其位置，则另一个数$y$的出现次数$b_j>b_i$。而这样的$y$不会超过$\frac{n}{b_i}$个，因此遍历$x$位置的次数不会超过$\frac{n}{b_i}$。

    最坏情况下，$Q = q$。假设出现次数$b_i > \sqrt{q}$的数有$k$个，易知$k≤\frac{n}{\sqrt{q}}$，将这些数挑出来可以组成$A_k^2 ≈ k^2$个有序对。最坏情况下这$k^2$个有序对均会被查询，出现$b_i$次的数会被查询$\frac{n}{b_i}$次，时间复杂度大约为$O(\sum{b_i\frac{n}{b_i}logb_j}) < O(nklogn)$。

    剩下的$q-k^2$次查询的时间复杂度不超过$O((q-k^2)\sqrt{q}logn)$。总时间复杂度约为$O((\sqrt{q}k^2+nk-q\sqrt{q})logn)<O((\frac{2n^2}{\sqrt{q}}-q\sqrt{q})logn)$

    注：对于$n=q=10^5$的最大数据，时间复杂度也可以化简$O(n\sqrt{q}logn)$

经过分析，两种情况均不会超时

最终版代码提交过后成功AC。AC代码如下：

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
#include<bits/stdc++.h>
using namespace std;
int n, q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test2.in", "r", stdin);
    //freopen("test2.out", "w", stdout);
    cin >> n >> q;
    vector <int> a(n);
    map <int, vector<int>> mp;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp[a[i]].push_back(i);      //记录a[i]的位置
    }
    map <pair<int, int>, long long> ans;    //记得开long long
    while(q--){
        int x, y;
        cin >> x >> y;
        pair<int, int> p = {x, y};
        if(ans.count(p)){       //记忆化
            cout << ans[p] << "\n";
            continue;
        }
        auto &mpx = mp[x];
        auto &mpy = mp[y];
        //记得开longlong，否则接下来的乘法运算中会爆int
        long long xl = mpx.size(), yl = mpy.size();   
        if(x == y){       //这里需要特判一下x = y的情况！！！
            cout << xl * (xl-1) / 2 << "\n";
            continue;
        }
        long long cnt = 0;
        if(xl < yl){        //选择出现次数少的遍历
            for(auto x : mpx){
                cnt += yl - (lower_bound(mpy.begin(), mpy.end(), x) - mpy.begin());
            }
            ans[p] = cnt;
        }else{
            for(auto y : mpy){
                cnt += lower_bound(mpx.begin(), mpx.end(), y) - mpx.begin();
                //注意：两种情况计算方法不一样
            }
            ans[p] = cnt;
        }
        ans[p] = cnt;       //记忆化
        cout << cnt << "\n";
    }
    return 0;
}

三、做题总结

本题的暴力优化关键在于寻找数据中的矛盾点——有效查询次数与位置数组大小，两者只能一大一小。而我们原本的暴力方法不怕有效查询次数多，位置数组小。因此我们只需找出一个针对有效查询次数少，但位置数组大的解决方案——记忆化。

其实这种思想很像根号分治。根号分治是一种在处理数据规模较大的问题时，利用不同算法来平衡复杂度的思想。它的核心在于将问题分为两类：对于小规模数据，采用暴力算法；而对于大规模数据，则使用更高效的算法，一般数据的临界点选择在$\sqrt{n}$左右。本题中我们全部采用暴力+记忆化的方法也能过，因此没有再具体细分数据类型。

接下来反思一下为什么在比赛中没能做出这题。其实早在A题我就犯了同样的错误：在造样例时没有考虑全所有的极端样例。因此A题多吃了两发罚时😭😭😭。A题中，我只考虑了棋盘是偏正方形的情况（比如600×600），没考虑一长条的情况（比如1×100000）。本题我在造数据的时候，只考虑了特别离散和特别密集的数据，却没有考虑到可以一半离散，一半密集。要是正式赛就要因为一个细节的疏忽而遗憾打铁了。