题目链接:https://vjudge.net/problem/POJ-3667
题目大意:n个连续的房间m个操作。操作分两种,
第一种以1 x形式给出,找到最左的能连续容下x个人的连续房间,并输出左端点的编号,如果找不到就输出0.
第二种以2 l x的形式给出,表示以l为起点的x个房间都清空。
思路:
采用线段树去维护最大连续区间。具体的讲解可以看:https://www.cnblogs.com/lonely-wind-/p/11667471.html
1 #include <math.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #include <algorithm> 6 #include <string> 7 #include <string.h> 8 #include <vector> 9 #include <map> 10 #include <stack> 11 #include <set> 12 //#include <random> 13 14 #define ll long long 15 #define ls nod<<1 16 #define rs (nod<<1)+1 17 const int maxn = 1e5 + 10; 18 19 20 struct segment_tree { 21 int l,r; 22 int lsum,rsum,sum; 23 int lazy; 24 }tree[maxn<<2]; 25 26 void pushup(int nod) { 27 int l = tree[nod].l,r = tree[nod].r; 28 int mid = (l + r) >> 1; 29 tree[nod].sum = std::max(std::max(tree[ls].sum,tree[rs].sum),tree[ls].rsum + tree[rs].lsum); 30 tree[nod].lsum = tree[ls].lsum; 31 tree[nod].rsum = tree[rs].rsum; 32 if (tree[ls].lsum == (mid-l+1)) 33 tree[nod].lsum = tree[ls].sum + tree[rs].lsum; 34 if (tree[rs].rsum == (r-mid)) 35 tree[nod].rsum = tree[rs].sum + tree[ls].rsum; 36 } 37 38 void pushdown(int nod) { 39 int l = tree[nod].l,r = tree[nod].r; 40 int mid = (l + r ) >> 1; 41 tree[ls].sum = tree[ls].rsum = tree[ls].lsum = tree[nod].lazy * (mid-l+1); 42 tree[rs].sum = tree[rs].rsum = tree[rs].lsum = tree[nod].lazy * (r-mid); 43 tree[ls].lazy = tree[rs].lazy = tree[nod].lazy; 44 tree[nod].lazy = -1; 45 } 46 47 void build(int l,int r,int nod) { 48 tree[nod].l = l; 49 tree[nod].r = r; 50 tree[nod].lazy = -1; 51 tree[nod].lsum = tree[nod].rsum = tree[nod].sum = (r - l + 1); 52 if (l == r) 53 return ; 54 int mid = (l + r ) >> 1; 55 build(l,mid,ls); 56 build(mid+1,r,rs); 57 } 58 59 void modify(int x,int y,int z,int nod=1) { 60 int l = tree[nod].l,r = tree[nod].r; 61 if (x <= l && y >= r) { 62 tree[nod].lsum = tree[nod].rsum = tree[nod].sum = (r-l+1)*z; 63 tree[nod].lazy = z; 64 return ; 65 } 66 if (tree[nod].lazy != -1) { 67 pushdown(nod); 68 } 69 int mid = (l + r) >> 1; 70 if (x <= mid) { 71 modify(x,y,z,ls); 72 } 73 if (y > mid) { 74 modify(x,y,z,rs); 75 } 76 pushup(nod); 77 } 78 79 int query(int siz,int nod=1) { 80 int l = tree[nod].l,r = tree[nod].r; 81 int mid = (l + r) >> 1; 82 if (l == r && siz == 1) 83 return l; 84 if (tree[nod].lazy != -1) 85 pushdown(nod); 86 if (tree[nod].sum >= siz) { 87 if (tree[ls].sum >= siz) 88 return query(siz,ls); 89 else if (tree[ls].rsum + tree[rs].lsum >= siz) { 90 return mid + 1 - tree[ls].rsum; 91 } 92 else 93 return query(siz,rs); 94 } 95 return 0; 96 } 97 98 int main() { 99 int n,m; 100 scanf("%d%d",&n,&m); 101 build(1,n,1); 102 while (m--) { 103 int opt; 104 scanf("%d",&opt); 105 if (opt == 1) { 106 int x; 107 scanf("%d",&x); 108 int temp = query(x,1); 109 printf("%d\n",temp); 110 if (!temp) { 111 continue; 112 } 113 modify(temp,temp+x-1,0); 114 } 115 else { 116 int x,y; 117 scanf("%d%d",&x,&y); 118 modify(x,x+y-1,1); 119 } 120 } 121 return 0; 122 }