[UVA][笛卡爾樹RMQ] 11235 - Frequent values
University of Ulm Local Contest
Problem F: Frequent values
You are given a sequence of n integers a1 , a2 , ... , an 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 ai , ... , aj.
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 a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+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
*/