M - 约会安排 HDU - 4553 线段树 （最长连续段）
中文题面
思路：维和两个区间 一个是女神区间 一个是基友区间 如果是基友要预约时间 直接在基友区间查询可满足的起点 （这里先判tree[1].m >=length也就是有没有这样的区间满足时间length） 预约成功后更新基友区间
如果是女神要预约区间 先在基友区间预约看有没有满足的区间 （同样看根节点的m） 如果有 同时更新两个区间 如果没有继续在女神区间查找 如果女神区间有 则同时更新基友和女神区间 如果没有 那就真没有了直接输出 题目要求的话
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+5; 4 struct Node{ 5 int l,r; 6 int ml,mr,m; 7 }tree1[maxn*4],tree2[maxn*4]; 8 void build(int x,int l,int r){ 9 tree1[x].l=tree2[x].l=l; 10 tree1[x].r=tree2[x].r=r; 11 tree1[x].ml=tree2[x].ml=tree1[x].mr=tree2[x].mr=tree1[x].m=tree2[x].m=r-l+1; 12 if(l==r)return ; 13 int mid=l+r>>1; 14 build(x<<1,l,mid); 15 build(x<<1|1,mid+1,r); 16 } 17 void push_up(int x){ 18 int mid=tree1[x].r+tree1[x].l>>1; 19 tree1[x].ml=tree1[x<<1].ml; 20 tree1[x].mr=tree1[x<<1|1].mr; 21 tree1[x].m=max(max(tree1[x<<1].m,tree1[x<<1|1].m),tree1[x<<1].mr+tree1[x<<1|1].ml); 22 if(tree1[x<<1].ml==mid-tree1[x].l+1)tree1[x].ml+=tree1[x<<1|1].ml; 23 if(tree1[x<<1|1].mr==tree1[x].r-mid)tree1[x].mr+=tree1[x<<1].mr; 24 25 tree2[x].ml=tree2[x<<1].ml; 26 tree2[x].mr=tree2[x<<1|1].mr; 27 tree2[x].m=max(max(tree2[x<<1].m,tree2[x<<1|1].m),tree2[x<<1].mr+tree2[x<<1|1].ml); 28 if(tree2[x<<1].ml==mid-tree2[x].l+1)tree2[x].ml+=tree2[x<<1|1].ml; 29 if(tree2[x<<1|1].mr==tree2[x].r-mid)tree2[x].mr+=tree2[x<<1].mr; 30 31 } 32 void push_down(int x){ 33 int mid=tree1[x].l+tree1[x].r>>1; 34 if(tree1[x].m==tree1[x].r-tree1[x].l+1){ 35 tree1[x<<1].ml=tree1[x<<1].mr=tree1[x<<1].m=mid-tree1[x].l+1; 36 tree1[x<<1|1].ml=tree1[x<<1|1].mr=tree1[x<<1|1].m=tree1[x].r-mid; 37 } 38 else if(tree1[x].m==0){ 39 tree1[x<<1].ml=tree1[x<<1].mr=tree1[x<<1].m=0; 40 tree1[x<<1|1].ml=tree1[x<<1|1].mr=tree1[x<<1|1].m=0; 41 } 42 43 if(tree2[x].m==tree2[x].r-tree2[x].l+1){ 44 tree2[x<<1].ml=tree2[x<<1].mr=tree2[x<<1].m=mid-tree2[x].l+1; 45 tree2[x<<1|1].mr=tree2[x<<1|1].ml=tree2[x<<1|1].m=tree2[x].r-mid; 46 } 47 else if(tree2[x].m==0){ 48 tree2[x<<1].ml=tree2[x<<1].mr=tree2[x<<1].m=0; 49 tree2[x<<1|1].mr=tree2[x<<1|1].ml=tree2[x<<1|1].m=0; 50 } 51 } 52 void update(int x,int l,int r,int value){ 53 if(tree1[x].l>=l&&tree1[x].r<=r){ 54 if(value==1){ 55 tree1[x].ml=tree1[x].mr=tree1[x].m=0; 56 } 57 else if(value==2){ 58 tree1[x].ml=tree1[x].mr=tree1[x].m=0; 59 tree2[x].ml=tree2[x].mr=tree2[x].m=0; 60 } 61 else { 62 tree1[x].ml=tree1[x].mr=tree1[x].m=tree1[x].r-tree1[x].l+1; 63 tree2[x].ml=tree2[x].mr=tree2[x].m=tree1[x].r-tree1[x].l+1; 64 } 65 return ; 66 } 67 int mid=tree1[x].l+tree1[x].r>>1; 68 push_down(x); 69 if(mid>=l)update(x<<1,l,r,value); 70 if(mid<r)update(x<<1|1,l,r,value); 71 push_up(x); 72 } 73 int query(int x,int length,int value){ 74 if(tree1[x].l==tree1[x].r)return tree1[x].l; 75 push_down(x); 76 int mid=tree1[x].l+tree1[x].r>>1; 77 if(value==1){ 78 if(tree1[x<<1].m>=length){ 79 return query(x<<1,length,value); 80 } 81 else if(tree1[x<<1].mr+tree1[x<<1|1].ml>=length){ 82 return mid-tree1[x<<1].mr+1; 83 } 84 else return query(x<<1|1,length,value); 85 } 86 else { 87 if(tree2[x<<1].m>=length){ 88 return query(x<<1,length,value); 89 } 90 else if(tree2[x<<1].mr+tree2[x<<1|1].ml>=length){ 91 return mid-tree2[x<<1].mr+1; 92 } 93 else return query(x<<1|1,length,value); 94 } 95 } 96 int main(){ 97 int t; 98 int kase=1; 99 scanf("%d",&t); 100 char s[100]; 101 int temp; 102 int q; 103 int n; 104 while(t--){ 105 printf("Case %d:\n",kase++); 106 scanf("%d%d",&n,&q); 107 build(1,1,n); 108 while(q--){ 109 scanf("%s%d",s,&temp); 110 if(s[0]=='D'){ 111 if(tree1[1].m>=temp){ 112 int start=query(1,temp,1); 113 update(1,start,start+temp-1,1); 114 printf("%d,let's fly\n",start); 115 } 116 else printf("fly with yourself\n"); 117 } 118 else if(s[0]=='N'){ 119 if(tree1[1].m>=temp){ 120 int start=query(1,temp,1); 121 update(1,start,start+temp-1,2); 122 printf("%d,don't put my gezi\n",start); 123 } 124 else if(tree2[1].m>=temp){ 125 int start=query(1,temp,0); 126 update(1,start,start+temp-1,2); 127 printf("%d,don't put my gezi\n",start); 128 } 129 else printf("wait for me\n"); 130 } 131 else { 132 int zz; 133 scanf("%d",&zz); 134 update(1,temp,zz,3); 135 printf("I am the hope of chinese chengxuyuan!!\n"); 136 } 137 } 138 139 } 140 return 0; 141 }
