526互联

[USACO08FEB]Hotel G

发布时间 2023-04-03 11:02:52作者: magicat

[USACO08FEB]Hotel G

线段树二分，最大字段和

对于操作二，是很简单的区间赋值

对于操作一，长度为\(len\)的,我们要找到最小的的 \(x\) 满足 \([x, x + len -1]\) 的房间为空

在最大字段和的基础上，我们可以求出最长连续空房间的长度，对于要求长度为\(len\)的房间，可以按顺序判断：

  1. 若左区间的最大长度满足要求，先选择左区间
  2. \(\text{左区间的右端最大长度} + \text{右区间的左端最大长度} \geq len\), 答案为\(mid - \text{左区间的右端最大长度}\), 此处\(mid\)左区间的右端点
  3. 若右区间的最大长度满足要求，选择右区间
//  AC one more times
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<long long,long long> PLL;
const int mod = 1e9+7;
const int N=5e5+10;

struct info
{
    int s,ls,rs,ms;
};

info operator + (const info &a,const info &b)
{
    info t;
    t.s=a.s+b.s;
    t.ls=a.ls;
    t.rs=b.rs;
    if(a.ls==a.s)
        t.ls=a.s+b.ls;
    if(b.rs==b.s)
        t.rs=b.s+a.rs;
    t.ms=max({a.ms,b.ms,t.ls,t.rs,a.rs+b.ls});
    return t;
}

struct segtree
{
    struct info val;
    int tag,sz;
}seg[N*4];

void update(int id)
{
    seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,int tag)
{
    seg[id].tag=tag;
    int sz=seg[id].val.s;
    if(tag==0)
        seg[id].val={sz,0,0,0};
    else if(tag==1)
        seg[id].val={sz,sz,sz,sz};
}

void pushdown(int id)
{
    if(seg[id].tag!=-1)
    {
        settag(id*2,seg[id].tag);
        settag(id*2+1,seg[id].tag);
        seg[id].tag=-1;
    }
}

void build(int id,int l,int r)
{
    seg[id].tag=-1;
    seg[id].sz=r-l+1;
    if(l==r)
    {
        seg[id].val={1,1,1,1};
        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    update(id);
}

void modify(int id,int l,int r,int ql,int qr,int tag)
{
    if(l==ql&&r==qr)
    {
        settag(id,tag);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(qr<=mid)
        modify(id*2,l,mid,ql,qr,tag);
    else if(ql>mid)
        modify(id*2+1,mid+1,r,ql,qr,tag);
    else 
        modify(id*2,l,mid,ql,mid,tag),
        modify(id*2+1,mid+1,r,mid+1,qr,tag);
    update(id);
}

int query(int id,int l,int r,int cnt)
{
    if(l==r)
    {
        return l;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(seg[id*2].val.ms>=cnt)
        return query(id*2,l,mid,cnt);
    else if(
        seg[id*2].val.rs+seg[id*2+1].val.ls>=cnt)
        return mid-seg[id*2].val.rs+1;
    else return query(id*2+1,mid+1,r,cnt);
}
 
void solve()
{
    int n,q;
    cin>>n>>q;
    build(1,1,n);
    while(q--)
    {
        int op; cin>>op;
        if(op==1)
        {
            int x;  cin>>x;
            if(seg[1].val.ms<x)
            {
                cout<<0<<endl;
                continue;
            }
            int pos=query(1,1,n,x);
            cout<<pos<<endl;
            modify(1,1,n,pos,pos+x-1,0);
        }
        else if(op==2)
        {
            int x,y;    cin>>x>>y;
            modify(1,1,n,x,x+y-1,1);
        }
    }
    return;
}
  
int main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int TC = 1;
    
    //cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }


    return 0;
}