网站seo优化服务商,中秋网页设计素材网站,网站建设谈单技巧,网站轮播图片psd源码CF_46D 由于数据范围很小#xff0c;实际上可以直接暴力的。但为了练练线段树合并区间的操作所以就用线段树写了。 更多和线段树合并区间有关的题目可以参考胡浩的博客#xff1a;http://www.notonlysuccess.com/index.php/segment-tree-complete/。 #includestdio.h…CF_46D 由于数据范围很小实际上可以直接暴力的。但为了练练线段树合并区间的操作所以就用线段树写了。 更多和线段树合并区间有关的题目可以参考胡浩的博客http://www.notonlysuccess.com/index.php/segment-tree-complete/。 #includestdio.h
#includestring.h
#define MAXD 100210
#define MAXQ 110
int N, L, B, F, lc[4 * MAXD], mc[4 * MAXD], rc[4 * MAXD], to[4 * MAXD];
struct Car
{int x, y;
}car[MAXQ];
void build(int cur, int x, int y)
{int mid (x y) 1, ls cur 1, rs (cur 1) | 1;mc[cur] lc[cur] rc[cur] y - x 1;to[cur] -1;if(x y)return ;build(ls, x, mid);build(rs, mid 1, y);
}
int getmax(int x, int y)
{return x y ? x : y;
}
void update(int cur, int x, int y)
{int mid (x y) 1, ls cur 1, rs (cur 1) | 1;mc[cur] getmax(mc[ls], mc[rs]);mc[cur] getmax(rc[ls] lc[rs], mc[cur]);lc[cur] lc[ls] (lc[ls] mid - x 1 ? lc[rs] : 0);rc[cur] rc[rs] (rc[rs] y - mid ? rc[ls] : 0);
}
void pushdown(int cur, int x, int y)
{int mid (x y) 1, ls cur 1, rs (cur 1) | 1;if(to[cur] ! -1){to[ls] to[rs] to[cur];mc[ls] lc[ls] rc[ls] (to[cur] ? 0 : mid - x 1);mc[rs] lc[rs] rc[rs] (to[cur] ? 0 : y - mid);to[cur] -1;}
}
int query(int cur, int x, int y, int z)
{int mid (x y) 1, ls cur 1, rs (cur 1) | 1;if(x y)return x;pushdown(cur, x, y);if(mc[rs] z)return query(rs, mid 1, y, z);else if(rc[ls] lc[rs] z)return mid lc[rs];elsereturn query(ls, x, mid, z);
}
void refresh(int cur, int x, int y, int s, int t, int c)
{int mid (x y) 1, ls cur 1, rs (cur 1) | 1;if(x s y t){to[cur] c;mc[cur] lc[cur] rc[cur] (c ? 0 : y - x 1);return ;}pushdown(cur, x, y);if(mid s)refresh(ls, x, mid, s, t, c);if(mid 1 t)refresh(rs, mid 1, y, s, t, c);update(cur, x, y);
}
void solve()
{int i, j, k, x, y, n, len;scanf(%d, n);for(i 1; i n; i ){scanf(%d, j);if(j 1){scanf(%d, len);if(mc[1] len B F)printf(-1\n);else{y query(1, 1, N, len B F);printf(%d\n, N - y);car[i].x y - B - len 1, car[i].y y - B;refresh(1, 1, N, car[i].x, car[i].y, 1);}}else{scanf(%d, k);refresh(1, 1, N, car[k].x, car[k].y, 0);}}
}
void init()
{N L B F;build(1, 1, N);
}
int main()
{while(scanf(%d%d%d, L, B, F) 3){init();solve();}return 0;
} 转载于:https://www.cnblogs.com/staginner/archive/2012/04/17/2454096.html
