解題區/解題區 - 其他題目

BZOJ 2038 小 Z 的袜子

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個序列，詢問一個區間中任挑兩個數字，這兩個數字相同的機率為何，將答案化簡後輸出。

Sample Input

1
2
3
4
5
6
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output

1
2
3
4
2/5
0/1
1/1
4/15

Solution

莫隊算法命名是莫濤隊伍想出來的，不算是特別算法命名，估計是比賽中想到，目前沒看到英文命名。

莫隊算法處理離線詢問，回答所有答案複雜度為 $O(N^{1.5})$，其中 N 是區間索引值的範圍大小。概念在於分塊處理如下：

  • 對於每個詢問的左端點放置於同一塊去處理
  • 每一次處理一個塊狀的所有詢問
  • 對於同一塊，詢問的右端點嚴格遞增去處理，讓左端點不斷地移動

發現到單獨看左端點指針的移動，約為 $O(N^{1.5})$，只考慮同一塊，最多有 $N$ 的詢問，一個詢問會造成左端點移動 $O(N^{0.5})$。而單獨看又端點指針的移動，約為 $O(N^{1.5})$，由於只會有 $O(N^{0.5})$ 塊，每一塊最慘就是遞增的移動 $O(N)$。

只要轉移區間 (維護區間的答案、計數，例如從 [l, r] 變成 [l, r-1] 的答案維護，把區間左右端點變大變小 1 的轉移計算) 的速度快，則複雜度約為 $O(N^{1.5})$。有不少情況需要 $O(\log N)$ 的其他數據結構維護轉移，複雜度就會變成 $O(N^{1.5} \log N)$，必要時使用塊狀表去作為數據結構進行轉移，當詢問次數 Q 與序列長度 N 呈線性關係，塊狀表支持 $O(1)$ 修改，$O(N^{0.5})$ 統計，那複雜度又能壓回 $O(N^{1.5})$。

能使用莫隊算法的題目，其中也不少能使用持久化結構來完成，若不考慮空間使用量，持久化結構能支持離線預處理、在線詢問。

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 50005;
const int MAXV = 50005;
class Offline {
public:
    struct Event {
        static int PILE;
        int l, r, qid;
        Event(int a = 0, int b = 0, int c = 0):
            l(a), r(b), qid(c) {}
        bool operator<(const Event &x) const {
            if (l / PILE != x.l / PILE)
                return l < x.l;
            return r < x.r; 
        }
    };
    int A[MAXN], N, qsize;
    vector<Event> event;
    vector< pair<long long, long long> > ret;
    void init(int N) {
        this->N = N, qsize = 0;
        event.clear();
        memset(B, 0, sizeof(B));
        for (Event::PILE = 1; Event::PILE * Event::PILE < N; Event::PILE <<= 1);
    }
    void q_add(int l, int r) {
        event.push_back(Event(l, r, qsize));
        qsize++;
    }
    void run() {
        sort(event.begin(), event.end());
        ret.resize(event.size());
        
        int l = 1, r = 0;
        q_stat = 0;
        for (int i = 0; i < event.size(); i++) {
            while (r < event[i].r)	r++, update(A[r], 1);
            while (r > event[i].r)	update(A[r], -1), r--;
            while (l > event[i].l)	l--, update(A[l], 1);
            while (l < event[i].l)	update(A[l], -1), l++;
            long long a, b, len = event[i].r - event[i].l + 1;
            if (len > 1) {
                a = q_stat - len;
                b = len * (len - 1);
            } else {
                a = 0, b = 1;
            }
            ret[event[i].qid] = make_pair(a, b);
        }
    }
private:
    long long B[MAXV], q_stat;
    void update(int x, int val) {
        B[x] += val;
        q_stat += val * 2 * B[x] - 1;
    }
} off;
int Offline::Event::PILE = 16;
long long llgcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int N, M, l, r;
    while (scanf("%d %d", &N, &M) == 2) {
        off.init(N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &off.A[i]);
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &l, &r);
            off.q_add(l, r);
        }
        off.run();
        for (int i = 0; i < off.ret.size(); i++) {
            long long a = off.ret[i].first;
            long long b = off.ret[i].second;
            long long g = llgcd(a, b);
            a /= g, b /= g;
            printf("%lld/%lld\n", a, b);
        }
    }
    return 0;
}
/*
1 1
5
1 1
*/