POJ3368题解
阅读原文时间:2023年07月09日阅读:1

题目大意:一个非降序序列,有若干查询,每次查询一个区间中重复次数最多的数字的个数。

思路:因为是非降序的,所以可以从头遍历把每个相同的数字划为一个块,用p[i]表示ai划分到了哪个块里面,同时还可以记录每个块的左右边界。同时还可以获得每块中数字的个数。可以把这些个数处理成ST表。

对于每个给定的查询区间,如果区间完全包含于某一个块内,那么说明区间内所有数字相同,答案就是区间的长度。否则,该查询区间可以分为3个部分:1)左侧[l,r[p[l]]的一个块的部分,2)左右侧[l[p[r],r]的另一个块的部分,以及3)中间的若干完整的块。其中1),2)中重复数字的数量分别就是他们的区间长度,而3)的部分可以通过ST表用RMQ求得,答案就是这三者取最大值。

代码:

//POJ.3368
//Author: Prgl
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

//ST表,各段数字出现次数,第i个数字位于第几段,段的左右界(左闭右开)
int b[100010][30], freq[100010], p[100010], l[100010], r[100010];

void RMQ_init(int n)
{
    for (int i = 0; i < n; i++)
        b[i][0] = freq[i];
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 0; i + (1 << j) - 1 < n; i++)
            b[i][j] = max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
    }
}

int RMQ(int l, int r)
{
    int k = 0;
    if (l >= r)
        return 0;
    while (1 << (k + 1) < r - l)
        k++;

    return max(b[l][k], b[r - (1 << k)][k]);
}

int N, Q;

void solve()
{
    memset(freq, 0, sizeof(freq));
    int num, last;
    int index = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        if (i == 0)
        {
            last = num;
            freq[index]++;
            l[0] = 0;
        }
        else
        {
            if (num == last)
            {
                freq[index]++;
            }
            else
            {
                last = num;
                r[index++] = i;
                freq[index]++;
                l[index] = i;
            }
        }
        p[i] = index;
    }
    r[index] = N;
    RMQ_init(index + 1);
    int ql, qr, ans, lo, hi;
    for (int i = 0; i < Q; i++)
    {
        scanf("%d%d", &lo, &hi);
        ql = lo - 1;
        qr = hi - 1;
        if (p[ql] == p[qr])
            ans = qr - ql + 1;
        else
        {
            int a = r[p[ql]] - ql;
            int b = qr - l[p[qr]] + 1;
            int c = RMQ(p[ql] + 1, p[qr]);
            ans = max(a, max(b, c));
        }
        printf("%d\n", ans);
    }
}

int main()
{
    scanf("%d", &N);
    while (N != 0)
    {
        scanf("%d", &Q);
        solve();
        scanf("%d", &N);
    }

    return 0;
}