frequent values(线段).cpp

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

//保存线段
//题意是连续线段，所以可以排序后进行判断
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
int n,m;
struct node {
	int x,y,s;
	bool operator < (const node & t) const {
		return s > t.s;
	}
}line[100100];

int main()
{
	int all,pre,now,x,y;
	int i,j;
	while (scanf("%d",&n), n) {
		scanf("%d",&m);
		all = 0;
		scanf("%d",&pre);
		line[all].x = 1;
		for (i=2;i<=n;i++) {
			scanf("%d",&now);
			if (now != pre) {
				line[all].y = i-1;
				line[all].s = line[all].y - line[all].x +1;
				pre = now;
				all ++;
				line[all].x = i;
			}
		}
		line[all].y = n;
		line[all].s = line[all].y - line[all].x +1;
		all ++;
		sort(line,line+all);
		
		for (i=0;i<m;i++) {
			scanf("%d %d",&x,&y);
			int mmax = -1;
			for (j=0;j<all;j++) {
				if (mmax > line[j].s) {
					break ;
				}
				if (x <= line[j].x && line[j].x <= y) {//x in
					if (line[j].y <= y) {//all in
						if (mmax < line[j].s) {
							mmax = line[j].s;
						}
						break ;
					}
					else {//x in
						now = y - line[j].x +1;
						pre = line[j].x - x;
						if (now > mmax) {
							mmax = now;
						}
						if (now >= pre) {
							break ;
						}
						else {
							y = line[j].x -1;
						}
					}
				}
				else if ( x <= line[j].y && line[j].y <= y) {//y in
					now = line[j].y - x +1;
					pre = y - line[j].y;
					if (now > mmax) {
						mmax = now;
					}
					if (now >= pre) {
						break ;
					}
					else {
						x = line[j].y +1;
					}
				}
				else if (line[j].x <= x && y <= line[j].y) {
					mmax = y - x +1;
					break ;
				}
			}//for
			printf("%d\n", mmax);
		}
	}
}