poj 3667 Hotel

昨天学习了线段树的延迟标记；
发现自己还有区间合并没有学；
抓紧时间学习一下；
代码：
  1 #include<cstdio>
  2 #include<algorithm>
  3 #define maxn 200005
  4 using namespace std;
  5 
  6 struct tree
  7 {
  8     int l,r,msum,lsum,rsum,flag;
  9     tree *right,*left;
 10 }tr[maxn];
 11 int nonocount;
 12 
 13 void build(tree *root,int l,int r)
 14 {
 15     root->l=l,root->r=r,root->flag=-1;
 16     root->msum=root->lsum=root->rsum=r-l+1;
 17     if(l==r)return;
 18     int mid=(l+r)>>1;
 19     nonocount++;
 20     root->left=tr+nonocount;
 21     nonocount++;
 22     root->right=tr+nonocount;
 23     build(root->left,l,mid);
 24     build(root->right,mid+1,r);
 25 }
 26 
 27 void pushdown(tree *root,int mid)
 28 {
 29     if(root->flag!=-1)
 30     {
 31         root->left->flag=root->right->flag=root->flag;
 32         int x=root->flag?0:mid-(mid>>1);
 33         root->left->lsum=root->left->msum=root->left->rsum=x;
 34         int y=root->flag?0:(mid>>1);
 35         root->right->lsum=root->right->msum=root->right->rsum=y;
 36         root->flag=-1;
 37     }
 38 }
 39 
 40 void pushup(tree *root,int mid)
 41 {
 42     root->lsum=root->left->lsum;
 43     root->rsum=root->right->rsum;
 44     if(root->lsum==mid-(mid>>1))root->lsum+=root->right->lsum;
 45     if(root->rsum==(mid>>1))root->rsum+=root->left->rsum;
 46     root->msum=max(root->right->lsum+root->left->rsum,max(root->left->msum,root->right->msum));
 47 }
 48 
 49 void update(tree *root,int l,int r,int c)
 50 {
 51     int x=root->r-root->l+1;
 52     if(l<=root->l&&root->r<=r)
 53     {
 54         root->msum=root->lsum=root->rsum=c?0:x;
 55         root->flag=c;
 56         return;
 57     }
 58     pushdown(root,x);
 59     int mid=(root->l+root->r)>>1;
 60     if(l<=mid)update(root->left,l,r,c);
 61     if(r>mid) update(root->right,l,r,c);
 62     pushup(root,x);
 63 }
 64 
 65 int query(tree *root,int w)
 66 {
 67     int x=root->r-root->l+1;
 68     if(root->l==root->r)return root->l;
 69     pushdown(root,x);
 70     int mid=(root->l+root->r)>>1;
 71     if(root->left->msum>=w)return query(root->left,w);
 72     else if(root->left->rsum+root->right->lsum>=w)return mid-root->left->rsum+1;
 73     return query(root->right,w);
 74 }
 75 int n,m,a,b,c;
 76 int main()
 77 {
 78     scanf("%d%d",&n,&m);
 79     build(tr,1,n);
 80     while(m--)
 81     {
 82         scanf("%d",&a);
 83         if(a==1)
 84         {
 85             scanf("%d",&b);
 86             if(tr->msum<b)puts("0");
 87             else
 88             {
 89                 int p=query(tr,b);
 90                 printf("%d
",p);
 91                 update(tr,p,p+b-1,1);
 92             }
 93         }
 94         else
 95         {
 96             scanf("%d%d",&b,&c);
 97             update(tr,b,b+c-1,0);
 98         }
 99     }
100     return 0;
101 }
View Code