hdu4553约会安排线段树

//DS QT 找一段最靠前的长度为QT的空间//NS QT 找一段最靠前的长度为QT的空间，如果没找到可以将DS占据的空间当做空闲空间，找一段最靠前的空间//STUDY!! L R 清空L ,R的空间//用两个线段树，一个处理DS的情况，一个处理NS的情况//线段树维护，ma_l , ma_r , ma 区间[l,r]的左边的空闲区间，，右边的以及最大的空闲区间#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std ;const int maxn = 1e5 + 10;#define left v<<1#define right v<<1|1struct node{ int l , r ; int ma_l ; int ma_r ; int ma ; int lazy ;}tree[2][maxn<<2] ;void build(int l , int r , int v){ for(int i = 0;i < 2;i++) { tree[i][v].l = l ; tree[i][v].r = r; tree[i][v].lazy = -1; tree[i][v].ma_l = tree[i][v].ma = tree[i][v].ma_r = (r – l + 1) ; } if(l == r)return ; int mid = (l + r)>>1 ; build(l , mid , left) ; build(mid+1 , r , right) ;}void push_down(int v){ for(int i = 0 ;i < 2;i++) if(tree[i][v].lazy != -1) { tree[i][left].ma_l = tree[i][left].ma_r = tree[i][left].ma = (tree[i][left].r – tree[i][left].l + 1)*tree[i][v].lazy ; tree[i][right].ma_l = tree[i][right].ma_r = tree[i][right].ma = (tree[i][right].r – tree[i][right].l + 1)*tree[i][v].lazy ; tree[i][left].lazy = tree[i][right].lazy = tree[i][v].lazy ; tree[i][v].lazy = -1; }}void push_up(int v){ for(int i = 0 ;i < 2;i++) { tree[i][v].ma_l = tree[i][left].ma_l ; tree[i][v].ma_r = tree[i][right].ma_r ; tree[i][v].ma = max(max(tree[i][left].ma ,tree[i][right].ma) ,tree[i][left].ma_r+tree[i][right].ma_l) ; if(tree[i][v].ma_l == (tree[i][left].r – tree[i][left].l + 1)) tree[i][v].ma_l += tree[i][right].ma_l ; if(tree[i][v].ma_r == (tree[i][right].r – tree[i][right].l + 1)) tree[i][v].ma_r += tree[i][left].ma_r ; }}int query(int v , const int flag , const int num){ if(tree[flag][v].l == tree[flag][v].r) return tree[flag][v].l ; push_down(v) ; if(tree[flag][left].ma >= num) return query(left , flag ,num) ; else if(tree[flag][left].ma_r + tree[flag][right].ma_l >= num) return tree[flag][left].r – tree[flag][left].ma_r + 1 ; else return query(right , flag , num) ;}void update(int a , int b , int v , const int flag , const int tag){ if(tree[flag][v].l >= a && tree[flag][v].r <= b) { tree[flag][v].lazy = tag; tree[flag][v].ma_l = tree[flag][v].ma = tree[flag][v].ma_r = (tree[flag][v].r – tree[flag][v].l + 1)*tag ; return ; } push_down(v) ; int mid = (tree[flag][v].l + tree[flag][v].r) >> 1 ; if(a <= mid)update(a , b , left , flag , tag) ; if(b > mid)update(a , b , right , flag , tag) ; push_up(v) ;}int main(){ // freopen("in.txt" ,"r" , stdin) ; int T ; scanf("%d" , &T) ; int cas = 0 ; while(T–) { int N , Q ; scanf("%d%d" ,&N , &Q) ; build(1 , N , 1) ; char ch[10] ; int L , R , qt ; printf("Case %d:\n" , ++cas) ; while(Q–) { scanf("%s" , ch) ; if(ch[0] == ‘D’) { scanf("%d" , &qt) ; if(tree[1][1].ma < qt) { puts("fly with yourself"); continue ; } int pos = query(1 , 1 , qt) ; update(pos , pos + qt – 1 , 1 , 1 , 0) ; printf("%d,let’s fly\n" , pos) ; } else if(ch[0] == ‘N’) { scanf("%d" , &qt) ; int pos ; if(tree[1][1].ma < qt && tree[0][1].ma < qt) {puts("wait for me"); continue ;} else if(tree[1][1].ma >= qt) pos = query(1 , 1 , qt) ; else pos = query(1 , 0 , qt) ; printf("%d,don’t put my gezi\n" , pos) ; update(pos , pos + qt – 1 , 1 , 0 ,0) ; update(pos , pos + qt – 1 , 1 , 1 , 0) ; } else if(ch[0] == ‘S’) { scanf("%d%d" , &L , &R) ; update(L , R , 1 , 0 , 1) ; update(L , R , 1 , 1 , 1) ; puts("I am the hope of chinese chengxuyuan!!") ; } } } return 0 ;}

心中有愿望一定要去闯，努力实现最初的梦想，

相关文章：

你感兴趣的文章：

标签云：