线段树洛谷P2894 [USACO08FEB]酒店Hotel

2019-11-08 20:01:07

字体：大中小

来源：转载

供稿：网友

https://www.luogu.org/PRoblem/show?pid=2894#sub 这道题第一天我觉得贼难，感觉很复杂；第二天看便有了思路，但觉得写起来不简单；第三天发现，只不过是线段树里面多维护了几个东西罢了；以后的练习，估计线段树不再仅仅是维护一下数值就好了；

#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>#define Ll long longusing namespace std;struct tree{ int xx,yy,l,r,m,p;//xx，yy是这个区间的范围，l,r代表这段区间的左右最长连续空位，m就是整段区间的连续空位，p是lazy标记 }T[500000*8+1];int n,m,x,y,z,ans;void clean(int num){//这个显然就是lazy的下传 if(T[num].xx==T[num].yy)return; if(!T[num].p)return; int k=num+num; if(T[num].p==1){ T[k].l=T[k].m=T[k].r=T[k+1].l=T[k+1].m=T[k+1].r=0; T[k].p=T[k+1].p=1; }else{ T[k].l=T[k].m=T[k].r=T[k].yy-T[k].xx+1; T[k+1].l=T[k+1].m=T[k+1].r=T[k+1].yy-T[k+1].xx+1; T[k].p=T[k+1].p=2; } T[num].p=0;}void maketree(int x,int y,int num){ T[num].xx=x;T[num].yy=y; T[num].l=T[num].r=T[num].m=y-x+1;//一开始全空房 if(x==y)return; int mid=(x+y)>>1;num=num<<1; maketree(x,mid ,num ); maketree(mid+1,y,num+1);}int find(int x,int num){//找一个长度位x的区间，现搜索到第num个区间 clean(num);clean(num*2);clean(num*2+1); if(T[num].l>=x)return T[num].xx;//如果这个区间的左连续区间足够，那么直接住在最左边吧 if(T[num*2].m>=x)return find(x,num*2);//如果左半段区间的最大值满足x，说明可以住在左子儿子的区间 if(T[num*2].r+T[num*2+1].l>=x)return T[num*2].yy-T[num*2].r+1;//这时判断中间的一块区域 return find(x,num*2+1); //因为一定可以找到区间，但前面都找不到，那只可能在右半段的区间里了 }void gaoji(int num){//ohly~ohlyohlyohly~~ wearethegay~~~wearethegay~~~~~~~~随便取的函数命 int k=num<<1; clean(k);clean(k+1); T[num].l=T[k ].l;//显然大区间的l是左小区间的l，但是如果左小区间全空，显然大区间的l要加上右小区间的l if(T[k ].l==T[k ].yy-T[k ].xx+1)T[num].l+=T[k+1].l; T[num].r=T[k+1].r;//同理 if(T[k+1].r==T[k+1].yy-T[k+1].xx+1)T[num].r+=T[k ].r; T[num].m=max(T[k].m,T[k+1].m);//这个很显然啊 T[num].m=max(T[num].m,T[k].r+T[k+1].l);}void dec(int x,int y,int num){//这些和基本线段树差不多 clean(num); if(x<=T[num].xx&&T[num].yy<=y){T[num].l=T[num].r=T[num].m=0;T[num].p=1;return;} num=num<<1; if(x<=T[num ].yy)dec(x,y,num ); if(y>=T[num+1].xx)dec(x,y,num+1); gaoji(num/2);}void pluss(int x,int y,int num){ clean(num); if(x<=T[num].xx&&T[num].yy<=y){T[num].l=T[num].r=T[num].m=T[num].yy-T[num].xx+1;T[num].p=2;return;} num=num<<1; if(x<=T[num ].yy)pluss(x,y,num ); if(y>=T[num+1].xx)pluss(x,y,num+1); gaoji(num/2);}int main(){ scanf("%d%d",&n,&m); maketree(1,n,1); while(m--){ scanf("%d",&x); if(x==1){ scanf("%d",&x); if(T[1].m<x){printf("0/n");continue;}//T[1].m是整个区间中的最大连续空位，这个判断显然成立 ans=find(x,1);//通过了上面一个判断，一定可以找出答案 printf("%d/n",ans); dec(ans,ans+x-1,1);//把新住进来的房间重置 }else{ scanf("%d%d",&x,&y); pluss(x,x+y-1,1);//把新走出去的房间重置 } }}

上一篇：求二叉树的先序遍历

下一篇：1214 线段覆盖