题目意思大概就是有一连串的房子。客人来时会要求订其中连续的 k 个房子,要你给出连续 k 个房子的最小编号。同时也会退订房间的操作。
用线段树来维护房子的订阅情况。线段树记录 4 个域。
struct Node{
int Lx; // 区间从左端点起连续的最大长度
int Rx; // 区间以右端点结束的最大连续长度
int Ax; // 区间全局最大连续长度
int cover; // 标记区间是否被覆盖 0, 1, -1
};
cover 为 0 表示这个区间里的房子都没订,为 1 表示这个区间房子都订了, 为 -1 表示其它情况。
Lx, Rx 是为了更新 Ax。。
代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int const N= 50010;
int n, m;
int COLOR;
struct Node{
int Lx; // 区间从左端点起连续的最大长度
int Rx; // 区间以右端点结束的最大连续长度
int Ax; // 区间全局最大连续长度
int cover; // 标记区间是否被覆盖 0, 1, -1
}
tb[N<<2];
void build( int L, int R, int rt ){
if( L== R ){
tb[rt].Lx= 1; tb[rt].Rx= 1; tb[rt].Ax= 1;
return;
}
int mid= (L+ R)>>1;
build( L, mid, rt<<1 );
build( mid+ 1, R, rt<<1|1 );
tb[rt].Lx= tb[rt].Rx= tb[rt].Ax= R- L+ 1;
tb[rt].cover= 0;
}
int query( int x, int L, int R, int rt ){
if( tb[rt].Ax== x && R- L+ 1== x ) return L;
if( tb[rt].Ax>= x ){
int mid= (L+ R)>>1;
if( tb[rt].cover!= -1 ){
tb[rt<<1].cover= tb[rt<<1|1].cover= tb[rt].cover;
if( tb[rt].cover== 0 ){
tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= mid- L+ 1;
tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= R- mid;
}
else{
tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= 0;
tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= 0;
}
tb[rt].cover= -1;
}
if( tb[rt<<1].Ax>= x ) return query( x, L, mid, rt<<1 );
else if( min( mid- L+ 1, tb[rt<<1].Rx )+ min( R- mid, tb[rt<<1|1].Lx )>= x ){
return mid- min( mid- L+ 1, tb[rt<<1].Rx )+ 1;
}
else if( tb[rt<<1|1].Ax>= x ) return query( x, mid+ 1, R, rt<<1| 1 );
}
return 0;
}
void update( int x, int y, int L, int R, int rt ){
if( L== x && R== y ){
tb[rt].cover= COLOR;
if( COLOR== 0 ) tb[rt].Ax= tb[rt].Lx= tb[rt].Rx= R- L+ 1;
else tb[rt].Ax= tb[rt].Lx= tb[rt].Rx= 0;
return;
}
int mid= (L+ R)>>1;
if( tb[rt].cover!= -1 ){
tb[rt<<1].cover= tb[rt<<1|1].cover= tb[rt].cover;
if( tb[rt].cover== 0 ){
tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= mid- L+ 1;
tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= R- mid;
}
else{
tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= 0;
tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= 0;
}
tb[rt].cover= -1;
}
if( y<= mid ) update( x, y, L, mid, rt<<1 );
else if( x> mid ) update( x, y, mid+ 1, R, rt<<1|1 );
else{
update( x, mid, L, mid, rt<<1 );
update( mid+ 1, y, mid+ 1, R, rt<<1|1 );
}
tb[rt].Ax= max( tb[rt<<1].Ax, tb[rt<<1|1].Ax );
if( tb[rt<<1].Lx== mid- L+ 1 ) tb[rt].Lx= tb[rt<<1].Lx+ tb[rt<<1|1].Lx;
else tb[rt].Lx= tb[rt<<1].Lx;
if( tb[rt<<1|1].Rx== R- mid ) tb[rt].Rx= tb[rt<<1|1].Rx+ tb[rt<<1].Rx;
else tb[rt].Rx= tb[rt<<1|1].Rx;
tb[rt].Ax= max( tb[rt].Ax, max( tb[rt].Lx, tb[rt].Rx ) );
tb[rt].Ax= max( tb[rt].Ax, tb[rt<<1].Rx+ tb[rt<<1|1].Lx );
}
int main(){
scanf("%d%d",&n,&m );
build( 1, n, 1 );
for( int i= 0; i< m; ++i ){
int x, y, z;
scanf("%d",&x);
if( x== 1 ){
scanf("%d",&y );
int pos= query( y, 1, n, 1 );
printf("%d\n", pos );
if( pos!= 0 ){
COLOR= 1;
update( pos, pos+ y- 1, 1, n, 1 );
}
}
else{
scanf("%d%d",&y,&z );
COLOR= 0;
update( y, y+ z- 1, 1, n, 1 );
}
}
return 0;
}
分享到:
相关推荐
PKU2104是北京大学的一道算法题目,其提供的源代码着重展示了线段树在“找数据”问题中的应用。 线段树的基本思想是将一个区间分解为若干个子区间,然后对每个子区间构建一棵小树,这些小树通过节点连接形成一个...
标题“PKU 、POJ ACM/ICPC300多题的代码”指的是北京大学(PKU)和编程在线评测平台POJ上收集的300多道ACM/ICPC(国际大学生程序设计竞赛)比赛题目解题代码。这个压缩包包含了解决这些竞赛问题的算法和程序实现,是...
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
标题中的“pku1151.rar_Atlantis_pku 11_poj Atlant_poj Atlantis_poj11”似乎是指北京大学(Peking University, PKU)编程竞赛中的一道题目,编号为1151,与“Atlantis”这个主题相关。这道题目在多个平台上也被提及...
线段树是一种非常有效的数据结构,主要用于解决区间查询和更新的问题,常用于算法竞赛和实际应用中的问题求解。接下来,我们将详细探讨“线段树六题”中各个题目的相关知识点。 ### 1. PKU2352 star2 校门外的树 **...
标题“PKU_poj 1001~1009”揭示了这是一组与北京大学(Peking University)编程竞赛平台POJ相关的解决方案。在这个压缩包中,包含了从问题1001到1009的C++源代码,表明这些代码已经过验证并成功解决了对应的算法问题。...
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
根据给定的文件信息,我们可以总结出以下关于POJ(PKU)问题2494“Acid Text”以及其Java代码实现的关键知识点: ### 1. POJ(PKU)2494:Acid Text POJ(Peking University Online Judge)是北京大学的一个在线...
标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...
### 线段树例题解析 #### Brackets (SPOJ61, BRCKTS) **题目描述:** 此题要求我们维护一个长度为 \(N\) 的小括号序列 \(A\),并支持两种操作: 1. **Replace(i)**:将第 \(i\) 个位置的括号方向反转。 2. **Check...
标题中的“pku1088.rar_pku 10_pku 1088_poj 1088”指的是北京大学(Peking University, PKU)编程竞赛中的第1088题,也称为POJ(Peking University Online Judge)的1088题。这个题目在编程竞赛社区中通常有一个特定的...
10. **POJ 2528 线段树.txt**:这是第三个线段树相关的题目,解题报告可能会深入讲解线段树在不同场景下的应用。 通过阅读这些解题报告,你可以学习到各种高级算法的应用,如动态规划、搜索算法、数据结构(如线段...
标题中的"poj3252.rar_pku 3252_poj32"表明这是一个与编程竞赛相关的资源,具体来说是北京大学(PKU)ACM竞赛中的问题3252。"poj"通常指的是"Programming Online Judge",这是一个在线编程比赛平台,而"Pku"则代表...
【标题】"poj 130题 acm pku" 涉及的是ACM(国际大学生程序设计竞赛)中的PKU(北京大学)在线判题系统POJ(Problem Online Judge)的相关题目。ACM/ICPC(International Collegiate Programming Contest)是全球...
根据提供的文件信息,我们可以分析出该段代码是用于解决POJ平台上的2314题的一种解决方案,主要涉及到了变量管理、表达式处理等方面。下面将详细解释代码中的关键概念和实现逻辑。 ### 关键概念解析 #### Variable...
### PKU POJ 1162 Building with Blocks 解题报告 #### 题目概述 本题名为“Building with Blocks”,属于经典的积木搭建问题。题目要求利用一定数量的基本单位积木,搭建出特定的三维形状。积木的种类不超过12种,...
“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/ 及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计...
根据提供的标题“poj pku图论、网络流入门题总结、汇总”及描述“很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析”,本篇将对这些经典图论与网络流问题进行详细的分析和总结。通过梳理各题目及其...
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
标题 "pku 123 题目代码" 暗示了这是一个与北京大学(Peking University)编程竞赛(PKU ACM/ICPC)相关的代码集合,可能包含了参赛者为解决PKU ACM在线判题系统(PJU POJ)上的123道题目所编写的程序。POJ是北京大学维护...