luogu2894 [USACO08FEB]酒店Hotel
2024-08-30 15:42:30
跟线段树求区间最值一样每个节点维护左边开始的最大连续空房间数、右边开始的最大连续空房间数、这个区间内的最大连续空房间数
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, opt, uu, vv;
struct SGT{
int lma[200005], rma[200005], sum[200005], tag[200005];
//sum means there are how many empty rooms
//tag==2 means these room should be clear, 1 means not
void pushUp(int o, int l, int r, int lson, int rson, int mid){
if(sum[lson]==mid-l+1) lma[o] = mid - l + 1 + lma[rson];
else lma[o] = lma[lson];
if(sum[rson]==r-mid) rma[o] = r - mid + rma[lson];
else rma[o] = rma[rson];
sum[o] = max(rma[lson] + lma[rson], max(sum[lson], sum[rson]));
}
void pushDown(int o, int l, int r, int lson, int rson, int mid){
tag[lson] = tag[rson] = tag[o];
sum[lson] = lma[lson] = rma[lson] = (mid - l + 1) * (tag[o] - 1);
sum[rson] = lma[rson] = rma[rson] = (r - mid) * (tag[o] - 1);
tag[o] = 0;
}
void build(int o, int l, int r){
if(l==r) lma[o] = rma[o] = sum[o] = 1;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(l<=mid) build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
pushUp(o, l, r, lson, rson, mid);
}
}
int query(int o, int l, int r, int x){
if(l==r) return l;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(tag[o]) pushDown(o, l, r, lson, rson, mid);
if(sum[lson]>=x) return query(lson, l, mid, x);
else if(rma[lson]+lma[rson]>=x) return mid-rma[lson]+1;
else return query(rson, mid+1, r, x);
}
}
void modify(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y){
sum[o] = lma[o] = rma[o] = (r - l + 1) * (k - 1);
tag[o] = k;
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(tag[o]) pushDown(o, l, r, lson, rson, mid);
if(x<=mid) modify(lson, l, mid, x, y, k);
if(mid<y) modify(rson, mid+1, r, x, y, k);
pushUp(o, l, r, lson, rson, mid);
}
}
}sgt;
int main(){
cin>>n>>m;
sgt.build(1, 1, n);
while(m--){
scanf("%d", &opt);
if(opt==1){
scanf("%d", &uu);
if(sgt.sum[1]<uu) printf("0\n");
else{
int ans=sgt.query(1, 1, n, uu);
printf("%d\n", ans);
sgt.modify(1, 1, n, ans, ans+uu-1, 1);
}
}
else{
scanf("%d %d", &uu, &vv);
sgt.modify(1, 1, n, uu, uu+vv-1, 2);
}
}
return 0;
}
最新文章
- 第二天----列表、元组、字符串、算数运算、字典、while
- excel将单元格格式由数字转为文本
- loadrunner agent 中删除失效的mmdrv进程
- 如何改变 FMX ListView 颜色
- winform去掉右上角关闭按钮
- zabbix(sql注入判断脚本)
- php中检查文件或目录是否存在的代码小结
- Codeforces Gym 100531I Instruction 构造
- 【GDOI2014 DAY2】Beyond （扩展KMP）
- Qt学习博客推荐
- IOS详解TableView——选项抽屉（天猫商品列表）
- linux shell——md5sum,sha1sum,sort,uniq (转)
- 使用Docker搭建简易的 Java Web 环境
- JPQL
- Linux文件目录
- WebService概念和使用
- async get_event_loop
- 实时计算DStream下求平均值（reduceByKey or combineByKey）
- eclipse/intellij idea 查看java源码和注释
- Android开发点滴 - 如何使按钮水平垂直居中且始终占据屏幕宽度一半