Problem Solving►UVa

UVa 11235 - Frequent values

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

基本上就是套線段樹的作法(參考之前寫的)。

由於該數列是 非遞減(重要!)，利用把連續的數字的次數作累積(fre)，再放進線段樹。

e.g.

1
2
3
idx:  1   2   3   4   5   6   7   8   9  10
num: -1  -1   1   1   1   1   3  10  10  10
fre:  2   2   4   4   4   4   1   3   3   3

這樣在查詢 沒有被切開 來的數字區段時就可以拿到正確答案，例如：[1, 6] => 4 (1 出現 4 次)。

但是如果是 [1, 3] 時，數字 1 的區段是不完整的，這樣 fre 給出的資訊就不正確了。
所以我們需要對查詢區間的頭尾做檢查，把有被切開的獨立算出，接著剩餘的就會是 完整的數字區間(因為是非遞減) 了。
基本上就是分成三個區段做查詢，左右能直接算出，中間利用線段樹查詢。
e.g.
[4, 9] =>
MAX([4, 6], [7], [8, 9]) => MAX(3, 1, 2) => 3
[2, 8] =>
MAX([2, 2], [3, 7], [8, 8]) => MAX(1, 4, 1) => 4

如果頭尾數字一樣代表中間也都一樣，答案即為查詢長度。

可以利用紀錄每個數字的左右邊界來判斷有無被切開。
e.g.

1
2
3
4
5
6
7
8
9
10
idx:  1   2   3   4   5   6   7   8   9  10
num: -1  -1   1   1   1   1   3  10  10  10
fre:  2   2   4   4   4   4   1   3   3   3

border
left: 1   1   3   3   3   3   7   8   8   8
right:2   2   6   6   6   6   7  10  10  10

left[4]: num[4](1) 它連續的數字段最左邊的位置為 idx = 3。  
right[4]: num[4](1) 它連續的數字段最右邊的位置為 idx = 6。

ref: http://www.algorithmist.com/index.php/UVa_11235

Code

UVa 11235
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
#include <cstdio>
#define N 100005
#define M 262144
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define LC(i) ((i) << 1)
#define RC(i) (((i) << 1) | 1)
#define PADDING 1e9

int arr[N];
int left[N], right[N]; //[n]: arr[n] 連續數字的左右邊界
int fre[N];            //該段數字的長度(次數)
int tree[M];           //segment tree
int T;                 //last level
void build(int n)
{
    //2: head and tail padding
    for (T = 1; T < n + 2; T <<= 1)
        ;
    int i;

    tree[T] = tree[T + n + 1] = 0;
    for (i = 1; i <= n; ++i)
        tree[T + i] = fre[i]; //frequent

    for (; i < T; ++i)
    {
        tree[T + i] = 0; //padding
    }

    for (i = T - 1; i; --i)
        tree[i] = MAX(tree[LC(i)], tree[RC(i)]);
}
int query(int L, int R)
{
    int res = 1;
    //因為是非遞減，頭尾數字一樣時，中間也一樣
    if (arr[L] != arr[R])
    {
        if (L > left[L]) //最左半段有被切
        {
            res = right[L] - L + 1; //最左段的長度
            L = right[L] + 1;
        }

        if (R < right[R]) //最右半段有被切
        {
            res = MAX(res, R - left[R] + 1); //最右段的長度
            R = left[R] - 1;
        }

        if (L < R) //還有剩餘沒被切割到的區段(L==R 時就只有 1 個省略不算)
            for (L += T - 1, R += T + 1; L ^ R ^ 1; L >>= 1, R >>= 1)
            {
                if (~L & 1)
                    res = MAX(res, tree[L ^ 1]);
                if (R & 1)
                    res = MAX(res, tree[R ^ 1]);
            }
    }
    else
        res = R - L + 1;

    return res;
}
inline int read()
{
    int n = 0, neg = 1;
    char c = getchar();
    if (c == '-')
        neg = -1;
    else
        n = c - '0';
    while ((c = getchar()) <= '9' && c >= '0')
        n = n * 10 + c - '0';

    return n * neg;
}
int main()
{
    /*int T;
    for (T = 1; T < N; T <<= 1)
        ;
    printf("%d\n", T * 2);*/

    int n, q;
    while (scanf("%d%d ", &n, &q) == 2)
    {
        int start = 1, last = PADDING, i;
        for (i = 1; i <= n; ++i)
        {
            //non-decreasing
            arr[i] = read();
            if (arr[i] != last)
            {
                for (int k = start; k < i; ++k)
                {
                    right[k] = i - 1;   //上個數字該邊界到 i - 1
                    fre[k] = i - start; //該段數字共有幾個
                }
                //重新開始某段數字
                start = left[i] = i;
                last = arr[i];
            }
            else
                left[i] = start;
        }
        //最後一段 [start, n]
        for (int k = start; k < i; ++k)
        {
            right[k] = i - 1; // (n+1) - 1
            fre[k] = i - start;
        }

        build(n);
        for (int i = 0; i < q; ++i)
        {
            int L = read(), R = read();
            printf("%d\n", query(L, R));
        }
    }

    return 0;
}