学步园

题目

和hdu 3308差不多

多了pushudown来更新区间内的值

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct Tree{
    int l,r;
    int lazy;
    int lsum,rsum,msum;//分别为左儿子最长子序列，右儿子最长子序列，最优子序列
    int lnum,rnum;//最左值，最右值
}tree[maxn<<2];

int num[maxn];

void PushUp(int rt)
{
    int l,r,m;
    l=tree[rt].l;
    r=tree[rt].r;
    m=(l+r)>>1;
    tree[rt].lnum=tree[rt<<1].lnum;
    tree[rt].rnum=tree[rt<<1|1].rnum;
    tree[rt].lsum=tree[rt<<1].lsum;
    tree[rt].rsum=tree[rt<<1|1].rsum;
    tree[rt].msum=max(tree[rt<<1].msum,tree[rt<<1|1].msum);
    if(tree[rt<<1].rnum<tree[rt<<1|1].lnum){
        if(tree[rt<<1].lsum==m-l+1)
            tree[rt].lsum+=tree[rt<<1|1].lsum;
        if(tree[rt<<1|1].rsum==r-m)
            tree[rt].rsum+=tree[rt<<1].rsum;
        tree[rt].msum=max(tree[rt].msum,tree[rt<<1].rsum+tree[rt<<1|1].lsum);
    }
}

void PushDown(int rt)
{
    if(tree[rt].lazy){
        tree[rt<<1].lazy+=tree[rt].lazy;
        tree[rt<<1].lnum+=tree[rt].lazy;
        tree[rt<<1].rnum+=tree[rt].lazy;
        tree[rt<<1|1].lazy+=tree[rt].lazy;
        tree[rt<<1|1].lnum+=tree[rt].lazy;
        tree[rt<<1|1].rnum+=tree[rt].lazy;
        tree[rt].lazy=0;
    }
}

void build(int l,int r ,int rt)
{
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].lazy=0;
    if(l==r){
        tree[rt].rnum=tree[rt].lnum=num[l];
        tree[rt].msum=tree[rt].lsum=tree[rt].rsum=1;
        return ;
    }

    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}

void update(int x,int y,int val,int rt){
    int l,r;
    l=tree[rt].l;
    r=tree[rt].r;
    if(x==l&&r==y){
        tree[rt].lazy+=val;
        tree[rt].lnum+=val;
        tree[rt].rnum+=val;
        return ;
    }
    PushDown(rt);
    int m=(l+r)>>1;
    if(x<=m) update(x,min(m,y),val,rt<<1);
    if(y>m) update(max(m+1,x),y,val,rt<<1|1);
    PushUp(rt);
}

int query(int x,int y,int rt)
{
    int l,r;
    l=tree[rt].l;
    r=tree[rt].r;
    if(l==x&&r==y){
        return tree[rt].msum;
    }
  //  PushDown(rt);
    int m=(l+r)>>1;
    int ans=0;
    if(x<=m) ans=max(ans,query(x,min(m,y),rt<<1));
    if(y>m) ans=max(ans,query(max(m+1,x),y,rt<<1|1));
    if(tree[rt<<1].rnum<tree[rt<<1|1].lnum){
        ans=max(ans,min(tree[rt<<1].rsum,m-x+1)+min(tree[rt<<1|1].lsum,y-m));
    }
    return ans;
}

int main()
{
//    freopen("1.txt","r",stdin);
    int T,n,m,ncase=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&num[i]);
        build(1,n,1);
        printf("Case #%d:\n",ncase++);
        while(m--){
            int a,b,c;
            char s[10];
            scanf("%s",s);
            if(s[0]=='q'){
                scanf("%d%d",&a,&b);
                printf("%d\n",query(a,b,1));
            }
            else{
                scanf("%d%d%d",&a,&b,&c);
                update(a,b,c,1);
            }
        }
    }
    return 0;
}