UVA 11235 Frequent values (RMQ )

询问静态区间最值的Sparse—Table(Tarjan提出)的算法。这个算法的思想是一个dp，dp[i][j]表示i开头长度为2^j的区间内的最值，然后倍增转移。

这道题询问的是出现次数，相同的数字是连续出现的，先把连续出现的数字按段编号，记录出现的次数。

因为题目询问给的是原来的数字的下标，记录一下这个位置对应的编号。对于完整包含在询问区间里的段，可直接套用RMQ，

为了处理不完整的区间，还需要记录段在原来数组中的左右端点。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;

int id[maxn];
int cnt[maxn],l[maxn],r[maxn];
int d[maxn][20];

void RMQ_init(int *A,int n)
{
    for(int i = 0; i < n; i++) d[i][0] = A[i];
    for(int j = 1; (1<<j)<=n; j++){
        int t = (1<<j)-1;
        for(int i = 0; i + t<= n; i++){
            d[i][j] = max(d[i][j-1],d[i+(t>>1)][j-1]);
        }
    }
}

int RMQ(int L,int R)
{
    int k = 0;
    while((1<<(k+1))<=R-L+1) k++;
    return max(d[L][k],d[R-(1<<k)+1][k]);
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n,q;
    while(scanf("%d%d",&n,&q),n){
        int pre; scanf("%d",&pre);
        int id_cnt = 0;
        cnt[0] = 1; l[0] = 0; id[0] = 0;
        for(int i = 1; i < n; i++){
            int cur; scanf("%d",&cur);
            if(cur == pre){
                cnt[id_cnt]++;
            }else {
                r[id_cnt++] = i-1;
                l[id_cnt] = i;
                cnt[id_cnt] = 1;
            }
            id[i] = id_cnt;
            pre = cur;
        }
        r[id_cnt++] = n-1;
        RMQ_init(cnt,id_cnt);
        while(q--){
            int i,j; scanf("%d%d",&i,&j);
            int ans;
            if(id[--j] != id[--i]){
                ans = max(r[id[i]]-i,j-l[id[j]])+1;
                if(id[j]-id[i]>1){
                    ans = max(ans,RMQ(id[i]+1,id[j]-1));
                }
            }else {
                ans = j-i+1;
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

UVA 11235 Frequent values (RMQ )

相关推荐