poj 3368_Frequent values_线段树

发布于 2019-05-20  784 次阅读


题目大意

给定一个不下降的序列,给定几个区间,求区间中连续的最多的数


思路

开一个线段树,记录
1.max 表示当前区间连续的最大值
2.x 表示该区间表示序列的第几位
3.lt,rt表示区间的左右分别为那个数
4,l,r为区间的左右连续的个数
然后就显而易见可以很容易的建一颗树,详见代码(我都不想复述了)
做的时候有一个地方写错了一点点,一直该不出来
建树的时候可以将右区间设为(m+1,r)来让线段树的每一个节点表示点而不是一个线段


#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;
#define fill(x,y) memset(x,y,sizeof(x))
int a[100010];
struct tree
{
    int max,l,r,x,lt,rt;
}t[1000005];
int k=0,ans=0,xx,yy;
int max(int x,int y)
{
    return x>y?x:y;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int create(int p,int l,int r)
{
    int m=(l+r)/2;
    t[p].max=t[p].l=t[p].r=t[p].x=t[p].lt=t[p].rt=0;
    if (r==l)
    {
        k++;
        t[p].x=k;
        return 0;
    }
    create(p*2,l,m);
    create(p*2+1,m+1,r);
}
int make(int p,int l,int r)
{
    int m=(l+r)/2;
    if (t[p].x!=0)
    {
        t[p].l=t[p].r=t[p].max=1;
        t[p].lt=t[p].rt=a[t[p].x];
        return 0;
    }
    make(p*2,l,m);
    t[p].l=t[p*2].l;
    t[p].lt=t[p*2].lt;
    make(p*2+1,m+1,r);
    t[p].r=t[p*2+1].r;
    t[p].rt=t[p*2+1].rt;
    if (t[p].lt==t[p].rt) 
    {
        t[p].max=r-l+1;
        t[p].l=r-l+1;
        t[p].r=r-l+1;
    }
    t[p].max=max(t[p*2].max,t[p*2+1].max);
    if (t[p*2].rt==t[p*2+1].lt)
    {
        if (t[p*2].lt==t[p*2+1].lt)
        {
            t[p].l=t[p*2].l+t[p*2+1].l;
            t[p].max=max(t[p].max,t[p].l);
        }
        else if (t[p*2].rt==t[p*2+1].rt)
        {
            t[p].r=t[p*2].r+t[p*2+1].l;
            t[p].max=max(t[p].max,t[p].r);
        }
    }
    if (t[p*2].r+t[p*2+1].l>t[p].max&&t[p*2].rt==t[p*2+1].lt) t[p].max=t[p*2].r+t[p*2+1].l;
}
int count(int p,int l,int r,int x,int y)
{
    if (x<=l&&y>=r) return t[p].max;
    int m=(l+r)/2;
    if (y<=m) return count(p*2,l,m,x,y);
    if (x>m) return count(p*2+1,m+1,r,x,y);
    int mx=1,mx1,mx2;
    if (t[p*2].rt==t[p*2+1].lt)
    {

        mx=min(m-x+1,t[p*2].r);
        mx+=min(y-m,t[p*2+1].l);
    }
    mx1=count(p*2,l,m,x,m);
    mx2=count(p*2+1,m+1,r,m+1,y);
    mx=max(mx1,mx);
    mx=max(mx2,mx);
    return mx;
}
int main()
{
    int n,m;
    while (~scanf("%d",&n)&&n)
    {
        scanf("%d",&m);
    k=0;
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    memset(&t,0,sizeof(t)); 
    create(1,1,n);    

    make(1,1,n); 

    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&xx,&yy);
        printf("%d\n",count(1,1,n,xx,yy));
    }
    }
}