首页 > 其他分享 >P2894 [USACO08FEB]Hotel G

P2894 [USACO08FEB]Hotel G

时间:2022-08-27 09:56:10浏览次数:99  
标签:return int 线段 Hotel USACO08FEB P2894 query 最长

P2894 [USACO08FEB]Hotel G

分析

题目很简单,给自己复建用的,好久没打代码了,摸鱼必死qwq。

我们读完题目,可以很容易发现,这题就是要维护最长连续区间,区间内全为0。

维护最长连续区间,那就经典维护三个值。lenllenrlen。分别表示维护,区间最长的线段,从左开始最长线段,从右开始最长线段。

相对于维护的值,可能相对查询会更麻烦些。

查询:需要我们查询起始点最靠左的长度大于等于x的线段的左端点是什么。

等于说是,我们要寻找满足某些条件的最靠左的线段

那,很容易就可以想到线段树上二分

那本题就结束了。

看代码。

AC_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;

const int N = 5e4 + 10;

struct Node
{
    int l,r;
    int len,llen,rlen,tag;
}tr[N<<2];

void pushup(int u)
{
    auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
    root.len = max(right.len,left.len);
    root.llen = tr[u<<1].llen;root.rlen = right.rlen;
    if(left.llen==left.r-left.l+1) root.llen += right.llen;
    if(right.rlen==right.r-right.l+1) root.rlen += left.rlen;
    root.len = max(root.len,max(left.rlen+right.llen,max(root.llen,root.rlen)));
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u] = {l,r,1,1,1,-1};
        return ;
    }
    tr[u] = {l,r,0,0,0,-1};
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

void change(Node &u,int k)
{
    if(!k) u.len = u.rlen = u.llen = u.r - u.l + 1;
    else u.len = u.rlen = u.llen = 0;
    u.tag = k;
}

void pushdown(int u)
{
    if(tr[u].tag!=-1)
    {
        change(tr[u<<1],tr[u].tag);
        change(tr[u<<1|1],tr[u].tag);
        tr[u].tag = -1;
    }
}

void modify(int u,int l,int r,int k)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        change(tr[u],k);
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l<=mid) modify(u<<1,l,r,k);
    if(r>mid) modify(u<<1|1,l,r,k);
    pushup(u);
}

int query(int u,int x)
{
    if(tr[u].l==tr[u].r) return tr[u].l;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(tr[u<<1].len>=x) return query(u<<1,x);
    else if(tr[u<<1].rlen+tr[u<<1|1].llen>=x) return query(u<<1|1,x-tr[u<<1].rlen);
    else if(tr[u<<1|1].len>=x) return query(u<<1|1,x);
    return 0;
}

int main()
{
    ios;
    int n,m;
    cin>>n>>m;
    build(1,1,n);
    while(m--)
    {
        int op,x,y;
        cin>>op>>x;
        if(op==1)
        {
            int t = query(1,x);
            if(t)
            {
                cout<<t-x+1<<"\n";
                modify(1,t-x+1,t,1);
            }
            else cout<<"0\n";
        }
        else 
        {
            cin>>y;
            modify(1,x,x+y-1,0);
        }
    }
    return 0;
}

标签:return,int,线段,Hotel,USACO08FEB,P2894,query,最长
From: https://www.cnblogs.com/aitejiu/p/16629861.html

相关文章