首页 > 其他分享 > [USACO08FEB]Hotel G 线段树区间合并|维护最长的连续1

[USACO08FEB]Hotel G 线段树区间合并|维护最长的连续1

时间:2023-03-28 09:34:49浏览次数:38  
标签:rt int 线段 Hotel mid ls ans USACO08FEB query

这个还是看代码,比讲的清楚

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;
const int maxn=5e4+5;
int n,m;
struct tree{
    int lmx,rmx,mx,lazy,len;
}t[maxn<<2];
void push_down(int rt){
    if(!t[rt].lazy) return;
    if(t[rt].len==1){
        t[rt].lazy=0;
        return;
    }
    if(t[rt].lazy==1){
        t[ls].lmx=t[ls].rmx=t[ls].mx=t[ls].len;
        t[ls].lazy=1;
        t[rs].lmx=t[rs].rmx=t[rs].mx=t[rs].len;
        t[rs].lazy=1;
    }
    if(t[rt].lazy==2){
        t[ls].lmx=t[ls].rmx=t[ls].mx=0;
        t[ls].lazy=2;
        t[rs].lmx=t[rs].rmx=t[rs].mx=0;
        t[rs].lazy=2;
    }
    t[rt].lazy=0;
}
void push_up(int rt){
    //lmx
    if(t[ls].lmx==t[ls].len){
        t[rt].lmx=t[ls].len+t[rs].lmx;
    }
    else if(t[ls].lmx!=t[ls].len){
        t[rt].lmx=t[ls].lmx;
    }
    //rmx
    if(t[rs].rmx==t[rs].len){
        t[rt].rmx=t[rs].len+t[ls].rmx;
    }
    else if(t[rs].rmx!=t[rs].len){
        t[rt].rmx=t[rs].rmx;
    }
    //mx
    t[rt].mx=max(max(t[ls].mx,t[rs].mx),t[ls].rmx+t[rs].lmx);
}
void build(int rt,int l,int r){
    t[rt].len=r-l+1;
    t[rt].lazy=0;
    t[rt].lmx=t[rt].rmx=t[rt].mx=t[rt].len;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
}
void update(int rt,int ql,int qr,int op,int l=1,int r=n){
    if(ql<=l&&r<=qr){
        if(op==1){//退房 
            t[rt].lmx=t[rt].rmx=t[rt].mx=t[rt].len;
            t[rt].lazy=1;
        }
        if(op==2){
            t[rt].lmx=t[rt].rmx=t[rt].mx=0;
            t[rt].lazy=2;
        }
        return;
    }
    push_down(rt);
    int mid=l+r>>1;
    if(ql<=mid) update(ls,ql,qr,op,l,mid);
    if(qr>mid) update(rs,ql,qr,op,mid+1,r);
    push_up(rt);
}
int query(int rt,int x,int l=1,int r=n){
    if(l==r){
        return l;
    }
    push_down(rt);
    int mid=l+r>>1,ans=0;
    if(t[ls].mx>=x) ans= query(ls,x,l,mid);
    else if(t[ls].rmx+t[rs].lmx>=x) ans= mid-t[ls].rmx+1;
    else ans= query(rs,x,mid+1,r);
    push_up(rt);
    return ans;
}
int main(){
    fastio;
    //freopen("lys.in","r",stdin);
    cin>>n>>m;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op;cin>>op;
        if(op==1){
            int x;
            cin>>x;
            if(t[1].mx>=x) {
               int pos=query(1,x);
               cout<<pos<<endl;
               update(1,pos,pos+x-1,2);    
            }
            else cout<<0<<endl;
        }
        else {
            int x,y;
            cin>>x>>y;
            update(1,x,x+y-1,1);
        }
    }
}

 

标签:rt,int,线段,Hotel,mid,ls,ans,USACO08FEB,query
From: https://www.cnblogs.com/liyishui2003/p/17263834.html

相关文章

  • 【hdu6547】Tree(树链剖分, 线段树区间根号)
    problemalgorihtm1、树链剖分什么是树链剖分(重链剖分)?树链,就是树上的路径。剖分,就是把路径分类为重链和轻链。对于树上的一个点,与其相连的边中,连向的节点子树大小最大(重儿子)......
  • 线段树
    #include<cstdio>#pragmawarning(disable:4996)usingnamespacestd;inta[10001];//结构体,存线段树structnode{intl,r,v;}tree[40001];//建树void......
  • 黑暗爆炸OJ #4695. 最假女选手 吉司机线段树
      传送门  题解还是这篇博客。PS:现在不挂梯子好像上不去了。  由于这篇博客只是讲的比较详细但是没有代码。贴一贴代码并且稍微讲讲每个函数的作用。  这题和......
  • 吉司机线段树
    吉司机线段树线段树3https://www.luogu.com.cn/problem/P6242Q1.对于所有的i∈[l,r],将Ai加上k(k可以为负数)对于k的值,我们分类讨论,讨论其对区间最大值的影响 1)k=......
  • bzoj 2006 [NOI2010] 超级钢琴 线段树求区间极值+优先队列
    挺神奇的一道题,唯一想不通的是为什么放在主席树的题单里..首先暴力找出所有的合法区间显然是不可能的。考虑怎么贪心,假如固定每个L作为左端点,那么合法的区间就是[L+l-1,L......
  • 2023年中国传媒大学程序设计大赛 G.跳台滑雪 线段树
    传送门#include<iostream>#include<cstring>#include<iomanip>#include<algorithm>#include<stack>#include<queue>#include<numeric>#include<cassert>#......
  • Vue+Openlayers实现绘制线段并测量距离显示
    场景在上面已经实现交互式绘制线段基础上,怎样实现测量距离。注:关注公众号霸道的程序猿获取编程相关电子书、教程推送与免费下载。实现1、页面上添加按钮与map<template>......
  • CAD如何检查线是否连接?CAD线段连接检查技巧
    在CAD制图过程中,当需要生成填充、计算面积和生成面域时,偶尔会遇到区域未封闭的情况。此时便需要检查图纸中的CAD线段连接状态,那CAD如何检查线是否连接呢?本文小编就来给大家......
  • 【Unity3D】使用GL绘制线段
    1前言​线段渲染器LineRenderer、拖尾TrailRenderer、绘制物体表面三角形网格从不同角度介绍了绘制线段的方法,本文再介绍一种新的绘制线段的方法:使用GL绘制线段。......
  • [DS记录] 线段树 Beats
    0.前言所谓线段树Beats,就是吉老师打出来的线段树。1.基本操作P6242线段树3区间加区间取min区间最大值区间和区间历史最大值首先考虑134咋做。就......