|
|
  /**//*
 上金工實習，無聊，找到題目想想吧，那就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;
}
|