PKU 3368 - Frequent values

問題文 : Frequent values

解法 :
各ノードは昇順になっているため、各数字の出現頻度をノードとして持つセグメント木を構築する.
各クエリについて, a[s] = a[t]であればt - s + 1を, そうでなければa[s]とa[t]を適切なだけ削り, RMQの処理を行う.

コード :

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int seg[1 << 18];
int size;

void init(int n)
{
	size = 1;
	while (size < n) size *= 2;
	
	memset(seg, -1, sizeof(seg));
}

void update(int k, int x)
{
	k += size - 1;
	seg[k] = x;
	
	while (k > 0){
		k = (k - 1) / 2;
		seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
	}
}

int getMax(int a, int b, int k, int l, int r)
{
	if (b <= l || r <= a){
		return (-1);
	}
	
	if (a <= l && r <= b){
		return (seg[k]);
	}
	int lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2);
	int rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
	
	return (max(lch, rch));
}

int main()
{
	int n, q;
	int a[100000];
	map<int, int> ord;
	
	while (1){
		scanf("%d", &n);
		if (n == 0) break;
		
		init(n);
		
		scanf("%d", &q);
		for (int i = 0; i < n; i++){
			scanf("%d", &a[i]);
		}
		
		ord[a[0]] = 0;
		int idx = 1;
		for (int i = 1; i < n; i++){
			if (a[i] != a[i - 1]){
				update(ord[a[i - 1]], upper_bound(a, a + n, a[i - 1]) - lower_bound(a, a + n, a[i - 1]));
				ord[a[i]] = idx++;
			}
		}
		update(ord[a[n - 1]], upper_bound(a, a + n, a[n - 1]) - lower_bound(a, a + n, a[n - 1]));
		
		for (int i = 0; i < q; i++){
			int s, g;
			scanf("%d %d", &s, &g);
			if (a[--s] == a[--g]){
				printf("%d\n", g - s + 1);
				continue;
			}
			update(ord[a[s]], upper_bound(a + s, a + g + 1, a[s]) - lower_bound(a + s, a + g + 1, a[s]));
			update(ord[a[g]], upper_bound(a + s, a + g + 1, a[g]) - lower_bound(a + s, a + g + 1, a[g]));
			
			printf("%d\n", getMax(ord[a[s]], ord[a[g]] + 1, 0, 0, size));
			
			update(ord[a[s]], upper_bound(a, a + n, a[s]) - lower_bound(a, a + n, a[s]));
			update(ord[a[g]], upper_bound(a, a + n, a[g]) - lower_bound(a, a + n, a[g]));
		}
	}
	return (0);
}