|
|
  /**//*
 上金工實(shí)習(xí)，無(wú)聊，找到題目想想吧，那就pku 3368吧，一直想做掉卻一直沒(méi)想法，題目意思很明確，
給定一串序列，然后是m條詢(xún)問(wèn)，問(wèn)[a, b]區(qū)間之間出現(xiàn)的數(shù)字頻率最多的是哪個(gè)數(shù)，由于m很大，所以
詢(xún)問(wèn)的復(fù)雜度必須要是log(n)，這樣一來(lái)就先確定下來(lái)是線(xiàn)段樹(shù)了，但是以前沒(méi)深入想下去，
重新看了遍題目，然后到了8教就開(kāi)始想，突然就有思路了，主要是以前有個(gè)限制條件沒(méi)看見(jiàn)，
有了這個(gè)限制條件題目就變得簡(jiǎn)單了。就是這句話(huà)in non-decreasing order，所有的數(shù)非遞減排列。
換言之，就是說(shuō)如果兩個(gè)數(shù)相同的話(huà)，他們必定生活在以前，并且中間的數(shù)和他們也相同。
于是就有了nlog(n)的算法：
對(duì)于所有的數(shù)均設(shè)定一個(gè)組號(hào)，也可以叫離散化吧，相同的數(shù)有相同的組號(hào)，然后將各個(gè)數(shù)的頻率統(tǒng)計(jì)后
記錄在一個(gè)數(shù)組中，表示該類(lèi)數(shù)的大小，然后對(duì)于輸入的詢(xún)問(wèn)[x, y]，直接查詢(xún)它們?cè)谀膫€(gè)組，分三種情況
1. 如果x和y在一個(gè)組，那么最長(zhǎng)長(zhǎng)度就是y - x + 1
2. 如果組號(hào)相差1，那么找出兩者的分界點(diǎn)z(假設(shè)z點(diǎn)和x點(diǎn)組號(hào)相同)，那么答案就是Max{z - x + 1, y - z}
3. 如果相差大于1，那么先將兩頭截掉，統(tǒng)計(jì)大的記錄，再和中間那段的最大值比較大小，中間那段的最大值可以用線(xiàn)段樹(shù)區(qū)間查詢(xún)最值
 */
 #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個(gè)數(shù)所在新的分組中的編號(hào)
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) {
//如果所在組號(hào)相同，說(shuō)明中間所有數(shù)都是一樣的，直接返回區(qū)間長(zhǎng)度
if(Rhash[x] == Rhash[y]) {
return y - x + 1;
}
//如果組號(hào)相差1，說(shuō)明中間必定由一個(gè)分段點(diǎn)，將[x, y]線(xiàn)段分成兩段，去大的
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;
}
//如果組號(hào)相差1以上，那么端點(diǎn)的兩個(gè)取最大，中間的區(qū)段用線(xiàn)段樹(shù)查詢(xún)最大值
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;
}
|