|
|
  /**//*
 上金工实习，无聊，找到题目想想吧，那就pku 3368吧，一直想做掉却一直没想法，题目意思很明确，
给定一串序列，然后是m条询问，问[a, b]区间之间出现的数字频率最多的是哪个数，由于m很大，所以
询问的复杂度必须要是log(n)，这样一来就先确定下来是线段树了，但是以前没深入想下去，
重新看了遍题目，然后到了8教就开始想，突然就有思路了，主要是以前有个限制条件没看见，
有了这个限制条件题目就变得简单了。就是这句话in non-decreasing order，所有的数非递减排列。
换言之，就是说如果两个数相同的话，他们必定生活在以前，并且中间的数和他们也相同。
于是就有了nlog(n)的算法：
对于所有的数均设定一个组号，也可以叫离散化吧，相同的数有相同的组号，然后将各个数的频率统计后
记录在一个数组中，表示该类数的大小，然后对于输入的询问[x, y]，直接查询它们在哪个组，分三种情况
1. 如果x和y在一个组，那么最长长度就是y - x + 1
2. 如果组号相差1，那么找出两者的分界点z(假设z点和x点组号相同)，那么答案就是Max{z - x + 1, y - z}
3. 如果相差大于1，那么先将两头截掉，统计大的记录，再和中间那段的最大值比较大小，中间那段的最大值可以用线段树区间查询最值
 */
 #include <iostream>
using namespace std;
struct point  {
int start;
int end;
int num;
int coun;
}p[ 100010 ];
int ori[ 100010 ];
int n, T;
int Rhash[ 100010 ]; //第i个数所在新的分组中的编号
struct Seg {
int num;
int Count;
}tree[1000010];
void init() {
T = 1;
p[1].start = 0;
p[1].end = 0;
p[1].coun = 1;
p[1].num = ori[0];
Rhash[ 0 ] = 1;
int i;
  for(i = 1; i < n; i++) {
if(ori[i] == ori[i-1]) {
p[ T ].coun ++;
p[ T ].end = i;
}else {
T ++;
p[ T ].num = ori[i];
p[ T ].coun = 1;
p[ T ].start = i;
p[ T ].end = i;
 }
Rhash[ i ] = T;
}
}
void Build(int P, int l, int r) {
int mid = (l + r) / 2;
if(l == r) {
tree[P].Count = p[l].coun;
tree[P].num = p[l].num;
return ;
}
Build(2*P, l, mid);
Build(2*P+1, mid+1, r);
if(tree[2*P].Count > tree[2*P+1].Count) {
tree[P] = tree[2*P];
}else
tree[P] = tree[2*P+1];
}
int Query(int P, int a, int b, int l, int r) {
if(a == l && r == b) {
return tree[P].Count;
}
int mid = (l + r) / 2;
if(b <= mid) {
return Query(2*P, a, b, l, mid);
}else if(mid + 1 <= a) {
return Query(2*P+1, a, b, mid+1, r);
}else {
int x = Query(2*P, a, mid, l, mid);
int y = Query(2*P+1, mid+1, b, mid+1, r);
return x > y ? x : y;
}
}
int Solve(int x, int y) {
//如果所在组号相同，说明中间所有数都是一样的，直接返回区间长度
if(Rhash[x] == Rhash[y]) {
return y - x + 1;
}
//如果组号相差1，说明中间必定由一个分段点，将[x, y]线段分成两段，去大的
else if(Rhash[x] + 1 == Rhash[y]) {
int l = p[ Rhash[x] ].end - x + 1;
int r = y - p[ Rhash[y] ].start + 1;
return l > r ? l : r;
}
//如果组号相差1以上，那么端点的两个取最大，中间的区段用线段树查询最大值
else {
int l = p[ Rhash[x] ].end - x + 1;
int r = y - p[ Rhash[y] ].start + 1;
int Max = l > r ? l : r;
int ans = Query(1, Rhash[x] + 1, Rhash[y] - 1, 1, T);
return Max > ans ? Max : ans;
}
}
int main() {
int i;
int q, x, y;
while(scanf("%d", &n) != EOF && n) {
scanf("%d", &q);
for(i = 0; i < n; i++) {
scanf("%d", &ori[i]);
}
init();
Build(1, 1, T);
while(q--) {
scanf("%d %d", &x, &y);
x --; y --;
printf("%d\n", Solve(x, y) );
}
}
return 0;
}
|