题解 P2894 【[USACO08FEB]酒店Hotel】

看到全是线段树的题解 那就来一个不同的吧！

我使用链表来储存空间 每一次操作的时候将可以合并的空间先进行合并 然后再探索是否有足够的空间

代码有一些冗杂所以跑得慢了一些

但是这样的链表思想可以用在许多的题目中解决内存的问题
NOI1999内存分配 就是个不错的例子

贴代码：

提示 ：

前方没有压行代码过长 请耐心食用

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#define ULL unsigned long long
#define LL long long
#define debug cout<<"bug"<<endl;
using namespace std;
const int maxn = 200110;

inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
struct node{
    int nxt,val,len,begin,endd;
}e[maxn];//单链表代替空间 
int n,m,cnt=1;

inline int check(int len)
{
    for(int u=1;u!=0;u=e[u].nxt)
    {   //合并 
        while(e[u].nxt!=0 && e[u].val==e[e[u].nxt].val )
        {
            e[u].len += e[e[u].nxt].len;
            e[u].endd = e[e[u].nxt].endd;
            e[u].nxt = e[e[u].nxt].nxt;
        }
        //分配 
        if(e[u].val==0 && e[u].len >=len)
        {
            if(e[u].len ==len)//长度正好 整体替换 
            {
                e[u].val = 1;
            }
            else
            {
                cnt++;
                e[cnt].nxt = e[u].nxt ;
                e[cnt].endd =e[u].endd ;
                e[cnt].begin =e[u].begin +len;
                e[cnt].len = e[cnt].endd -e[cnt].begin +1;
                e[u].nxt = cnt;
                e[u].val = 1;
                e[u].len =len;
                e[u].endd =e[u].begin +len-1;
            }
            return e[u].begin ;
        }
    }
    return 0;
}
inline void change(int l,int r)
{
    for(int u=1;u!=0;u=e[u].nxt)
    {   //合并 
        while(e[u].nxt!=0 && e[u].val==e[e[u].nxt].val )
        {
            e[u].len += e[e[u].nxt].len;
            e[u].endd = e[e[u].nxt].endd;
            e[u].nxt = e[e[u].nxt].nxt;
        }
        if(e[u].val == 0) continue;//已符合要求 
        if(e[u].begin > r) return;//最大范围不受控
        if(e[u].begin >=l && e[u].endd <=r) //全部修改 
            e[u].val = 0;
        else if(e[u].begin <= l && e[u].endd<=r && e[u].endd >=l) //修改后面
        {
            cnt++;
            e[cnt].endd = e[u].endd ;
            e[cnt].begin = l;
            e[cnt].len = e[cnt].endd -e[cnt].begin +1;
            e[cnt].nxt = e[u].nxt ;
            e[u].endd = l-1;
            e[u].len = e[u].endd -e[u].begin +1;
            e[u].nxt = cnt;
        }
        else if( e[u].begin >= l &&e[u].endd >=r) //修改前面 
        {
            cnt++;
            e[cnt].val = e[u].val ;
            e[cnt].endd = e[u].endd ;
            e[cnt].begin = r+1;
            e[cnt].len = e[cnt].endd -e[cnt].begin +1;
            e[cnt].nxt = e[u].nxt ;
            e[u].nxt = cnt;
            e[u].endd = r;
            e[u].val = 0;
            e[u].len = e[u].endd -e[u].begin +1;
        }
        else if(e[u].begin<=l && r<=e[u].endd )//修改中间
        {
            cnt++;
            e[cnt].begin = l;
            e[cnt].endd = e[u].endd; 
            e[cnt].len = e[cnt].endd -e[cnt].begin +1;
            e[cnt].val = e[u].val ;
            e[cnt].nxt = e[u].nxt ;
            e[u].nxt = cnt;
            e[u].endd = l-1;
            e[u].len = e[u].endd -e[u].begin +1;
            u=cnt;
            cnt++;
            e[cnt].begin = r+1;
            e[cnt].endd = e[u].endd ;
            e[cnt].len = e[cnt].endd -e[cnt].begin +1;
            e[cnt].val = e[u].val ;
            e[cnt].nxt = e[u].nxt ;
            e[u].endd = r;
            e[u].val = 0;
            e[u].nxt = cnt;
            e[u].len = e[u].endd -e[u].begin +1;
        }
    }
} 
int main()
{
//    freopen("b.in","r",stdin);
//    freopen("b.out","w",stdout);
    read(n),read(m);
    e[1].len = n;
    e[1].begin = 1;
    e[1].endd = n;
    int c,a,b;
    while(m--)
    {
        read(c);
        if(c==1)//查询 
        {
            read(a);
            printf("%d\n",check(a));
        }
        else//改变 
        {
            read(a),read(b);
            change(a,a+b-1);
        }
    }
    return 0;
}