poj 3368 Frequent values 线段树节点值得变化

本文主要是介绍poj 3368 Frequent values 线段树节点值得变化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=3368

题意：

   #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=100000;
int min(int a,int b) {return a>b?b:a;};
int max(int a,int b) {return a>b?a:b;};
int lef[big+5],righ[big+5];
int a[big+5],p[big+5],q[big+5],data[4*big+5],v[big+5];
struct Node{
   int lp;int rp;
}kind[big+5];
void build(int n,int l,int r)
{
    if(r-l==1)
    {
        data[n]=kind[l].rp-kind[l].lp+1;
        return;
    }
    build(2*n+1,l,(l+r)>>1);
    build(2*n+2,(l+r)>>1,r);
    data[n]=max(data[2*n+1],data[2*n+2]);
}
int query(int a,int b,int k,int l,int r)
{
    if(r<=a||l>=b)
        return -inf;
    else if(a<=l&&r<=b)
        return data[k];
    else if(r>a&&l<b)
    {
        int templ=query(a,b,2*k+1,l,(l+r)>>1);
        int tempr=query(a,b,2*k+2,(l+r)>>1,r);
        return templ>tempr?templ:tempr;
    }
}
int n,c,cnt;
void init()
{
    scanf("%d",&c);
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(i==1||a[i]!=a[i-1])
                {
                    lef[i]=i;
                    ++cnt;
                    kind[cnt].lp=i;
                    kind[cnt-1].rp=i-1;
                }
            else
                lef[i]=lef[i-1];
            v[i]=cnt;
        }
        build(0,1,cnt+1);
        for(int i=n;i>=1;i--)
            if(i==n||a[i]!=a[i+1])
                righ[i]=i;
            else
                righ[i]=righ[i+1];
        for(int i=1;i<=c;i++)
                scanf("%d %d",&p[i],&q[i]);
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        for(int i=1;i<=c;i++)
        {
            int x=p[i],y=q[i];
            if(a[x]==a[y])
                printf("%d\n",y-x+1);
            else if(righ[x]+1==lef[y])
                printf("%d\n",max(righ[x]-x+1,y-lef[y]+1));
            else
            {
                int temp=max(righ[x]-x+1,y-lef[y]+1);
                printf("%d\n",max(temp,query(v[x]+1,v[y],0,1,cnt+1)));
            }
        }
    }
    return 0;
}