BZOJ 1593: [Usaco2008 Feb]Hotel 旅馆 [线段树]

传送门

题意:

操作1:找长为$len$的空区间并填满,没有输出$0$

操作2:将$[l,r]$之间的区间置空


我真是太弱了这种线段树还写了一个半小时,中间为了查错手动模拟了$30min$线段树操作,然后发现$zz$的寻找时没有单独判断跨过中间的情况,自以为看一下$t[x].pos$就可以了...

然后交到洛谷$T$了一个点,交到$BZOJ$跑了$7s$度人家都是不到半秒,突然发现自己的寻找是$nlogn$的......然后改成$logn$又出了点小问题无奈加上了判断$l==r$.....我太弱了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
#define lson lc,l,mid
#define rson rc,mid+1,r
const int N=1e5+,INF=1e9;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
} int n,Q,op,p,len;
struct Node{
int mx,lm,rm,pos,rpos;
int tag;
Node():mx(),lm(),rm(){}
void debug(){printf("%d %d %d %d %d %d\n",mx,lm,rm,pos,rpos,tag);}
}t[N<<]; inline void merge(int x,int l,int r){
if(t[lc].mx>t[rc].mx)
t[x].mx=t[lc].mx,t[x].pos=t[lc].pos;
else t[x].mx=t[rc].mx,t[x].pos=t[rc].pos;
if(t[lc].rm+t[rc].lm>t[x].mx) t[x].mx=t[lc].rm+t[rc].lm,t[x].pos=t[lc].rpos; if(t[lc].lm==mid-l+) t[x].lm=t[lc].lm+t[rc].lm;
else t[x].lm=t[lc].lm;
if(t[rc].rm==r-mid&&t[lc].rm)
t[x].rm=t[rc].rm+t[lc].rm,t[x].rpos=t[lc].rpos;
else t[x].rm=t[rc].rm, t[x].rpos=t[rc].rpos;
} inline void paint(int x,int l,int r,int v){
t[x].tag=v;
if(v==) t[x].mx=t[x].lm=t[x].rm=,t[x].pos=t[x].rpos=INF;
else t[x].mx=t[x].lm=t[x].rm=r-l+,t[x].pos=t[x].rpos=l;
}
inline void pushDown(int x,int l,int r){
if(t[x].tag){
paint(lson,t[x].tag);
paint(rson,t[x].tag);
t[x].tag=;
}
}
void build(int x,int l,int r){
if(l==r) t[x].mx=t[x].lm=t[x].rm=,t[x].pos=t[x].rpos=l;
else{
build(lson);
build(rson);
merge(x,l,r);
}
//printf("build %d %d %d \n",x,l,r);
//t[x].debug();
} void segAdd(int x,int l,int r,int ql,int qr,int v){//printf("segAdd %d %d %d\n",x,l,r);
if(ql<=l&&r<=qr) paint(x,l,r,v);
else{
pushDown(x,l,r);
if(ql<=mid) segAdd(lson,ql,qr,v);
if(mid<qr) segAdd(rson,ql,qr,v);
merge(x,l,r);
}
//printf("segAdd %d %d %d\n",x,l,r);
//t[x].debug();
} int segFin(int x,int l,int r,int len){//printf("segFin %d %d %d %d %d\n",x,l,r,len,t[x].mx);
if(l==r) return l;
if(t[x].mx<len) return INF;
else{
pushDown(x,l,r);
if(t[lc].mx>=len) return segFin(lson,len);
else if(t[lc].rm+t[rc].lm>=len&&t[lc].rm) return t[lc].rpos;
else return segFin(rson,len);
}
} inline void Query1(int len){
if(t[].mx<len) puts("");
else{
int ans=segFin(,,n,len);
printf("%d\n",ans);
segAdd(,,n,ans,ans+len-,);//printf("ql qr %d %d\n",ans,ans+len-1);
}
}
inline void Query2(int ql,int qr){
segAdd(,,n,ql,qr,-);
} int main(){
freopen("in","r",stdin);
//freopen("out","w",stdout);
n=read();Q=read();
build(,,n);
for(int id=;id<=Q;id++){//printf("Q %d %d\n",id,t[1<<1].mx);
op=read();
if(op==) len=read(),Query1(len);
else p=read(),len=read(),Query2(p,p+len-);
}
}
上一篇:C语言中字符数组和字符串指针分析


下一篇:Jdk1.6 JUC源码解析(13)-LinkedBlockingQueue