frequent values(线段树).cpp

杭电acm解题报告2001---2099.

//此题推荐，需要转换
#include <cstdio>
#include <string>
#define MAX 100100

int n,q;
int num[MAX];//原始值
struct line {
	int x,y,s;//记录区间和次数
}ls[2*MAX];//hash保存出现次数，这个才是真正应该来作RMQ的
struct node {
	node * pleft,* pright;
	int left,right;
	line mmax;
};
node mem[4*MAX];
int mem_pos;

node * new_node()
{
	node * p = &mem[mem_pos ++ ];
	memset(p,0,sizeof(node));
	return p;
}

node * make_tree(int x,int y)
{
	int mid = (x+y)/2;
	node * root = new_node();

	root ->left = x;
	root ->right = y;
	
	if (y - x <= 1) {
		if (ls[x].s > ls[y].s) {
			root ->mmax = ls[x];
		}
		else {
			root ->mmax = ls[y];
		}
	}
	else {
		root ->pleft = make_tree(x,mid);	
		root ->pright = make_tree(mid,y);
		node * pl = root ->pleft;
		node * pr = root ->pright;
		if (pl ->mmax.s > pr ->mmax.s) {
			root ->mmax = pl ->mmax;
		}
		else {
			root ->mmax = pr ->mmax;
		}
	}

	return root;
}

int get_max(node * root,int nx,int ny)
{
	if (nx == root ->left && ny == root ->right) {
		return root ->mmax.s;
	}
	int nmid = (root ->left + root ->right)/2;
	if (nx >= nmid) {
		return get_max(root ->pright,nx,ny);
	}
	if (ny <= nmid) {
		return get_max(root ->pleft,nx,ny);
	}
	int max1 = get_max(root ->pleft,nx,nmid);
	int max2 = get_max(root ->pright,nmid,ny);
	return max1 > max2 ? max1 : max2;
}

int main()
{
	int i,x,y;
	int mmax,mmin;
	node * root;
	
	while (scanf("%d",&n), n) {
		scanf("%d",&q);
		mem_pos = 0;
		memset(ls,0,sizeof(ls));

		scanf("%d",&num[1]);
		ls[100001 + num[1]].s ++;
		ls[100001 + num[1]].x = 1;
		for (i=2;i<=n;i++) {
			scanf("%d",&num[i]);
			ls[100001 + num[i]].s ++;
			if (num[i] != num[i-1]) {
				ls[100001 + num[i-1]].y = i-1;
				ls[100001 + num[i]].x = i;
			}
		}
		ls[100001 + num[n]].y = n;

		root = make_tree(100001+num[1], 100001+num[n]);
		while (q--) {
			scanf("%d %d",&x,&y);
			int nx = 100001+num[x];
			int ny = 100001+num[y];
			mmax = -1;
			if( x == y || nx == ny) {//在一个区间内
				printf("%d\n", y-x+1);
			}
			else {//先缩小区间，取整
				if (ny-1 >= nx+1) {//y - x >= 2
					if (nx+1 == ny-1) {
						mmax = ls[nx+1].s;
					}
					else {
						mmax = get_max(root,nx+1,ny-1);
					}
				}
				int l1 = ls[nx].y - x +1;//两边剩余部分
				int l2 = y - ls[ny].x +1;
				if (l1 < l2) {
					l1 = l2;
				}
				if (mmax < l1) {
					mmax = l1;
				}
				printf("%d\n",mmax);
			}
		}
	}
}