[RMQ] [线段树] POJ 3368 Frequent Values

时间：2022-11-13 22:51:15

一句话，多次查询区间的众数的次数

注意多组数据！！！！

RMQ方法：

预处理 i 及其之前相同的数的个数

再倒着预处理出 i 到不是与 a[i] 相等的位置之前的一个位置， 查询时分成相同的一段和不同的一段 （RMQ）

但是要注意 to[i] 大于查询范围的情况， 以及RMQ时 x < y 的情况！！

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<string>

#include<iomanip>

#include<ctime>

#include<climits>

#include<cctype>

#include<algorithm>

#ifdef WIN32

#define AUTO "%I64d"

#else

#define AUTO "%lld"

#endif

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=;

const int maxd=;

int n,q;

int a[maxn];

int sum[maxn];

int to[maxn];

inline bool init()

{

    if(!~scanf("%d%d",&n,&q) || !n) return false;

    for(int i=;i<=n;i++) scanf("%d",a+i);

    sum[]=;

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

        if(a[i-]^a[i]) sum[i]=;

        else sum[i]=sum[i-]+;

    to[n]=n;

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

        to[i] = a[i]^a[i+]? i : to[i+];

    return true;

}

int dp[maxn][maxd];

void ST()

{

    for(int i=;i<=n;i++) dp[i][] = sum[i];

    int k=;

    while( (<<k+) <= n ) k++;

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

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

            dp[i][j] = max( dp[i][j-] , dp[i+(<<j-)][j-] ); // j-1 moved !!!

}

inline int RMQ(int x,int y)

{

    if (x>y) return -INF; // INF here to make the case extinct!!

    int k=;

    while( (<<k+) <= (y-x+) ) k++;

    return max(dp[x][k] , dp[y-(<<k)+][k]);

}

int main()

{

    freopen("fre.in","r",stdin);

    freopen("fre.out","w",stdout);

    while(init())

    {

        ST();

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

        {

            int x,y;

            scanf("%d%d",&x,&y);

            printf("%d\n",max(sum[min(to[x],y)]-sum[x]+ , RMQ(to[x]+,y)));

        }

    }

    return ;

}

线段树方法：

不急，懒得写了。。

相关文章