最近在研究線段樹(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)這東西還挺耐玩的，它沒(méi)有固定的模式，具體的構(gòu)建方法要依據(jù)不同題目的具體要求而定，雖然如此，不過(guò)大致的思路還是差不多，充其量不過(guò)改改節(jié)點(diǎn)里面的域罷了。
這題我看了半天，因?yàn)榭吹接袇^(qū)間了，而且數(shù)據(jù)量又很大，顯然要用log L的算法，于是只能是線段樹(shù)，可問(wèn)題在于怎么維護(hù)這顆線段樹(shù)？
由于給出的序列一定是非遞減的，所以如果兩個(gè)數(shù)字相同的話，它們中間的數(shù)字肯定相同。
具體的算法是這樣的：
首先對(duì)給出的序列進(jìn)行離散化統(tǒng)計(jì)，將相同的數(shù)字壓縮成一個(gè)節(jié)點(diǎn)，然后統(tǒng)計(jì)出這個(gè)壓縮后的節(jié)點(diǎn)在原序列中起點(diǎn)和終點(diǎn)的位置，以及出現(xiàn)的次數(shù)等。當(dāng)然也要記錄原數(shù)字在離散化后的序列中的位置。
之后就是查詢(xún)，比方說(shuō)[a,b]
1.如果a,b屬于同一個(gè)組，那么區(qū)間長(zhǎng)度就是我們想要的答案 b-a+1;
2.如果a,b組號(hào)相差1，說(shuō)明該區(qū)間被中間截?cái)嗔耍灰謩e研究?jī)蓚?cè)的區(qū)間，取大值即可Max(c-a+1,b-c) ---其中c是中間點(diǎn)---
3.如果a,b組號(hào)相差大于1，先取出兩側(cè)進(jìn)行研究，取大值，然后再用線段樹(shù)，算出中間區(qū)間的最大值，與剛才的那個(gè)數(shù)比較，取出最大值即可。
//This is the source code for POJ 3368
//Coded by abilitytao
//Time:2009年7月24日21:03:20
//PS:This is the first time to using the method of discretization and the Data Structure Segment Tree to solve Problem.
//Worth to Memorize.
//Many thanks to the people on the Internet to share their codes.
//And Special thanks to the Blog owner "英雄哪里出來(lái)".
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAX 100010
struct point
{
int left;
int right;
int num;
int count;
}p[MAX];//這個(gè)數(shù)組用來(lái)存儲(chǔ)離散化之后點(diǎn)的信息
int myarray[MAX];
int n,q,T;
int hash[MAX];//第i個(gè)數(shù)在新的分組中的編號(hào)
struct Segnode
{
int num;//統(tǒng)計(jì)那個(gè)頻率最高的數(shù)字
int count;//統(tǒng)計(jì)頻率最高的數(shù)字出現(xiàn)的次數(shù)
Segnode *lchild;//指向左孩子
Segnode *rchild;//指向右孩子
}Segnodeset[MAX];//預(yù)先開(kāi)辟很多節(jié)點(diǎn)以備使用，可以提升效率
Segnode *Newnode()
{
static int countnum=0;
Segnode *temp=&Segnodeset[countnum++];
temp->lchild=NULL;
temp->rchild=NULL;
return temp;
}
void init()//離散化過(guò)程
{
T=1;
p[T].left=1;
p[T].right=1;
p[T].count=1;
p[T].num=myarray[1];
hash[1]=1;
int i;
for(i=2;i<=n;i++)
{
if(myarray[i]==myarray[i-1])
{
p[T].count++;
p[T].right=i;
}
else
{
T++;
p[T].num=myarray[i];
p[T].count=1;
p[T].left=i;
p[T].right=i;
}
hash[i]=T;
}
}
Segnode *Build (int l,int r)//建立線段樹(shù)，建立的同時(shí)統(tǒng)計(jì)區(qū)間上的最高頻率
{
Segnode *root=Newnode();
if(l==r)
{
root->count=p[l].count;
root->num=p[l].num;
return root;
}
int mid=(l+r)>>1;
root->lchild=Build(l,mid);
root->rchild=Build(mid+1,r);
if(root->lchild->count > root->rchild->count)
{
root->num=root->lchild->num;
root->count=root->lchild->count;
}
else
{
root->num=root->rchild->num;
root->count=root->rchild->count;
}
return root;
}
int Query(Segnode *root,int a,int b,int l,int r)//查詢(xún)函數(shù)
{
if(a==l&&b==r)
{
return root->count;
}
int mid=(l+r)>>1;
if(b<=mid)
{
return Query(root->lchild,a,b,l,mid);
}
else if(mid+1<=a)
{
return Query (root->rchild,a,b,mid+1,r);
}
else
{
int x=Query(root->lchild,a,mid,l,mid);
int y=Query(root->rchild,mid+1,b,mid+1,r);
return x>y?x:y;
}
}
int solve(Segnode *root,int a,int b)//算法核心在這個(gè)函數(shù)
{
if(hash[a]==hash[b])
{
return b-a+1;
}//如果查詢(xún)的兩個(gè)數(shù)在同一組中，很顯然最大的頻數(shù)應(yīng)該等于區(qū)間長(zhǎng)度
else if(hash[a]+1==hash[b])
{
int l=p[hash[a]].right-a+1;
int r=b-p[hash[b]].left+1;
return l>r?l:r;
}//如果組號(hào)相差一，則中間有分段點(diǎn)，截?cái)嘀笕〈蟮?/span>
else
{
int l=p[hash[a]].right-a+1;
int r=b-p[hash[b]].left+1;
int MAXNUM=l>r?l:r;
int ans=Query(root,hash[a]+1,hash[b]-1,1,T);
return MAXNUM>ans?MAXNUM:ans;
}
}
inline void put(int x)//用字符串輸出，用以節(jié)省OI時(shí)間 PS:不過(guò)貌似作用不大
{
if(x< 0)
{
putchar('-');
x = -x;
}
if(x == 0){
putchar('0');
return;
}
char s[20];
int bas = 0;
for(;x;x/=10)s[bas++] = x%10+'0';
for(;bas--;)putchar(s[bas]);
return;
}
int main()
{
int i;
int a,b;
Segnode *root;
while(scanf("%d",&n))
{
if(n==0)
break;
scanf("%d",&q);
for(i=1;i<=n;i++)
{
scanf("%d",&myarray[i]);
}
init();
root=Build(1,T);
while(q--)
{
scanf("%d%d",&a,&b);
put(solve(root,a,b));
putchar('\n');
}
}
return 0;
}