frequent.java

Ulm大学2007年竞赛题和解题报告

// Adrian Kuegel
// Date: 17. 6. 2007
// Complexity: O(n log n + q)

import java.io.*;
import java.util.*;

public class frequent {
	public static void main(String [] args) throws Exception {
		Scanner in = new Scanner(new File("frequent.in"));
		int [] log2 = new int[100001];
		for (int i=1,p = 0; i<100001; ++i) {
			if ((1<<p)<=i) ++p;
			log2[i] = p;
		}
		while(true) {
			int n = in.nextInt();
			if (n == 0)
				break;
			int q = in.nextInt();
			int [] a = new int[n];
			for (int i=0; i<n; ++i)
				a[i] = in.nextInt();
			int p2 = log2[n];
			int [][] best = new int[p2][n];
			int [][] pref = new int[p2][n];
			int [][] suff = new int[p2][n];
			for (int i=0; i<n; ++i)
				pref[0][i] = best[0][i] = suff[0][i] = 1;
			// precalculate answers for all ranges which are a power of two -> O(n log n)
			for (int p=1; p<p2; ++p) {
				int d = (1<<p);
				for (int i=0; i+d<=n; ++i) {
					pref[p][i] = pref[p-1][i]+(a[i+d/2] == a[i]?pref[p-1][i+d/2]:0);
					suff[p][i] = suff[p-1][i+d/2]+(a[i+d-1] == a[i+d/2-1]?suff[p-1][i]:0);
					best[p][i] = Math.max(best[p-1][i],best[p-1][i+d/2]);
					if (a[i+d/2-1] == a[i+d/2])
						best[p][i] = Math.max(best[p][i],suff[p-1][i]+pref[p-1][i+d/2]);
				}
			}
			while(q-- > 0) {
				int i = in.nextInt();
				int j = in.nextInt();
				--i;
				--j;
				int dist = j-i+1;
				int p = log2[dist]-1;
				int d = 1<<p;
				// answer each query in constant time by using two overlapping ranges
				// of size 2^p which cover the whole interval
				int res = Math.max(best[p][i],best[p][j-d+1]);
				// special case: check if the overlapping part contains the maximum
				if (a[i+d-1] == a[j-d+1])
					res = Math.max(res,suff[p][i]+pref[p][j-d+1]-(2*d-dist));
				System.out.println(res);
			}
		}
	}
}