hdu_3308 区间合并

一两个月没写代码的确是手生的厉害，debug的好艰辛，，不过看到accept时的那种满足感真的就是爽
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int maxn=111111;

int rnum[maxn<<2],lnum[maxn<<2];

int len[maxn<<2],rlen[maxn<<2],llen[maxn<<2];

int lmmax,mmax,lln;

void pushUp(int rt,int m)

{

    llen[rt]=llen[rt<<1],rlen[rt]=rlen[rt<<1|1];

    lnum[rt]=lnum[rt<<1],rnum[rt]=rnum[rt<<1|1];

    int tem=0;

        if(rnum[rt<<1]<lnum[rt<<1|1])

            tem=rlen[rt<<1]+llen[rt<<1|1];

    if(llen[rt]==m-(m>>1)&&lnum[rt<<1|1]>rnum[rt<<1])

        llen[rt]+=llen[rt<<1|1];

    if(rlen[rt]==m>>1&&lnum[rt<<1|1]>rnum[rt<<1])

        rlen[rt]+=rlen[rt<<1];

    len[rt]=max(max(llen[rt],max(rlen[rt],tem)),max(len[rt<<1],len[rt<<1|1]));

}

void build(int l,int r,int rt)

{

    if(l==r)

    {

        len[rt]=rlen[rt]=llen[rt]=1;

        int a;

        scanf("%d",&a);

        rnum[rt]=lnum[rt]=a;

        return;

    }

    int m=(l+r)>>1;

    build(lson);

    build(rson);

    pushUp(rt,r-l+1);

}

void update(int L,int d,int l,int r,int rt)

{

    if(l==r)

    {

        lnum[rt]=rnum[rt]=d;

        return ;

    }

    int m=(l+r)>>1;

    if(m>=L) update(L,d,lson);

    else update(L,d,rson);

    pushUp(rt,r-l+1);

}

void query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&R>=r)

    {

        int a=0;

        if(lln<lnum[rt])

        {

            a=lmmax+llen[rt];

        }

        if(llen[rt]==r-l+1&&lln<lnum[rt])

            lmmax=lmmax+llen[rt];

        else

            lmmax=rlen[rt];

        lln=rnum[rt];

        mmax=max(max(mmax,a),len[rt]);

        return;

    }

    int m=(l+r)>>1;

    if(L<=m)

        query(L,R,lson);

    if(R>m)

        query(L,R,rson);

        return;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        build(1,n,1);

        char op[3];

        int a,b;

        while(m--){

            scanf("%s%d%d",op,&a,&b);

            a++;

            if(op[0]=='Q')

                {

                    b++;

                    lmmax=0;mmax=1,lln=99999999;

                    query(a,b,1,n,1);

                    printf("%d\n",mmax);

                }

            else update(a,b,1,n,1);

        }

    }

    return 0;

}
巴特西

hdu_3308 区间合并

最新文章

热门文章
