『线段树』「USACO月赛」Hotel

题目描述

奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及 明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的 旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房，它们在同一层 楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的 湖面。

贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台， 希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单： 如果存在r满足编号为r…r+D_i-1的房间均空着，他就将这一批顾客安排到这些 房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另 找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。

旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i 描述，表示编号为X_i…X_i+D_i-1 (1 <= X_i <= N-D_i+1)房间中的客人全部 离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。

而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共 需要处理M (1 <= M < 50,000)个按输入次序到来的住店或退房的请求。第一个 请求到来前，旅店中所有房间都是空闲的。

题目大意

有两个询问：

询问1：询问是否存在一段连续的长度为$d$的空位置；若存在，则输出这个起点并将序列填满，且需要保证起点最小；若不存在，输出$0$.询问2：将$[X,X+D-1]$的数去掉。

题解

一个用线段树维护的题，可以线段树练习的还不够自己写不出来。

初始化：维护每一个区间靠左的连续空位，靠右的连续空位，最大的连续空位。初始化的每一个值都是当前序列的长度。

修改操作：维护两个标记，一个表示开房操作，一个表示退房操作。主要在于spread函数和updata函数上。每一个点完全覆盖以后需要对子节点进行一次完全覆盖,即spread函数的作用；uptata函数和最长连续子段和相似；注意需要判断子区间是否完全覆盖，若不完全覆盖只能只用某一个区间的答案，若完全覆盖则可以全部加起来。

代码是这样的：

void updata(int p) { if (a[p*2].max == a[p*2].len) a[p].lmax = a[p*2].len+a[p*2+1].lmax; else a[p].lmax = a[p*2].lmax; if (a[p*2+1].max == a[p*2+1].len) a[p].rmax = a[p*2].rmax+a[p*2+1].len; else a[p].rmax = a[p*2+1].rmax; a[p].max = max(a[p*2].rmax+a[p*2+1].lmax, max(a[p*2].max, a[p*2+1].max)); return; }

**查询操作：**分成3种：

左区间已经包括了答案的→查询左区间。左区间的$rmax$和右区间的$lmax$构成答案的→找到左区间形成$rmax$序列的起始点，即$r-rmax+1.$右区间已经包括答案的→查询右区间。在查询之前记得特判一下是否有解。

代码如下：

#include <bits/stdc++.h> using namespace std; int n,m; struct SegmentTree { int l,r,len,max,lmax,rmax,tag; } a[1000000]; int cnt = 0; int Ans[200000]; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } void build(int p,int l,int r) { a[p].l = l; a[p].r = r; a[p].len = r-l+1; a[p].lmax = a[p].rmax = a[p].max = a[p].len; if (l == r) return; int mid = l+r >> 1; build(p*2,l,mid); build(p*2+1,mid+1,r); return; } void spread(int p) { if (a[p].tag == 0) return; if (a[p].tag == 1) { a[p*2].tag = a[p*2+1].tag = 1; a[p*2].lmax = a[p*2].rmax = a[p*2].max = 0; a[p*2+1].lmax = a[p*2+1].rmax = a[p*2+1].max = 0; } if (a[p].tag == 2) { a[p*2].tag = a[p*2+1].tag = 2; a[p*2].lmax = a[p*2].rmax = a[p*2].max = a[p*2].len; a[p*2+1].lmax = a[p*2+1].rmax = a[p*2+1].max = a[p*2+1].len; } a[p].tag = 0; return; } void updata(int p) { if (a[p*2].max == a[p*2].len) a[p].lmax = a[p*2].len+a[p*2+1].lmax; else a[p].lmax = a[p*2].lmax; if (a[p*2+1].max == a[p*2+1].len) a[p].rmax = a[p*2].rmax+a[p*2+1].len; else a[p].rmax = a[p*2+1].rmax; a[p].max = max(a[p*2].rmax+a[p*2+1].lmax, max(a[p*2].max, a[p*2+1].max)); return; } void change(int p,int l,int r,int tag) { if (l <= a[p].l && r >= a[p].r) { if (tag == 2) a[p].lmax = a[p].rmax = a[p].max = a[p].len;//退房 if (tag == 1) a[p].lmax = a[p].rmax = a[p].max = 0;//开房 a[p].tag = tag; return; } spread(p); int mid = a[p].l+a[p].r >> 1; if (l <= mid) change(p*2,l,r,tag); if (r > mid) change(p*2+1,l,r,tag); updata(p); return; } int ask(int p,int d) { spread(p); if (a[p].l == a[p].r) return a[p].l; if (a[p*2].max >= d) return ask(p*2,d); if (a[p*2].rmax + a[p*2+1].lmax >= d) return a[p*2].r-a[p*2].rmax+1; return ask(p*2+1,d); } int main(void) { freopen("hotel.in","r",stdin); freopen("hotel.out","w",stdout); n = read(); m = read(); build(1,1,n); while (m --) { int opt = read(); if (opt == 1) { int d = read(); int ans = ask(1,d); if (a[1].max < d) cnt ++; else Ans[++cnt] = ans, change(1,ans,ans+d-1,1); } if (opt == 2) { int x = read(), d = read(); change(1,x,x+d-1,2); } } for (int i=1;i<=cnt;++i) printf("%d\n", Ans[i]); return 0; }