2007/2008 ACM International Collegiate Programming Contest
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
*/
文章定位：
