题解 P2894 【[USACO08FEB]酒店Hotel】

· · 题解

暴力出奇迹，如果暴力没有AC,那我们就去卡常。

   在仔细观察题目后，我们发现题目需要我们维护以下两种操作。

1.给定一个正整数 D，找到一个左端点最小且它的大小 \geq D 全 0 区间，我们假设找到的这个区间为 [l,r]，我们需要将 [l,l+d-1] 赋值为 1，[l+d,r] 赋值为 0。

2.给定两个正整数 X D，我们需要将区间 [x,x+d-1] 赋值为 0。

   不难发现，操作 2 就是个很显然的区间推平，我们考虑用珂朵莉树去解决这个问题。

   首先，对于操作 2，就是个简单的区间推平，我们不难写出如下代码，表示将 [l,r] 这个区间推平为 val。

inline void assignval(int l,int r,int v=0)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,v));
}

   考虑操作 1，由于题目很显然要我们找到一个左端点最小的区间，我们不难想到一个朴素的算法，从左往右扫描 ODT 的每一个区间，找到第一个满足我们要求的区间来赋值，如果找不到这个区间，我们就输出 0。

inline void add(int sum)
{
    set<node>::iterator itl,itr;
    itl=s.begin();
    bool pd=false;
    while(itl!=s.end())
    {
        if(itl->v==1)
        {
            ++itl;
            continue;
        }
        itr=itl;
        while(itr!=s.end()&&itr->v==0)
        {
            ++itr;
        }
        bool ccpd=false;
        if(itr==s.end())
            ccpd=true;
        --itr;
        if(itr->r-itl->l+1>=sum)
        {
            pd=true;
            break;
        }
        if(ccpd)
        {
            break;
        }
        itl=itr;
        ++itl;
    }
    if(pd==false)
        puts("0");
    else
    {
        int l=itl->l,r=itr->r;
        write(l);
        putchar('\n');
        s.erase(itl,++itr);
        s.insert(node(l,l+sum-1,1));
        if(r-l+1!=sum)
        {
            s.insert(node(l+sum,r,0));
        }
    }
}

   因为我们使用了双指针进行求解，显然这样的操作是 O(ODT.size()) 的，在期望下，算法的复杂度是接近于 O(nlogn) 的。于是我们把这份代码交了上去，T 了一个点。

   难道我们真的只能用线段树来写线段树裸题了吗？虽然线段树代码量小，实现简单，复杂度具有保证，但喜欢暴力的我显然是不会去选择线段树的，考虑优化我们的ODT。

   为什么我们的算法会这么慢呢？我们不难发现，因为我们推平操作的暴力性，使得程序在运行过程中显然会出现这样的一个情况。

   是的，由于我们每次都是暴力地新建一个节点，代表我们 [l,r] 赋值为了 val，但是，在这道题里面，val 的取值只有 0 和 1，这意味着我们会有很多次操作，把一段全是 0 的区间分割成 3 个全是 0 的区间，或者刚好把一段全是 0 的区间赋值成 1，与其余的 1 接到一起。这显然不是我们想要的，但也为我们提供了一种思路，我们每次操作最多推平一个区间，如果我们每推平一个区间，都去尝试把它和相邻的两个区间做一次合并，那是不是就能减少我们的元素数量了呢？

   于是，我们不难写出如下合并代码，并将它放到别的操作里。

inline void merge(int l)
{
    set<node>::iterator it1,it2,it3;
    it2=s.lower_bound(l);
    if(it2==s.begin())
        return;
    it1=it2,it3=it2;
    it1--,++it3;
    bool pd3=(it3!=s.end());
    if(pd3&&it1->v==it2->v&&it2->v==it3->v&&it1->v==it3->v)
    {
        int l=it1->l,r=it3->r,v=it2->v;
        s.erase(it1,++it3);
        s.insert(node(l,r,v));
    }
    else if(it1->v==it2->v)
    {
        int l=it1->l,r=it2->r,v=it2->v;
        s.erase(it1,++it2);
        s.insert(node(l,r,v));
    }
    else if(pd3&&it2->v==it3->v)
    {
        int l=it2->l,r=it3->r,v=it2->v;
        s.erase(it2,++it3);
        s.insert(node(l,r,v));
    }
}

   需要注意的是，如果我们当前取出来的节点已经是 Set 的 begin 了，那我们再取它左边的元素显然是会 RE 的，需要特判一下。

   幸运的是，我们成功地把看不到跑了多少秒的 TLE 优化到了 1.01s 的 TLE 。

   现在我们只需要对几毫秒进行优化了，不难想到去卡常。

   首先我们注意到，这个题目的读入的数据比较大，于是我们用 fread 的输入替代我们原来的 getchar，同样地，对于输出，我们尽可能地用 putchar 去输出答案，对于输出 0，我们可以直接 puts("0") 。

   当然，我们还可以对很多的细节进行优化，比如 ++ 写在变量的前面，对于判断比较多的量就直接用变量存起来等，这个属于个人码风的问题，可能只有我这种代码贼丑的人会在加了第一个优化以后还不能过吧。

// luogu-judger-enable-o2
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

template <class T>
inline void write(T x)
{
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

inline char nc()
{
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &sum)
{
    char ch=nc();
    int tf=0;
    sum=0;
    while((ch<'0'||ch>'9')&&(ch!='-')) ch=nc();
    tf=((ch=='-')&&(ch=nc()));
    while(ch>='0'&&ch<='9') sum=sum*10+(ch-48),ch=nc();
    (tf)&&(sum=-sum);
}

const int MAXN=50010;

struct node
{
    mutable int l,r,v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V) {}
    bool operator<(const node &o) const
    {
        return l<o.l;
    }
};

set<node> s;

inline void check()
{
    for(set<node>::iterator it=s.begin();it!=s.end();++it)
    {
        for(int j=1;j<=(it->r-it->l+1);++j)
        {
            cout<<it->v<<" ";
        }
    }
    cout<<endl;
}

inline void merge(int l)
{
    set<node>::iterator it1,it2,it3;
    it2=s.lower_bound(l);
    if(it2==s.begin())
        return;
    it1=it2,it3=it2;
    it1--,++it3;
    bool pd3=(it3!=s.end());
    if(pd3&&it1->v==it2->v&&it2->v==it3->v&&it1->v==it3->v)
    {
        int l=it1->l,r=it3->r,v=it2->v;
        s.erase(it1,++it3);
        s.insert(node(l,r,v));
    }
    else if(it1->v==it2->v)
    {
        int l=it1->l,r=it2->r,v=it2->v;
        s.erase(it1,++it2);
        s.insert(node(l,r,v));
    }
    else if(pd3&&it2->v==it3->v)
    {
        int l=it2->l,r=it3->r,v=it2->v;
        s.erase(it2,++it3);
        s.insert(node(l,r,v));
    }
}

inline set<node>::iterator split(int pos)
{
    set<node>::iterator it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos) return it;
    --it;
    int L=it->l,R=it->r,V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

inline void assignval(int l,int r,int v=0)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,v));
    merge(l);
}

inline void add(int sum)
{
    set<node>::iterator itl,itr;
    itl=s.begin();
    bool pd=false;
    while(itl!=s.end())
    {
        if(itl->v==1)
        {
            ++itl;
            continue;
        }
        itr=itl;
        while(itr!=s.end()&&itr->v==0)
        {
            ++itr;
        }
        bool ccpd=false;
        if(itr==s.end())
            ccpd=true;
        --itr;
        if(itr->r-itl->l+1>=sum)
        {
            pd=true;
            break;
        }
        if(ccpd)
        {
            break;
        }
        itl=itr;
        ++itl;
    }
    if(pd==false)
        puts("0");
    else
    {
        int l=itl->l,r=itr->r;
        write(l);
        putchar('\n');
        s.erase(itl,++itr);
        s.insert(node(l,l+sum-1,1));
        if(r-l+1!=sum)
        {
            s.insert(node(l+sum,r,0));
        }
        merge(l);
    }
}

int n,m;

int main()
{
    read(n),read(m);
    s.insert(node(1,n,0));
    while(m--)
    {
        int op,x,y;
        read(op);
        if(op==1)
        {
            read(x);
            add(x);
        }
        else if(op==2)
        {
            read(x),read(y);
            assignval(x,x+y-1,0);
        }
    }
    return 0;
}

    在加了这些优化之后，我们就可以用 999 毫秒通过这道题目了。

999毫秒极限过题