解題區/解題區 - Zerojudge

b417. 區間眾數

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 莫隊算法
    2. 4.2. 分塊在線 1
    3. 4.3. 分塊在線 2

Problem

背景

大學上課是怎麼回事的呢？談論到學期成績計算，很多奇聞軼事可以說的，例如教授任選三題批改、同學任選三題作答、滿分三百、沒有考試、 … 等。筆試類型的考試只是最常見的一種，還有所謂的多才華加分，例如上台報告、舉手發問、參與展覽、參加競賽、 … 等。

不幸地，某 M 修了一堂怪課，教授每一堂課結束後總是會大聲宣揚「葛萊分多加 5 分」對於需要不斷複習演練的某 M 而言，這門課的即時評分方式讓其非常挫敗。神奇的是，有一次教授這麼問同學「給一序列，請計算眾數、平均數、中位數，答對加分。」某 M 剎那間傻住，大學的學期成績可以用這種問題獲得，當他在懷疑這個問題時，問題早已被同學回答走。

某 M 非常不甘心，計算眾數、平均數、中位數就能夠加分，要求只是 n = 10 的序列。既然加分有理，出題吧！

題目描述

平均數、中位數可以藉由區間總和、區間 K 小問題來完成，現在來解決眾數。

給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$)，對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r$，每次輸出 $[s_l, \text{... },s_r]$ 中，出現最多次的次數以及有多少種數字出現最多次。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
10 10
2 3 1 1 1 2 1 2 1 1
5 8
1 10
6 9
5 9
1 5
3 10
1 9
1 1
6 9
2 3

Sample Output

1
2
3
4
5
6
7
8
9
10
2 2
6 1
2 2
3 1
3 1
6 1
5 1
1 1
2 2
1 2

Solution

眾數區間查找 Range mode query 性質可以參考維基百科。

在這一題中，這裡提供三種解法，但我的寫法中只有莫隊算法可以通過，其餘算法受到時間跟空間上的限制，需要額外的優化，細節就不多做說明：

  • 莫隊算法
    只能離線處理，無法強制在線詢問，維護眾數最高頻率指針，來統計眾數的對應次數和等價眾數的個數，由於指針移動都是 $O(1)$，整體上時間效能為 $O(N^{1.5})$。
  • 分塊在線 1
    離線預處理 $O(N^{0.5} \times N^{0.5} \times \log{N})$
    提供在線詢問 $O(\text{ans} \times \log{N})$，由於知道每一個塊中的代表眾數都可能是答案，因此預處理每一個塊的眾數，其餘的非眾數捨棄掉，最慘情況是每個數字都出現一次，在線詢問時複雜度會掉到 $O(N \log N)$。
  • 分塊在線 2
    • 離線預處理時間 $O(N \times L^2)$，提供在線詢問 $O(N/L)$，其中 $L$ 表示有多少個分塊。
    • 預處理分塊編號 $PILE[i, j]$ 的眾數情況 (類似莫隊維護指針)，因此記憶體消耗 $O(N \times L^2)$。
    • 對於每一處詢問，會對應預處理中的區域塊的紀錄 $PILE[L, R]$，接著頭尾兩端的殘存數字再依序加入，意即 $A[a, L-1]$ 和 $A[R+1, b]$ 的數字加入的複雜度 $O(1)$，隨後再進行撤銷 $O(1)$。
    • 假設詢問次數 $Q$ 與 $N$ 呈現性關係，整體需要 $O(N \times L^2 + N^2 / L)$，則 $L = N^{1/3}$ 是最好的情況，意即每一個塊具有 $O(N^{2/3})$ 個數字，最後得到整體時間效能為 $O(N^{1.66})$。

由於這一題目標不是找到眾數為何 (這牽涉到最小字典順序)，而是找眾數的出現個數和有幾種眾數可能，莫隊算法會快於其他算法。若是要求最小眾數莫隊算法需要 $O(N^{1.5} \log{N})$，分塊在線 1 也是 $O(N^{1.5} \log{N})$。

分塊在線 2 在此題不僅僅遇到記憶體過大，只好鬆弛 $L$ 來壓低記憶體用量，但增加時間需求，時間上慢個 10 倍以上。

莫隊算法

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
const int MAXV = 100005;
const int MAXQ = 1000005;
class Offline {
public:
    struct Event {
        static int PILE, belong[MAXV];
        int l, r, qid;
        Event(int a = 0, int b = 0, int e = 0):
            l(a), r(b), qid(e) {}
        bool operator<(const Event &x) const {
            if (belong[l] != belong[x.l])
                return l < x.l;
            return r < x.r; 
        }
    } event[MAXQ];
    int A[MAXN], N, qsize;
    int ret[MAXQ][2];
    void init(int N) {
        this->N = N, qsize = 0;
        memset(val_count, 0, sizeof(val_count));
        memset(mode_freq, 0, sizeof(mode_freq));
        mode_idx = 0;
        Event::PILE = sqrt(N);
        for (int i = N; i >= 1; i--)
            Event::belong[i] = i / Event::PILE;
    }
    void q_add(int l, int r) {
        event[qsize] = Event(l, r, qsize);
        qsize++;
    }
    void run() {
        sort(event, event+qsize);
        
        int l = 1, r = 0;
        for (int i = 0; i < qsize; 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++;
            ret[event[i].qid][0] = mode_idx;
            ret[event[i].qid][1] = mode_freq[mode_idx];
        }
    }
private:
    // unrolled
    int val_count[MAXV], mode_freq[MAXN], mode_idx;
    inline void update(int x, int val) {
        if (val == 1) {
            mode_freq[val_count[x]]--;
            val_count[x]++;
            mode_freq[val_count[x]]++;
            if (mode_freq[mode_idx+1] != 0)
                mode_idx++;
        } else if (val == -1) {
            mode_freq[val_count[x]]--;
            val_count[x]--;
            mode_freq[val_count[x]]++;
            if (mode_freq[mode_idx] == 0)
                mode_idx--;
        }
    }
} off;
int Offline::Event::PILE = 16, Offline::Event::belong[MAXV];
namespace mLocalStream {
    class M {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        M() {
            p = buf, end = buf + N - 1;
        }
        void printInt(int x) {
            static char stk[16];
            int idx = 0;
            stk[idx++] = '\n';
            if (!x)	
                stk[idx++] = '0';
            while (x)
                stk[idx++] = x%10 + '0', x /= 10;
            while (idx) {
                if (p == end) {
                    *p = '\0';
                    printf("%s", buf), p = buf;
                }
                *p = stk[--idx], p++;
            }
        }	
        static inline int readchar() {
            static char buf[N];
            static char *p = buf, *end = buf;
            if(p == end) {
                if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
                p = buf;
            }
            return *p++;
        }
        static inline int ReadInt(int *x) {
            static char c, neg;
            while((c = readchar()) < '-')    {if(c == EOF) return 0;}
            neg = (c == '-') ? -1 : 1;
            *x = (neg == 1) ? c-'0' : 0;
            while((c = readchar()) >= '0')
                *x = (*x << 3) + (*x << 1) + c-'0';
            *x *= neg;
            return 1;
        }
        ~M() {
            *p = '\0';
            printf("%s", buf);
        }		
    } bprint;
}
int main() {
    int n, m, l, r, a, b;
    while (mLocalStream::M::ReadInt(&n)) {
        mLocalStream::M::ReadInt(&m);
        off.init(n);
        for (int i = 1; i <= n; i++)
            mLocalStream::M::ReadInt(&off.A[i]);
        for (int i = 0; i < m; i++) {
            mLocalStream::M::ReadInt(&l);
            mLocalStream::M::ReadInt(&r);
            off.q_add(l, r);
        }
        
        off.run();
        for (int i = 0; i < m; i++)
            printf("%d %d\n", off.ret[i][0], off.ret[i][1]);
    }
    return 0;
}

分塊在線 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
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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
class ModeQuery {
public:
    int A[MAXN], N, PILE, belong[MAXN];
    vector< vector<int> > V, Vmode;
    vector<int> POS[MAXN];
    int q_dup[MAXN], q_cases;
    void make(int n) {
        N = n, q_cases = 0;
        for (PILE = 1; PILE * PILE < N; PILE <<= 1);
        
        V.clear(), Vmode.clear();
        for (int l = 0, r; l < N; l = r+1) {
            r = min(l + PILE - 1, N-1);
            V.push_back(vector<int>(A+l, A+r+1));
            Vmode.push_back(vector<int>());
        }
        
        for (int i = 0; i < V.size(); i++) {
            sort(V[i].begin(), V[i].end());
            int mx_cnt = 1, cnt = 1;
            for (int j = 1; j <= V[i].size(); j++) {
                if (j == V[i].size() || V[i][j] != V[i][j-1]) {
                    if (cnt > mx_cnt)	
                        mx_cnt = cnt, Vmode[i].clear();
                    if (cnt == mx_cnt)
                        Vmode[i].push_back(V[i][j-1]);
                    cnt = 1;
                } else {
                    cnt++;
                }
            }
        }
        
        for (int i = 1; i <= N; i++) // value range
            POS[i].clear(), q_dup[i] = 0;
        for (int i = 0; i < N; i++)
            POS[A[i]].push_back(i);
        for (int i = N-1; i >= 0; i--)
            belong[i] = i / PILE;
    }
    int compute_cnt(int x, int l, int r) {
        if (q_dup[x] == q_cases)
            return 0;
        q_dup[x] = q_cases;
        int va = (int) (lower_bound(POS[x].begin(), POS[x].end(), l) - POS[x].begin()) - 1;
        int vb = (int) (upper_bound(POS[x].begin(), POS[x].end(), r) - POS[x].begin()) - 1;
        return vb - va;
    }
    void query(int l, int r, int &a, int &b) {
        static int t;
        q_cases++;
        a = b = 0;
        if (belong[l] == belong[r]) {
            for (int i = l; i <= r; i++) {
                t = compute_cnt(A[i], l, r);
                if (t > a)	a = t, b = 0;
                if (t == a)	b++;
            }	
            return ;		
        }
        for (int i = belong[l]+1; i < belong[r]; i++) {
            for (int j = 0; j < Vmode[i].size(); j++) {
                t = compute_cnt(Vmode[i][j], l, r);
                if (t > a)	a = t, b = 0;
                if (t == a)	b++;
            }
        }
        for (int i = (belong[a]+1)*PILE-1; i >= l; i--) {
            t = compute_cnt(A[i], l, r);
            if (t > a)	a = t, b = 0;
            if (t == a)	b++;
        }
        for (int i = (belong[b])*PILE; i <= r; i++) {
            t = compute_cnt(A[i], l, r);
            if (t > a)	a = t, b = 0;
            if (t == a)	b++;
        }
    }
} dream;
int main() {
    int n, m, l, r, a, b;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &dream.A[i]);
        dream.make(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &l, &r);
            l--, r--;
            dream.query(l, r, a, b);
            printf("%d %d\n", a, b);
        }
    }
    return 0;
}

分塊在線 2

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
const int MAXS = 35;
class ModeQuery {
public:
    struct Kit {
        unsigned short cnt[MAXN], freq[MAXN];
        int mode_idx;
        Kit() {
            init();
        }
        void init() {
            mode_idx = 0;
        }
        void add(int x, int val) {
            freq[cnt[x]]--;
            cnt[x] += val;
            freq[cnt[x]]++;
            if (cnt[x] > mode_idx)
                mode_idx = cnt[x];
        }
        void resume(int x, int val) {
            freq[cnt[x]]--;
            cnt[x] -= val;
            freq[cnt[x]]++;
        } 
    } f[MAXS * MAXS/2], kit;
    int fr[MAXS][MAXS];
    int A[MAXN], N, PILE, belong[MAXN];
    vector< pair<int, int> > V;
    void heavy() {
        int ff = 0;
        for (int i = 0; i < V.size(); i++)
            for (int j = i; j < V.size(); j++)
                fr[i][j] = ff++;
        for (int i = 0; i < V.size(); i++)
            for (int j = 0; j < i; j++)
                fr[i][j] = ff;
        for (int i = 0; i < V.size(); i++) {
            f[fr[i][i]].init();
            for (int j = V[i].first; j <= V[i].second; j++)
                f[fr[i][i]].add(A[j], 1);
        }
        for (int i = 0; i < V.size(); i++) {
            for (int j = i+1; j < V.size(); j++) {
                f[fr[i][j]] = f[fr[i][j-1]];
                for (int k = V[j].first; k <= V[j].second; k++)
                    f[fr[i][j]].add(A[k], 1);
            }
        }
    }
    void make(int n) {
        N = n;
        PILE = (int) pow(n, 0.70) + 1;
                
        V.clear();
        for (int l = 0, r; l < N; l = r+1) {
            r = min(l + PILE - 1, N-1);
            V.push_back(make_pair(l, r));
        }
        for (int i = N-1; i >= 0; i--)
            belong[i] = i / PILE;
        heavy();
    }
    void query(int l, int r, int &a, int &b) {
        int bl = belong[l], br = belong[r];
        if (bl == br || r - l <= PILE + 10) {
            kit.init();
            for (int i = l; i <= r; i++)
                kit.add(A[i], 1);
            a = kit.freq[kit.mode_idx], b = kit.mode_idx;
            for (int i = l; i <= r; i++)
                kit.resume(A[i], 1);
            return ;
        }
        if (l >= 0 && belong[l-1] == bl)	
            bl++;
        if (r < N && belong[r+1] == br)
            br--;
        Kit &tmp = f[fr[bl][br]];
        int tmp_mode_idx = tmp.mode_idx;
        for (int i = bl*PILE - 1; i >= l; i--)
            tmp.add(A[i], 1);
        for (int i = (br+1)*PILE; i <= r; i++)
            tmp.add(A[i], 1);
        a = tmp.freq[tmp.mode_idx], b = tmp.mode_idx;
        for (int i = bl*PILE - 1; i >= l; i--)
            tmp.resume(A[i], 1);
        for (int i = (br+1)*PILE; i <= r; i++)
            tmp.resume(A[i], 1);
        tmp.mode_idx = tmp_mode_idx;
    }
} dream;
int main() {
    int n, m, l, r, a, b;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &dream.A[i]);
        dream.make(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &l, &r);
            l--, r--;
            dream.query(l, r, a, b);
            printf("%d %d\n", b, a);
        }
    }
    return 0;
}