POJ 3368 Frequent values 线段树与RMQ解法

题意：给出n个数的非递减序列，进行q次查询。每次查询给出两个数a，b，求出第a个数到第b个数之间数字的最大频数。

如序列：-1 -1 1 1 1 1 2 2 3

第2个数到第5个数之间出现次数最多的是数字1，它的频数3。

思路：假设查询时的参数为a, b。这道题查询时有以下两种情况：

1、 num[a] = num[b]. 即区间内的数字全相同，此时答案为b - a + 1。

2、如果不相同，则以一般情况来讨论。见下图。

因为序列为非递减序列，因此值相同的数字必然连续出现。将区间分为3部分。num[a]以及与它值相同的区域构成第一部分，num[b]以及与它值相同的区域构成第三部分。区间[a, b]中剩下的构成第二部分。

定义left[i]表示与num[i]值相等的数字从左起开始的下标，right[i]表示与num[i]值相等的数字从右起开始的下标。

由图易知，第二部分里的数字，left与right值均在区间[a，b]内。

当给出区间范围a，b后，第一部分在区间内出现的次数为right[a] - a + 1。第三部分在区间内出现的次数为b - left[b] + 1。

如果right[a] + 1 > left[b] - 1，说明区间没有第二部分，直接输出上面两个值中的较大者。

如果存在第二部分，需要求出第二部分里的最大频数。不过这次就非常好求了，因为所有的数开始和结束都是在第二部分中，不存在部分出现的情况。定义tmax[i] = right[i] - left[i] + 1。则第二部分里数字的最大出现次数，即为该区间内tmax的最大值。将该值求出后与前面一三部分求出的较大者比较，最大的值即为最终答案。

因为查询量巨大，当第二部分需要计算时，可以采用线段树或者rmq。

现将两种方法的代码都给出。根据提交的结果来看，线段树所需空间远小于rmq，且速度稍快一点（不排除服务器的偶然性以及我rmq代码的效率比较低等原因）。

线段树求解代码

 #include<stdio.h>

 #include<algorithm>

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define maxn 100020

 #define inf 0x3f3f3f3f

 using namespace std;

 int num[maxn], left[maxn], right[maxn], tmax[maxn<<];

 void PushUp(int rt)

 {

     tmax[rt] = max(tmax[rt<<], tmax[rt<<|]);

 }

 void build(int l,int r,int rt)

 {

     if (l == r)

     {

         tmax[rt] = right[l] - left[l] + ;

         return;

     }

     int m = (l + r) >> ;

     build(lson);

     build(rson);

     PushUp(rt);

 }

 int query(int L,int R,int l,int r,int rt)

 {

     if (L <= l && r <= R) return tmax[rt];

     int m = (l + r) >> ;

     int ret = -inf;

     if (L <= m) ret = max(ret, query(L, R, lson));

     if (m < R) ret = max(ret, query(L, R, rson));

     return ret;

 }

 int main()

 {

     int n, q;

     //freopen("data.in", "r", stdin);

     while (~scanf("%d",&n) && n)

     {

         scanf("%d",&q);

         for (int i = ; i < n; i++)

         {

             scanf("%d",&num[i]);

             if (!i || num[i] != num[i-]) left[i] = i;

             else left[i] = left[i-];

         }

         for (int i = n - ; i > -; i--)

         {

             if (i == (n - ) ||num[i] != num[i+])

                 right[i] = i;

             else right[i] = right[i+];

         }

         build(, n - , );

         while (q--)

         {

             int a, b;

             scanf("%d%d",&a,&b);

             a--; b--;

             if (num[b] == num[a]) printf("%d\n", b - a + );

             else

             {

                 int tem = max(right[a] - a + , b - left[b] + );

                 if (right[a] +  > left[b] - ) printf("%d\n",tem);

                 else printf("%d\n", max(tem, query(right[a] + , left[b] - , , n - , )));

             }

         }

     }

     return ;

 }

================================

rmq st算法求解代码

 #include<stdio.h>

 #include<math.h>

 #include<algorithm>

 #define maxn 100020

 using namespace std;

 int num[maxn], left[maxn], right[maxn], tmax[maxn][];

 void st(int n)

 {

     int k = (int)(log((double)n) / log(2.0));

     for (int i = ; i < n; i++)

         tmax[i][] = right[i] - left[i] + ;//递推的初值

     for (int j = ; j <= k; j++)

         for (int i = ; i + ( << j) -  < n; i++)

         {

             int m = i + ( << (j - ));//求出中间值

             tmax[i][j] = max(tmax[i][j-], tmax[m][j-]);

         }

 }

 //查询i和j之间的最值，注意i是从0开始的

 int rmq(int i, int j)

 {

     int k = (int)(log(double(j - i + )) / log(2.0));

     int t1 = max(tmax[i][k], tmax[j-(<<k)+][k]);

     return t1;

 }

 int main()

 {

     int n, q;

     //freopen("data.in", "r", stdin);

     while (~scanf("%d",&n) && n)

     {

         scanf("%d",&q);

         for (int i = ; i < n; i++)

         {

             scanf("%d",&num[i]);

             if (!i || num[i] != num[i-]) left[i] = i;

             else left[i] = left[i-];

         }

         for (int i = n - ; i > -; i--)

         {

             if (i == (n - ) ||num[i] != num[i+])

                 right[i] = i;

             else right[i] = right[i+];

         }

         st(n);

         while (q--)

         {

             int a, b;

             scanf("%d%d",&a,&b);

             a--; b--;

             if (num[b] == num[a]) printf("%d\n", b - a + );

             else

             {

                 int tem = max(right[a] - a + , b - left[b] + );

                 if (right[a] +  > left[b] - ) printf("%d\n",tem);

                 else printf("%d\n", max(tem, rmq(right[a] + , left[b] - )));

             }

         }

     }

     return ;

 }

巴特西

POJ 3368 Frequent values 线段树与RMQ解法

最新文章

热门文章