TIOJ-1726

2qbingxuan

2019-12-23

TIOJ , sqrt-decomposition

Dice Wars

https://tioj.ck.tp.edu.tw/problems/1726

Description

Dice Wars是一款兼具謀略和運氣的遊戲。
遊戲中你扮演紫色的骰子，要攻下其他顏色的骰子的城池，進而統一全地圖。

如今你選到了一張看起來不錯的地圖: 整張地圖呈一條直線，每個位置都有一個顏色勢力佔領。
由於每次移動到相鄰異色的城池都必須經歷一場鏖戰，你想先經過程式計算後再進行遊戲。

你想要每次詢問一個顏色對$(S, T)$，問從任何一個$S$的城池到任一個$T$的城池至少要經過幾場戰鬥。
如果$S$或$T$已經滅亡(地圖中沒有任何一個該勢力)，就輸出$-1$。

Solution

題敘裡面附上的遊戲好好玩www

題目要問的其實就是$\min\limits _ {c_i=S,c_j=T}(|i-j|)$
可以想到對每種顏色開一個 vector 紀錄他們的index

一種naive$\mathcal{O}(nq)$的方法是每次詢問都直接把兩種顏色的兩個 vector merge $\mathcal{O}(n)$合併並計算答案
而另一種naive的算法則是先針對每一種顏色$\mathcal{O}(n)$預處理其對其他顏色的答案，複雜度$\mathcal{O}(n^2+q)$
前者拉低複雜度的關鍵是某種顏色出現很多次
而後者則是會因為太多種顏色而複雜度爛掉

怎麼辦呢？可以不要全部預處理，只針對出現次數超過$k$的顏色做預處理，這些顏色的種類數不會超過$\frac{n}{k}$種
故預處理需要$\mathcal{O}(\frac{n^2}{k})$
而對於詢問的兩個顏色的出現次數都沒有超過$k$的情況，可以直接用上面第一個算法處理
複雜度$\mathcal{O}(qk)$

根據算幾不等式可取$k=\frac{n}{\sqrt{q}}$有複雜度$\mathcal{O}(n\sqrt{q})$

註: 這題我寫的時候 ans 開原生陣列MLE，不知為何用vector陣列會是好的

AC code

 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
#include <bits/stdc++.h>
#ifdef local
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#else
#define debug(x) ((void)0)
#endif // local
#define pb emplace_back

using namespace std;
constexpr int N = 60025, K = 300, inf = 1e8;

vector<int> id[N],ans[K];
int big[N],totb,n,q,v[N];
void precalc(int k) {
    ans[k].resize(n+1,inf);
    //for(int i = 1; i <= n; i++) ans[k][i] = inf;
    int last;
    last = -inf;
    for(int i = 0; i < n; i++) {
        if(big[v[i]] == k)
            last = i;
        else
            ans[k][v[i]] = min(ans[k][v[i]], i - last);
    }
    last = inf;
    for(int i = n-1; i >= 0; i--) {
        if(big[v[i]] == k)
            last = i;
        else
            ans[k][v[i]] = min(ans[k][v[i]], last - i);
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    // small - small -> brute every time
    // big - other -> precalc
    cin >> n >> q;
    int S = 400;
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++) id[v[i]].pb(i);
    for(int i = 1; i <= n; i++) if(id[i].size() >= S) {
        big[i] = ++totb;
        precalc(big[i]);
    }
    while(q--) {
        int a,b;
        cin >> a >> b;
        if(id[a].empty() || id[b].empty()) cout << -1 << '\n';
        else if(a == b) cout << 0 << '\n';
        else {
            if(id[a].size() < S && id[b].size() < S) {
                vector<int> A = id[a];
                vector<int> B = id[b];
                int i = 0, j = 0, lastA = -inf, lastB = -inf, res = inf;
                while(i < A.size() || j < B.size()) {
                    if(j==B.size() || (i<A.size() && A[i]<B[j])) {
                        int t = A[i++];
                        res = min(res, t - lastB);
                        lastA = t;
                    }else {
                        int t = B[j++];
                        res = min(res, t - lastA);
                        lastB = t;
                    }
                }
                cout << res << '\n';
            }else {
                if(big[a])
                    cout << ans[big[a]][b] << '\n';
                else
                    cout << ans[big[b]][a] << '\n';
            }
        }
    }
}