首页 > 代码库 > POJ 3368 Frequent values
POJ 3368 Frequent values
You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Sample Output
1
4
3
以前还没怎么结构体和数组有很大的区别,做完这个题以后,深有体会,结构体在树状数组里面太重要了,这个题打算用线段树和RMQ写。
这个题让我有种树中树的感觉,实现过程在代码中详解!!!
AC代码如下:
///线段树 547MS 3660K #include<iostream> #include<cstring> #include<cstdio> #define M 100010 using namespace std; struct H { int l,r,nn; }trees[M]; struct HH { int l,r,um; }tree[M]; int num[M],hash[M]; int dp[M][20]; int n,m; void build_trees(int jd ,int l,int r) { tree[jd].l=l;tree[jd].r=r; if(l==r) { tree[jd].um=trees[l].nn; return ; } int mid = (l+r)/2; build_trees(jd*2,l,mid); build_trees(jd*2+1,mid+1,r); tree[jd].um=max(tree[jd*2].um,tree[jd*2+1].um); } int query(int jd,int l,int r) { int ans = 0; if(l<=tree[jd].l&&r>=tree[jd].r) return tree[jd].um; int mid = (tree[jd].l+tree[jd].r)/2; if(l<=mid) ans=max(ans,query(jd*2,l,r)); if(r>mid) ans=max(ans,query(jd*2+1,l,r)); return ans; } int main() { int i,j; int a,b; while(~scanf("%d",&n)) { if(n==0) break; scanf("%d",&m); for(i=1;i<=n;i++) { scanf("%d",&num[i]); } memset(trees,0,sizeof trees); int tt=1; trees[tt].l=1; int cont =1; hash[1]=1; for(i=2;i<=n;i++) { if(num[i]!=num[i-1]) { trees[tt].r=i-1; trees[tt].nn=cont; tt++; trees[tt].l=i; cont=1; hash[i]=tt; } else{ cont++;hash[i]=tt; } if(i==n) { trees[tt].r=i;trees[tt].nn=cont; } } // for(i=1;i<=n;i++) // cout<<num[i]<<" "; // cout<<endl; // for(i=1;i<=n;i++) // cout<<hash[i]<<" ";//hash记录的是i号在第几类 // cout<<endl; // for(i=1;i<=tt;i++) // cout<<"<"<<trees[i].l<<" "<<trees[i].nn<<" "<<trees[i].r<<">"<<endl;//将这个注释消掉,你应该能看明白很多东西 build_trees(1,1,tt);//建树,一类别编号为左右区间,相同数的个数为最大值建树 for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); if(hash[a]==hash[b])//当区间同类的时候,就是区间长度 printf("%d\n",(b-a+1)); else//不同类时 { int ans = trees[hash[a]].r-a+1;//计算最左区间 if(b-trees[hash[b]].l+1>ans) ans=b-trees[hash[b]].l+1;//计算最右区间 if(hash[b]-hash[a]>1) { int aa=query(1,hash[a]+1,hash[b]-1);//如果中间还有不同的类,需要求最值 if(aa>ans) ans=aa; } printf("%d\n",ans); } } } return 0; }
RMQ~~~~!!快得不多,写法也差不多
/// RMQ 454MS 9948K <span style="font-size:14px;">#include<iostream> #include<cstring> #include<cstdio> #define M 100010 using namespace std; struct H { int l,r,nn; }trees[M]; int dp[M][20]; int num[M],hash[M]; int n,m; void RMQ(int n) { int i,j; memset(dp,0,sizeof dp); for(i=1;i<=n;i++) dp[i][0]=trees[i].nn; for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int rmq(int l,int r) { int k=0; while((1<<(k+1))<=r-l+1) { k++; } return max(dp[l][k],dp[r-(1<<k)+1][k]); } int main() { int i,j; int a,b; while(~scanf("%d",&n)) { if(n==0) break; scanf("%d",&m); for(i=1;i<=n;i++) { scanf("%d",&num[i]); } memset(trees,0,sizeof trees); int tt=1; trees[tt].l=1; int cont =1; hash[1]=1; for(i=2;i<=n;i++) { if(num[i]!=num[i-1]) { trees[tt].r=i-1; trees[tt].nn=cont; tt++; trees[tt].l=i; cont=1; hash[i]=tt; } else{ cont++;hash[i]=tt; } if(i==n) { trees[tt].r=i;trees[tt].nn=cont; } } RMQ(tt); // for(i=1;i<=n;i++) // cout<<num[i]<<" "; // cout<<endl; // for(i=1;i<=n;i++) // cout<<hash[i]<<" "; // cout<<endl; // for(i=1;i<=tt;i++) // cout<<"<"<<trees[i].l<<" "<<trees[i].nn<<" "<<trees[i].r<<">"<<endl; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); if(hash[a]==hash[b]) printf("%d\n",(b-a+1)); else { int ans = trees[hash[a]].r-a+1; if(b-trees[hash[b]].l+1>ans) ans=b-trees[hash[b]].l+1; if(hash[b]-hash[a]>1) { int aa=rmq(hash[a]+1,hash[b]-1); if(aa>ans) ans=aa; } printf("%d\n",ans); } } } return 0; }</span>