2007/2008 ACM International Collegiate Programming Contest
University of Ulm Local Contest

Problem F: Frequent values

You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j.

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

Sample Output

1
4
3

---

A naive algorithm may not run in time!

希望在看此篇文章之前，已經先了解使用 segment tree 解決這題的 RMQ 問題。

而這只是實作笛卡爾樹對於 RMQ 的離線詢問，可以在 O(n) - O(1) 完成。

也就是說當數列有 n 個數字，詢問次數有 m 個時，消耗時間為 O(n+m)。

這種方法並不適用有單點更新的支持。

先稍微認識一下笛卡爾樹 (一種二元樹)，每個節點為 <key, value>，只看 key 時，笛卡爾樹是一棵二元搜尋樹，而看 value 時，它是一個最大堆 (或者是最小堆)。

在建造前，先撇清一點，笛卡爾樹的深度可能到達 n，與一般平衡樹不同。

笛卡爾樹如何建造 ? 假使已經對於 key 值由小到大排序 (升排序)，那麼將點依序插入笛卡爾樹，能保證的是－由於要符合二元搜尋樹，新加入的點一定是這棵樹某個節點的右節點。知道這一點後，再往前考慮前一次插入的點(它原本也符合再某節點的右節點)，往這個節點往上爬，直到符合最大堆(性質 node.v > new_insert.v)，這時將這個節點的右子樹移到新加入節點的左子樹 (此時符合二元搜尋樹的性質，也保有原本堆的性質)。就這麼持續入點下去。

這麼發現，往上爬的次數不超過節點個數，因為每個節點只會從右子樹換到左子樹。

均攤下 O(n)

---

如何利用這個笛卡爾樹解決最簡單的 RMQ 問題，對於 <key, value> = <i, A[i]> 所建造的笛卡爾樹，可以利用 LCA 的 tarjan 算法(離線作法) 在 O(n) 時間內完成。

一般最常見的是使用 segment tree 完成 RMQ 線上查詢，若要解決 LCA 問題也可以透過 Euler travel 轉換成 RMQ 問題後用 segment tree，如此一來是 O(n) - O(log n)。

然而使用笛卡爾樹就是將 RMQ 轉換成 LCA 的一種離線工具。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
struct Node {
    int index;
    int val, lson, rson, parent;
};
Node D[100005];
int A[100005], B[100005];
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].val < D[index].val)
        p = D[p].parent;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
int parent[100005];
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    parent[x] = y;
}
struct Qi {
    int q, i;
    Qi(int a = 0, int b = 0):q(a), i(b) {
    }
};
vector<Qi> query[100005];
int used[100005];
int oput[100000];
void tarjan(int nd) {
    used[nd] = 1;
    for(vector<Qi>::iterator it = query[nd].begin();
        it != query[nd].end(); it++) {
        if(used[it->q]) {
            oput[it->i] = max(B[findp(it->q)], oput[it->i]);
        }
    }
    int u;
    if(u = D[nd].lson) {
        tarjan(u), joint(u, nd);
    }
    if(u = D[nd].rson) {
        tarjan(u), joint(u, nd);
    }
}

int leftmost[100005], rightmost[100005];
void build(int A[], int N, int B[]) {
    int before = A[1], cnt = 0;
    for(int i = 1; i <= N; i++) {
        if(A[i] == before)
            cnt++;
        else
            cnt = 1;
        B[i] = cnt, before = A[i];
    }
    leftmost[1] = 1, rightmost[N] = N;
    for(int i = 2; i <= N; i++) {
        leftmost[i] = A[i] == A[i-1] ? leftmost[i-1] : i;
    }
    for(int i = N-1; i >= 1; i--) {
        rightmost[i] = A[i] == A[i+1] ? rightmost[i+1] : i;
    }
}
int main() {
    int N, Q, x, y;
    while(scanf("%d %d", &N, &Q) == 2 && N) {
        for(int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
        build(A, N, B);
        for(int i = N; i >= 0; i--) {
            parent[i] = i;
            query[i].clear();
            used[i] = 0;
        }
        D[0].val = 0x3f3f3f3f;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].val = B[i], D[i].index = i;
        }
        for(int i = 1; i <= N; i++)
            insertCartesianTree(i, D);
        for(int i = 0; i < Q; i++) {
            scanf("%d %d", &x, &y);
            int ni, nj;
            ni = rightmost[x] + 1;
            nj = leftmost[y] - 1;
            oput[i] = 0;
            if(ni <= nj) {
                query[ni].push_back(Qi(nj, i));
                query[nj].push_back(Qi(ni, i));
                oput[i] = max(ni - x, y - nj);
            } else {
                if(A[x] != A[y])
                    oput[i] = max(ni - x, y - nj);
                else
                    oput[i] = y - x + 1;
            }
        }
        tarjan(D[0].rson);
        for(int i = 0; i < Q; i++) {
            printf("%d\n", oput[i]);
        }
    }
    return 0;
}
/*
Sample Input:
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10

Sample Output:
1
4
3

*/