POJ 3368 RMQ

此题用线段树也能做 用RMQ也能做

当然RMQ的速度比线段树要快很多

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 111111
#define MAXM 11111
#define INF 1000000000
using namespace std;
int mx[MAXN][18], Log[MAXN];
struct PP
{
    int left, right, num;
} p[MAXN];
int v[MAXN], h[MAXN];
int n, m, len;
void rmqinit()
{
    for(int i = 1; i <= n; i++) mx[i][0] = p[i].num;
    int m = Log[n];
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {
            mx[j][i] = mx[j][i - 1];
            if(j + (1 << (i - 1)) <= n) mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);
        }
}
int rmqmax(int l, int r)
{
    int m = Log[r - l + 1];
    return max(mx[l][m] , mx[r - (1 << m) + 1][m]);
}
void get()
{
    len = 1;
    p[1].left = 1;
    p[1].num = 1;
    h[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(v[i] == v[i - 1])
            p[len].num++;
        else
        {
            p[len++].right = i - 1;
            p[len].left = i;
            p[len].num = 1;
        }
        h[i] = len;
    }
    p[len].right = n;
}
int in()
{
    int flag = 1;
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' || ch == '\n');
    if(ch == '-') flag = -1;
    else
        a += ch - '0';
    while((ch = getchar()) != ' ' && ch != '\n')
    {
        a *= 10;
        a += ch - '0';
    }
    return flag * a;
}
void out(int a)
{
    if(a < 0)
    {
        putchar('-');
        a = -a;
    }
    if(a >= 10)out(a / 10);
    putchar(a % 10 + '0');
}
int main()
{
    Log[1] = 0;
    for(int i = 2; i < MAXN; i++) Log[i] = Log[i >> 1] + 1;
    while(scanf("%d", &n) != EOF && n)
    {
        scanf("%d", &m);
        for(int i = 1; i <= n; i++) v[i] = in();
        get();
        n = len;
        rmqinit();
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            x= in();
            y = in();
            int u = h[x];
            int v = h[y];
            if(u == v) out(y - x + 1);
            else if(u == v - 1) out(max(p[u].right - x + 1, y - p[v].left + 1));
            else
            {
                int ans = max(p[u].right - x + 1, y - p[v].left + 1);
                int t = rmqmax(u + 1, v - 1);
                ans = max(ans, t);
                out(ans);
            }
            putchar('\n');
        }
    }
    return 0;
}