学步园

　　话说这题从我开始学线段树就开始做，直到今天才A掉，前后有近3个月吧。今天重新翻这个题，思路有点乱，看了一下大牛的代码。然后就自己写，没想到，居然敲了一遍就过了，激动啊～～

3667

Accepted

3200K

625MS

C++

2422B

2011-10-25 17:50:22

思路：

　　结构体定义包含：l, r, cov, ls, sum, rs。其中：ls表示从左边数连续的空余空间大小，rs表示从右边数连续的空余空间大小。sum表示整段上最大的空余空间大小。

查询时。当查询到当段段的sum > len时，满足条件。

更新时，当cov改变，同时要改变当前段的ls、rs、sum。当一段更新完后还要上传cov的信息。

My Code:

#include <iostream>
#include <cstring>
#include <cstdio>
#define L(t) t << 1
#define R(t) t << 1 | 1

using namespace std;

const int N = 50010;

struct node{
int cov;
int l, r;
int ls, rs, sum;
}node[N<<2];

void creat(int t, int l, int r){
    node[t].l = l;
    node[t].r = r;
    node[t].cov = 0;
    node[t].ls = node[t].rs = node[t].sum = r-l+1;
if(l == r)    return ;
int mid = (l + r) >> 1;
    creat(L(t), l, mid);
    creat(R(t), mid+1, r);
}
void updata_sum(int t){
if(node[t].cov == 0){
        node[t].sum = node[t].ls = node[t].rs = node[t].r - node[t].l + 1;
    } else {
        node[t].sum = node[t].ls = node[t].rs = 0;
    }
}

void updata_cov(int t){
if(node[L(t)].cov == 0 && node[R(t)].cov == 0)
        node[t].cov = 0;
else if(node[L(t)].cov == 1 && node[R(t)].cov == 1)
        node[t].cov = 1;
else
        node[t].cov = -1;
}

void updata(int t, int l, int r, int cov){
if(node[t].cov == cov)    return;
if(node[t].l >= l && node[t].r <= r){
        node[t].cov = cov;
        updata_sum(t);
return ;
    }
if(node[t].l == node[t].r)    return;
if(node[t].cov != -1){
        node[L(t)].cov = node[R(t)].cov = node[t].cov;
        updata_sum(L(t)); updata_sum(R(t));
    }
int mid = (node[t].l + node[t].r) >> 1;
if(l > mid)
        updata(R(t), l, r, cov);
else if(r <= mid)
        updata(L(t), l, r, cov);
else{
        updata(L(t), l, mid, cov);
        updata(R(t), mid+1, r, cov);
    }
    updata_cov(t);
    node[t].ls = node[L(t)].ls + (node[L(t)].cov == 0 ? node[R(t)].ls : 0);
    node[t].rs = node[R(t)].rs + (node[R(t)].cov == 0 ? node[L(t)].rs : 0);
    node[t].sum = max(max(node[L(t)].sum, node[R(t)].sum), node[L(t)].rs + node[R(t)].ls);
}

int query(int t, int len){
if(node[t].cov == 0 && node[t].sum >= len)
return node[t].l;
if(node[t].cov == 1)    return 0;
else{
if(node[L(t)].sum >= len)
return query(L(t), len);
else if(node[L(t)].rs + node[R(t)].ls >= len)
return ((node[t].l + node[t].r) >> 1) - node[L(t)].rs + 1;
else if(node[R(t)].sum >= len)
return query(R(t), len);
    }
return 0;
}

int main(){
//freopen("data.in", "r", stdin);

int n, m, x, y, z, p;
while(~scanf("%d%d", &n, &m)){
        creat(1, 1, n);
while(m--){
            scanf("%d", &x);
if(x == 1){
                scanf("%d", &y);
                p = query(1, y);
                printf("%d\n", p);
if(p)
                    updata(1, p, p+y-1, 1);
            }
else{
                scanf("%d%d", &y, &z);
                updata(1, y, z+y-1, 0);
            }
        }
    }
return 0;
}