USACO Hotel

洛谷传送门

JDOJ传送门

Description

The cows are journeying north to Thunder Bay in Canada to gain
cultural enrichment and enjoy a vacation on the sunny shores of
Lake Superior. Bessie, ever the competent travel agent, has named
the Bullmoose Hotel on famed Cumberland Street as their vacation
residence. This immense hotel has N (1 <= N <= 50,000) rooms all
located on the same side of an extremely long hallway (all the
better to see the lake, of course).

The cows and other visitors arrive in groups of size D_i (1 <= D_i
<= N) and approach the front desk to check in. Each group i requests
a set of D_i contiguous rooms from Canmuu, the moose staffing the
counter. He assigns them some set of consecutive room numbers
r..r+D_i-1 if they are available or, if no contiguous set of rooms
is available, politely suggests alternate lodging. Canmuu always
chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms.
Checkout i has the parameters X_i and D_i which specify the vacating
of rooms X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1). Some (or all) of
those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 <= M < 50,000)
checkin/checkout requests. The hotel is initially unoccupied.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 contains request expressed as one of two
possible formats: (a) Two space separated integers
representing a check-in request: 1 and D_i (b) Three
space-separated integers representing a check-out: 2, X_i, and
D_i

Output

* Lines 1.....: For each check-in request, output a single line with a
single integer r, the first room in the contiguous sequence of
rooms to be occupied. If the request cannot be satisfied,
output 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

最优解声明：

emm...换个了号刷题（冲其他人借的号，并非新号），刷了双份最优解，懂得自然懂（狗头保命

题解：

这道题和小白逛公园有一点神似。

蒟蒻在这里瞎xx总结一下：类似这种区间最优化问题，都可以往这边想一想：既然线段树只维护一个信息没有办法转移，就多维护几个信息。类似这种“区间连续最优化”的问题，就尝试着维护\(lmax[]/rmax[]\)数组，然后进行线段树上的维护和转移。（肤浅之见，欢迎指正）

这样想的话，这道题的状态就比较好想了：令\(tree[]\)表示区间最长连续空房多长，\(lmax[]/rmax[]\)分别表示从左/从右开始的最长连续空房多长，\(len[]\)表示区间总长。

转移也和小白逛公园相似。需要注意的是，小白逛公园因为不需要维护“连续为空”，而只需要维护“最大子段和”，所以无脑max就可以。但是这道题需要加一个判断。如\(pushup()\)函数所示，应该很容易看懂。

最后分享蒟蒻在lazy标记上犯下的一个错误：这道题的lazy标记有两种。一种是开房，一种是退房。这都比较好维护。但是需要注意的是，这道题不能无脑下传lazy标记，也就是需要判断lazy标记是否为0，是0的话就不能下传。原理很简单，如果下传0的话，可能会导致已经有lazy标记的节点的lazy标记被清空。如果是普通线段树，单纯维护和的话，就可以无脑下传，因为lazy+0对其毫无影响。

数据结构的题细节很多，还要多多注意。

附AC代码：

#include<cstdio>
#include<algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=5*1e4+10;
int n,m;
int tree[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],len[maxn<<2],lazy[maxn<<2];
void pushup(int pos)
{
    len[pos]=len[lson]+len[rson];
    if(lmax[lson]==len[lson])
        lmax[pos]=len[lson]+lmax[rson];
    else
        lmax[pos]=lmax[lson];
    if(rmax[rson]==len[rson])
        rmax[pos]=len[rson]+rmax[lson];
    else
        rmax[pos]=rmax[rson];
    tree[pos]=max(max(tree[lson],tree[rson]),lmax[rson]+rmax[lson]);
}
void build(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    if(l==r)
    {
        tree[pos]=lmax[pos]=rmax[pos]=len[pos]=1;
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(pos);
}
void mark(int pos,int l,int r,int k)
{
    lazy[pos]=k;
    if(k==1)//住人
        tree[pos]=lmax[pos]=rmax[pos]=0;
    if(k==2)//退房
        tree[pos]=lmax[pos]=rmax[pos]=len[pos];
}
void pushdown(int pos,int l,int r)
{
    if(!lazy[pos])
        return;
    int mid=(l+r)>>1;
    mark(lson,l,mid,lazy[pos]);
    mark(rson,mid+1,r,lazy[pos]);
    lazy[pos]=0;
}
void update(int pos,int l,int r,int x,int y,int k)
{
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
    {
        mark(pos,l,r,k);
        return;
    }
    pushdown(pos,l,r);
    if(x<=mid)
        update(lson,l,mid,x,y,k);
    if(y>mid)
        update(rson,mid+1,r,x,y,k);
    pushup(pos);
}
int query(int pos,int l,int r,int x)
{
    int mid=(l+r)>>1;
    if(l==r)
        return l;
    pushdown(pos,l,r);
    if(tree[lson]>=x)
        return query(lson,l,mid,x);
    if(lmax[rson]+rmax[lson]>=x)
        return mid-rmax[lson]+1;
    return query(rson,mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d",&x);
            if(tree[1]>=x)
            {
                int ans=query(1,1,n,x);
                printf("%d\n",ans);
                update(1,1,n,ans,ans+x-1,1);//1为住人
            }
            else
                puts("0");
        }
        else
        {
            scanf("%d%d",&x,&y);
            update(1,1,n,x,x+y-1,2);//2为退房
        }
    }
    return 0;
}