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; }