hdu4553 约会安排
传送门
题意
一个人有长度为(n)的空闲时间，有三种操作：
1.基友来约长度为(t)的空闲时间，判断是否可行，如果可行计算开始时间最早的时刻
2.女神来约长度为(t)的空闲时间，首先判断在不耽误和之前基友约会的情况下是否可行，如果不可行，再判断在取消和某些基友约会的情况下是否可行，计算两种情况下可行时开始时间最早的时刻
3.立志好好学习，清空区间([l,r])之内的所有约会
题解
为基友和女神建立两棵线段树
(1)表示时间点空闲，(0)表示时间点被占用
三种操作的对应处理方式：
1.基友的请求只在基友线段树上找，找到之后更新也只更新基友线段树
2.女神的请求先在基友线段树上找，如果找不到再在女神线段树上找，不管在哪棵线段树上找到长度为(t)的空闲时间，都需要更新两棵线段树的对应区间，因为女神的优先级高于基友，如果一个区间被女神占了，那么既不能被基友占也不能被其他女神占
3.同时清空基友线段树和女神线段树的相应区间
(ps:)线段树区间更新需要设立(lazy)标记，但是(lazy)不能初始化成(0)，因为之前已经设定(0)表示被占用。可以将(lazy)初始化成(-1)，这样清除时也将(lazy)更改为(-1)
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=110010;
int T,n,m;
char s[10];
struct node{
int lmx,rmx,amx,lazy;
}ds[4*maxn],ns[4*maxn];
void pushup(node* tree,int o,int l,int r){
int mid=(l+r)>>1;
tree[o].lmx=tree[o<<1].lmx;
if(tree[o<<1].lmx==mid-l+1) tree[o].lmx+=tree[o<<1|1].lmx;
tree[o].rmx=tree[o<<1|1].rmx;
if(tree[o<<1|1].rmx==r-mid) tree[o].rmx+=tree[o<<1].rmx;
tree[o].amx=max(max(tree[o<<1].amx,tree[o<<1|1].amx),tree[o<<1].rmx+tree[o<<1|1].lmx);
}
void build(node* tree,int o,int l,int r){
tree[o].lazy=-1;
if(l==r){
tree[o].lmx=tree[o].rmx=tree[o].amx=1;
return;
}
int mid=(l+r)>>1;
build(tree,o<<1,l,mid);
build(tree,o<<1|1,mid+1,r);
pushup(tree,o,l,r);
}
void puttag(node* tree,int o,int l,int r,int v){
tree[o].lazy=v;
tree[o].lmx=tree[o].rmx=tree[o].amx=v*(r-l+1);
}
void pushdown(node* tree,int o,int l,int r){
if(tree[o].lazy==-1) return;
int mid=(l+r)>>1;
tree[o<<1].lazy=tree[o].lazy;
tree[o<<1|1].lazy=tree[o].lazy;
tree[o].lazy=-1;
tree[o<<1].lmx=tree[o<<1].rmx=tree[o<<1].amx=tree[o<<1].lazy*(mid-l+1);
tree[o<<1|1].lmx=tree[o<<1|1].rmx=tree[o<<1|1].amx=tree[o<<1|1].lazy*(r-mid);
}
void change(node* tree,int o,int l,int r,int ql,int qr,int v){
if(ql<=l && r<=qr){
puttag(tree,o,l,r,v);
return;
}
pushdown(tree,o,l,r);
int mid=(l+r)>>1;
if(ql<=mid) change(tree,o<<1,l,mid,ql,qr,v);
if(qr>mid) change(tree,o<<1|1,mid+1,r,ql,qr,v);
pushup(tree,o,l,r);
}
int query(node* tree,int o,int l,int r,int len){
if(tree[o].amx<len) return 0;
if(l==r) return l;
pushdown(tree,o,l,r);
int mid=(l+r)>>1;
if(tree[o<<1].amx>=len) return query(tree,o<<1,l,mid,len);
if(tree[o<<1].rmx+tree[o<<1|1].lmx>=len) return mid-tree[o<<1].rmx+1;
return query(tree,o<<1|1,mid+1,r,len);
}
int main(){
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
printf("Case %d:
",cas);
scanf("%d %d",&n,&m);
build(ds,1,1,n);
build(ns,1,1,n);
while(m--){
scanf("%s",s);
if(s[0]=='D'){
int t,x=0;
scanf("%d",&t);
x=query(ds,1,1,n,t);
if(x){
printf("%d,let's fly
",x);
change(ds,1,1,n,x,x+t-1,0);
}
else printf("fly with yourself
");
}
else if(s[0]=='N'){
int t,x=0;
scanf("%d",&t);
x=query(ds,1,1,n,t);
if(x){
change(ds,1,1,n,x,x+t-1,0);
change(ns,1,1,n,x,x+t-1,0);
}
else{
x=query(ns,1,1,n,t);
if(x){
change(ns,1,1,n,x,x+t-1,0);
change(ds,1,1,n,x,x+t-1,0);
}
}
if(x) printf("%d,don't put my gezi
",x);
else printf("wait for me
");
}
else{
int l,r;
scanf("%d %d",&l,&r);
change(ds,1,1,n,l,r,1);
change(ns,1,1,n,l,r,1);
printf("I am the hope of chinese chengxuyuan!!
");
}
}
}
return 0;
}