POJ 3368 Frequent values

問題

単調非減少な数列A[i]が与えられる。
m個のクエリが与えられるのでそれに答えよ。

クエリ:
二つの整数l,rが与えられる。Aのl番目〜r番目の項のうち、最も出現回数が多い数字の出現回数はいくつか。

制約条件

-100000≦A[i]≦100000
m≦100000
数列の項≦100000

方針

Segment Treeを3つ作る。
それぞれ、「区間内で連続する最も長い項の項数」、「区間の左端を含み、連続する最も長い項の項数」、「区間の右端を含み、連続する最も長い項の項数」
を持たせる。


上手く初期化して、これらを使ってクエリに答えればいい。
問題の「数列は単調非減少」という条件を使ってないことに気づいた。
これを使ったもっと上手い解法があるのかも。

ソースコード

TLEギリギリ(1600ms)

int n,m,N;
int con[MAX], left_con[MAX], right_con[MAX];
int A[MAX_N];

void init(int k,int l,int r){
	if(r-l==1){
		con[k]=left_con[k]=right_con[k]=l<n;
		return;
	}
	init(k*2+1,l,(l+r)/2); init(k*2+2,(l+r)/2,r);
	con[k]=max(con[k*2+1],con[k*2+2]);
	left_con[k]=left_con[k*2+1]; right_con[k]=right_con[k*2+2];
	
	if((l+r)/2<n&&A[(l+r)/2-1]==A[(l+r)/2]){
		con[k]=max(con[k],right_con[k*2+1]+left_con[k*2+2]);
		if(left_con[k*2+1]==(l+r)/2-l)left_con[k]+=left_con[k*2+2];
		if(right_con[k*2+2]==r-(l+r)/2)right_con[k]+=right_con[k*2+1];
	}
}
pair<int,pi> query(int a,int b,int k,int l,int r){
	if(a<=l&&r<=b)return mp(con[k],mp(left_con[k],right_con[k]));
	if(b<=l||a>=r)return mp(0,mp(-inf,-inf));
	pair<int,pi> p=query(a,b,k*2+1,l,(l+r)/2), q=query(a,b,k*2+2,(l+r)/2,r);
	
	int tcon=max(p.first,q.first);
	int mid=-inf,L=p.second.first,R=q.second.second;
	if((l+r)/2<n&&A[(l+r)/2-1]==A[(l+r)/2]){
		mid=p.second.second+q.second.first;
		tcon=max(mid,tcon);
		if(L==(l+r)/2-l)L=mid;
		if(R==r-(l+r)/2)R=mid;
	}
	
	return mp(tcon,mp(L,R));
}
int main()
{
	while(scanf("%d",&n),n){
		scanf("%d",&m);
		rep(i,n)scanf("%d",A+i);
		for(N=1;N<n;N<<=1);
		
		init(0,0,N);
		
		rep(i,m){
			int l,r; scanf("%d%d",&l,&r);
			pair<int,pi> ans=query(l-1,r,0,0,N);
			printf("%d\n",ans.first);
		}
	}
	return 0;
}