hdu_2871

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#include<cmath>

#define lson r,m,rt<<1

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

const int maxn=55555;

using namespace std;

int lsum[maxn<<2],rsum[rt<<2],sum[rt<<2];

void pushUp(int rt,int m)

{

    rsum[rt]=rsum[rt<<1|1];

    lsum[rt]=lsum[rt<<1];

    if(lsum[rt]==(m-m>>1))

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

    if(rsum[rt]==m>>1)

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

    sum[rt]=max(max(rsum[rt],lsum[rt]),max(max(sum[rt<<1],sum[rt<<1|1]),rsum[rt]+lsum[rt<<1|1]));

}

build(int l,int r,int rt)

{

    if(l==r)

    {

        lsum[rt]=rsum[rt]=sum[rt]=1;

        return ;

    }

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

    build(lson);

    build(rson);

    pushUp(rt,r-l+1);

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        build(1,n,1);

        for(int i=0;i<m;i++){

            char str[10];

            int d;

            scanf("%s",str);

            if(str[0]=='N')

                update()

        }

    }

    return 0;

}
巴特西

hdu_2871

最新文章

热门文章
