Uva 11235 RMQ问题

RMQ：

有一个不变的数组，不停的求一个区间的最小值。

使用倍增的思想优化到logN;

d(i,j) 表示从 i 开始的，长度为2^j的一段元素中的最小值。

那么状态转移方程：

d(i,j) = min{ d(i,j-1) , d(i+2^j-1,j-1) }

题目链接：https://vjudge.net/contest/146667#problem/B

题意：一个非降序的数组，询问(i,j)中出现次数最多的数值，所对应的出现次数是多少。

分析：

进行游戏编码，value[i] 和count[i] 表示第 i 段对应的数值和出现的次数，

num[i] 表示位置 i 对应的段所在的编号，left[i] 表示 i 位置所在的段的左端点，right[i] 右端点。

那么(L，R)就是分成3个部分。

一个是right[L] - L + 1，R-left[R] + 1，还一个就是RMQ(count,num[L]+1,num[R]-1)。

特殊情况：如果L和R在同一段里面，R-L+1；

Source Code：

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int maxn =  + ;

 const int maxlog = ;

 // 区间最*大*值

 struct RMQ

 {

     int d[maxn][maxlog];

     void init(const vector<int>& A)

     {

         int n = A.size();

         for(int i = ; i < n; i++) d[i][] = A[i];

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

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

                 d[i][j] = max(d[i][j-], d[i + (<<(j-))][j-]);

     }

     int query(int L, int R)

     {

         int k = ;

         while((<<(k+)) <= R-L+) k++; // 如果2^(k+1)<=R-L+1，那么k还可以加1

         return max(d[L][k], d[R-(<<k)+][k]);

     }

 };

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

 RMQ rmq;

 int main()

 {

     int n,q;

     while(scanf("%d%d",&n,&q)==)

     {

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

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

         a[n] = a[n-] + ;

         int start = -;

         vector<int> count;

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

         {

             if(i==||a[i]>a[i-])

             {

                 if(i>)

                 {

                     count.push_back(i-start);

                     for(int j=start;j<i;j++) {

                         num[j] = count.size()-;

                         left[j] = start;

                         right[j] = i-;

                     }

                 }

                 start = i;

             }

         }

         rmq.init(count);

         while(q--) {

             int L,R,ans;

             scanf("%d%d",&L,&R);

             L--;

             R--;

             if(num[L]==num[R]) ans = R - L + ;

             else {

                 ans = max(R-left[R]+,right[L]-L+);

                 if(num[L]+<num[R])

                     ans = max(ans,rmq.query(num[L]+,num[R]-));

             }

             printf("%d\n",ans);

         }

     }

     return ;

 }

巴特西

Uva 11235 RMQ问题

最新文章

热门文章