POJ 3667 区间染色 询问连续空段

n个点 q个操作

1 u 找出连续u个值为0的点 并染色( 若没有输出0 有则输出其位置( 有多个满足条件的点就输出最左端位置 ))

2 u v 把 [u, u+v-1] 这个区间清空, 注意u+v-1 范围可能超过n

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#define N 51000#define L(x) (x<<1)#define R(x) (x<<1|1)using namespace std;inline int Max(int a,int b){return a>b?a:b;}inline int Min(int a,int b){return a<b?a:b;}struct node{int l,r;int mid(){ return (l+r)>>1; }int len(){ return r-l+1; }int  num ; //num 为0表示区间全空 1表示全满 2表示有空有满int Llen, Rlen, Maxlen;// Llen表示区间向右连续为空个数 Maxlen表示区间内最大空数}tree[4*N];void Lazy(int id){if(tree[id].l == tree[id].r) return ;if(tree[id].num == 2)return ;tree[L(id)].num = tree[R(id)].num = tree[id].num;if(tree[id].num == 0){tree[L(id)].Maxlen = tree[L(id)].Llen = tree[L(id)].Rlen = tree[L(id)].len();tree[R(id)].Maxlen = tree[R(id)].Llen = tree[R(id)].Rlen = tree[R(id)].len();}else {tree[L(id)].Maxlen = tree[L(id)].Llen = tree[L(id)].Rlen = 0;tree[R(id)].Maxlen = tree[R(id)].Llen = tree[R(id)].Rlen = 0;}}void updata_up(int id){tree[id].Llen = tree[L(id)].Llen;tree[id].Rlen = tree[R(id)].Rlen;tree[id].Maxlen = Max( tree[L(id)].Maxlen, tree[R(id)].Maxlen);if(tree[L(id)].Rlen && tree[R(id)].Llen){if(tree[L(id)].Llen == tree[L(id)].len()){tree[id].Llen += tree[R(id)].Llen;tree[id].Maxlen = Max(tree[id].Maxlen, tree[id].Llen);}if(tree[R(id)].Rlen == tree[R(id)].len()){tree[id].Rlen += tree[L(id)].Rlen;tree[id].Maxlen = Max(tree[id].Maxlen, tree[id].Rlen);}tree[id].Maxlen = Max( tree[id].Maxlen , tree[L(id)].Rlen + tree[R(id)].Llen);}if( tree[id].Maxlen == 0)tree[id].num = 1;else if( tree[id].Maxlen == tree[id].len() )tree[id].num = 0;else tree[id].num = 2;}void build(int l, int r, int id){tree[id].l = l,  tree[id].r = r;if(l==r){ tree[id].Llen = tree[id].Rlen = 1; tree[id].num = 0; return ; }int mid = tree[id].mid();build(l,   mid, L(id));build(mid+1, r, R(id));updata_up(id);}void updata(int l, int r, int id, int oper){Lazy(id);if( l == tree[id].l && tree[id].r == r){if(oper)tree[id].Maxlen = tree[id].Llen = tree[id].Rlen =0;else tree[id].Maxlen =tree[id].Llen = tree[id].Rlen = tree[id].len();tree[id].num  = oper;return ;}int mid = tree[id].mid();if( r <= mid )   updata(l, r, L(id), oper);else if( mid < l ) updata(l, r, R(id), oper);else {updata(  l, mid, L(id), oper);updata(mid+1, r, R(id), oper);}updata_up(id);}int query(int len, int id){Lazy(id);if(tree[id].Llen >= len ) return tree[id].l;if(tree[L(id)].Maxlen >= len) return query(len, L(id));if(tree[L(id)].Rlen + tree[R(id)].Llen >= len)return tree[L(id)].r - tree[L(id)].Rlen +1;return query(len, R(id));}int main(){int n,q,u,v;while(~scanf("%d %d", &n, &q)){build(1, n, 1);while(q--){int oper; scanf("%d",&oper);if(oper == 1){scanf("%d",&u);if(tree[1].Maxlen < u){printf("0\n");continue;}int v = query(u,1);printf("%d\n",v);updata(v, v+u-1, 1, 1);}else {scanf("%d%d",&u,&v);updata(u,Min(u+v-1,n),1,0);}}}return 0;}/*10 61 31 31 31 32 5 51 6*/