線段樹專輯——pku 3667 Hotel

http://poj.org/problem?id=3667

哈哈，經典中的經典題啊。利用線段樹求最大連續空閑區間，并返回空閑區間的起點坐標。

View Code

  1 #include<iostream>
  2 #include<string>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 struct node
  7 {
  8     int l;
  9     int r;
 10     int l_val; //從左節點數起的最大連續空閑區間
 11     int r_val; //從右節點起的最大連續空閑區間
 12     int max_val; //整個區間的最大連續空閑區間
 13     int cover;  //當前區間的占用情況，1表示占用，0表示不占用，-1表示既有占用又有不占用
 14 }; 
 15 
 16 node tree[250000];
 17 int n,m;
 18 
 19 int max(int a,int b)
 20 {
 21     return a>b?a:b;
 22 }
 23 
 24 void build(int i,int l,int r)
 25 {
 26     tree[i].l=l;
 27     tree[i].r=r;
 28     tree[i].cover=0;
 29     tree[i].l_val=tree[i].r_val=tree[i].max_val=r-l+1; //開始所有區間都未使用
 30     if(l==r)
 31         return;
 32     int mid=(l+r)/2;
 33     build(2*i,l,mid);
 34     build(2*i+1,mid+1,r);
 35 }
 36 
 37 void fun(int i) //跟新區間
 38 {
 39     if(tree[i].cover==0)
 40     {
 41         tree[i].l_val=tree[i].r_val=tree[i].max_val=tree[i].r-tree[i].l+1;    
 42     }
 43     else if(tree[i].cover==1)
 44     {
 45         tree[i].l_val=tree[i].r_val=tree[i].max_val=0;
 46     }
 47 }
 48 
 49 void updata(int i,int l,int r,int w)
 50 {
 51     if(tree[i].l>r || tree[i].r<l)
 52         return;
 53     if(tree[i].l>=l && tree[i].r<=r)
 54     {
 55         tree[i].cover=w; //跟新該段情況
 56         fun(i);  //并根據cover跟新其他域
 57         return;
 58     }
 59     if(tree[i].cover!=-1)
 60     {
 61         tree[2*i].cover=tree[2*i+1].cover=tree[i].cover;
 62         fun(2*i);  fun(2*i+1);
 63         tree[i].cover=-1;
 64     }
 65     updata(2*i,l,r,w);
 66     updata(2*i+1,l,r,w);
 67     if(tree[2*i].cover==tree[2*i+1].cover) //由下而上跟新所有信息
 68         tree[i].cover=tree[2*i].cover;
 69     else
 70         tree[i].cover=-1;
 71     tree[i].l_val=tree[2*i].l_val+(tree[2*i].cover==0 ? tree[2*i+1].l_val:0);
 72     tree[i].r_val=tree[2*i+1].r_val+(tree[2*i+1].cover==0 ? tree[2*i].r_val:0);
 73     tree[i].max_val=max(max(tree[2*i].max_val,tree[2*i+1].max_val),(tree[2*i].r_val+tree[2*i+1].l_val));
 74 }
 75 
 76 int find(int i,int w)
 77 {
 78     if(tree[i].cover==0 && tree[i].l_val>=w) //從左邊起能找到
 79     {
 80         return tree[i].l;
 81     }
 82     if(tree[i].cover==1)
 83     {
 84         return 0;
 85     }
 86     if(tree[i].cover==-1 && tree[i].max_val>=w)
 87     {
 88         if(tree[2*i].max_val>=w) //左邊還有足夠空間，向左遞歸
 89             return find(2*i,w);
 90         else if(tree[2*i].r_val+tree[2*i+1].l_val>=w) //如果中間有足夠空間，直接計算
 91         {
 92             return tree[2*i].r-tree[2*i].r_val+1;
 93         }
 94         else
 95             return find(2*i+1,w); //向右遞歸
 96     }
 97     return 0;
 98 }
 99 
100 int main()
101 {
102     freopen("D:\\in.txt","r",stdin);
103     int i,a,b,c;
104     while(scanf("%d%d",&n,&m)!=EOF)
105     {
106         build(1,1,n);
107         for(i=0;i<m;i++)
108         {
109             scanf("%d",&c);
110             if(c==1)
111             {
112                 scanf("%d",&a);
113                 b=find(1,a);
114                 printf("%d\n",b);
115                 if(b)
116                 {
117                     updata(1,b,b+a-1,1);
118                 }
119             }
120             else
121             {
122                 scanf("%d%d",&a,&b);
123                 updata(1,a,a+b-1,0);
124             }
125         }
126     }
127     return 0;
128 }

轉載于:https://www.cnblogs.com/ka200812/archive/2011/11/10/2244966.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/275177.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/275177.shtml
英文地址，請注明出處：http://en.pswp.cn/news/275177.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！