网站建设营销攻略,天河建设网站多少钱,如何自己做淘宝网站,百度推广官网网站1593: [Usaco2008 Feb]Hotel 旅馆 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 489 Solved: 272[Submit][Status][Discuss]Description 奶牛们最近的旅游计划#xff0c;是到苏必利尔湖畔#xff0c;享受那里的湖光山色#xff0c;以及明媚的阳光。作为整个旅游的策划… 1593: [Usaco2008 Feb]Hotel 旅馆 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 489 Solved: 272[Submit][Status][Discuss] Description 奶牛们最近的旅游计划是到苏必利尔湖畔享受那里的湖光山色以及明媚的阳光。作为整个旅游的策划者和负责人贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 N 50,000)间客房它们在同一层楼中顺次一字排开在任何一个房间里只需要拉开窗帘就能见到波光粼粼的湖面。 贝茜一行以及其他慕名而来的旅游者都是一批批地来到旅馆的服务台希望能订到D_i (1 D_i N)间连续的房间。服务台的接待工作也很简单如果存在r满足编号为r..rD_i-1的房间均空着他就将这一批顾客安排到这些房间入住如果没有满足条件的r他会道歉说没有足够的空房间请顾客们另找一家宾馆。如果有多个满足条件的r服务员会选择其中最小的一个。 旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i 描述表示编号为X_i..X_iD_i-1 (1 X_i N-D_i1)房间中的客人全部离开。退房前请求退掉的房间中的一些甚至是所有可能本来就无人入住。 而你的工作就是写一个程序帮服务员为旅客安排房间。你的程序一共需要处理M (1 M 50,000)个按输入次序到来的住店或退房的请求。第一个请求到来前旅店中所有房间都是空闲的。 Input * 第1行: 2个用空格隔开的整数N、M * 第2..M1行: 第i1描述了第i个请求如果它是一个订房请求则用2个数字 1、D_i描述数字间用空格隔开如果它是一个退房请求用3 个以空格隔开的数字2、X_i、D_i描述 Output * 第1..??行: 对于每个订房请求输出1个独占1行的数字如果请求能被满足 输出满足条件的最小的r如果请求无法被满足输出0 Sample Input 10 6 1 3 1 3 1 3 1 3 2 5 5 1 6 Sample Output 1 4 7 0 5 HINT Source USACO Gold [Submit][Status][Discuss] 把酒店看成01串0表示没人入住1表示有人入住 每个线段树的节点维护三个值maxlen表示此线段树节点维护的区域中最长的连续长度 llen表示此线段树节点从最左边开始连续的长度 rlen表示此线段树节点从最右边开始连续的长度 例如某线段树节点维护000001110000000111101111000 则maxlen7 llen5 rlen3 1 #includeiostream2 #includecstdio3 #includecstdlib4 #includecstring5 #includealgorithm6 #includecmath7 using namespace std;8 typedef long long LL;9 const int maxn50010;
10 struct node{
11 int l,r;
12 int ls,rs;
13 int maxlen,llen,rlen;
14 int lazy;
15 }seg[maxn*10];
16 int N,M;
17 int tot1;
18 void updata_down(int rt){
19 if(seg[rt].lazy-1) return ;
20 int dseg[rt].lazy;
21 int lsonseg[rt].ls; int rsonseg[rt].rs;
22 seg[lson].maxlenseg[lson].llenseg[lson].rlen(seg[lson].r-seg[lson].l1)*d;
23 seg[rson].maxlenseg[rson].llenseg[rson].rlen(seg[rson].r-seg[rson].l1)*d;
24 seg[lson].lazyseg[rson].lazyseg[rt].lazy;
25 seg[rt].lazy-1;
26 }
27 void updata_up(int rt){
28 int lsonseg[rt].ls; int rsonseg[rt].rs;
29 seg[rt].maxlenmax(seg[lson].maxlen,max(seg[rson].maxlen,seg[lson].rlenseg[rson].llen));
30 if(seg[lson].llenseg[lson].r-seg[lson].l1) seg[rt].llenseg[lson].llenseg[rson].llen;
31 else seg[rt].llenseg[lson].llen;
32 if(seg[rson].rlenseg[rson].r-seg[rson].l1) seg[rt].rlenseg[rson].rlenseg[lson].rlen;
33 else seg[rt].rlenseg[rson].rlen;
34 }
35 void Build(int rt,int l,int r){
36 seg[rt].ll; seg[rt].rr;
37 seg[rt].maxlenseg[rt].llenseg[rt].rlen(r-l1);
38 seg[rt].lazy-1;
39 if(lr) return ;
40 int mid(lr)1;
41 tot; seg[rt].lstot; Build(seg[rt].ls,l,mid);
42 tot; seg[rt].rstot; Build(seg[rt].rs,mid1,r);
43 }
44 int query(int rt,int Len){
45 updata_down(rt);
46 int lsonseg[rt].ls; int rsonseg[rt].rs;
47 if(seg[rt].maxlenLen) return 0;
48 if(seg[rt].r-seg[rt].l1Len) return seg[rt].l;
49 if(seg[lson].maxlenLen) return query(lson,Len);
50 if(seg[lson].rlenseg[rson].llenLen) return seg[lson].r-seg[lson].rlen1;
51 return query(rson,Len);
52 }
53 void change(int rt,int l,int r,int k){
54 updata_down(rt);
55 if(lseg[rt].lseg[rt].rr){
56 seg[rt].maxlenseg[rt].llenseg[rt].rlen(seg[rt].r-seg[rt].l1)*k;
57 seg[rt].lazyk;
58 return ;
59 }
60 int lsonseg[rt].ls; int rsonseg[rt].rs;
61 int mid(seg[rt].lseg[rt].r)1;
62 if(lmid) change(lson,l,r,k);
63 if(mid1r) change(rson,l,r,k);
64 updata_up(rt);
65 }
66 int main(){
67 scanf(%d%d,N,M);
68 Build(1,1,N);
69 int k,x,y;
70 while(M--){
71 scanf(%d,k);
72 if(k1){
73 scanf(%d,x);
74 if(xseg[1].maxlen) printf(0\n);
75 else{
76 yquery(1,x);
77 printf(%d\n,y);
78 change(1,y,yx-1,0);
79 }
80 }
81 else{
82 scanf(%d%d,x,y);
83 change(1,x,xy-1,1);
84 }
85 }
86 return 0;
87 } 转载于:https://www.cnblogs.com/CXCXCXC/p/5001571.html
