- 题意: 一维区间,有申请一段连续区间的操作,优先级高的申请可以覆盖优先级低的,还可以清空一段区间的申请.问对每次申请的结果.
- 思路: 为两种申请都创建一颗线段树,每个节点保存左区间最长的,右区间最长的和总区间最长的连续区间
#include<string>
#include<vector>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define FOR(i,l,r) for(int i = l ; i <= r ;++i )
#define inf 1<<30
#define EPS (1e-9)
#define lson(p) (p<<1)
#define rson(p) (p<<1|1)
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5+30;
int n,m;
struct node{
int l,r;
int lsum,rsum,ssum;
}a[N<<2],b[N<<2];
void push_up(int rt,int l,int r){
int mid = (l+r)>>1;
a[rt].lsum = a[lson(rt)].lsum; // 左子树的左连续空间更新父亲
a[rt].rsum = a[rson(rt)].rsum; // 右子树的右连续空间更新父亲
// 总连续空间为 max(左子树总连续,右子树总连续, 左子树右连续+右子树左连续)
a[rt].ssum = max(max(a[lson(rt)].ssum,a[rson(rt)].ssum),a[lson(rt)].rsum+a[rson(rt)].lsum);
if(a[lson(rt)].lsum == mid-l+1) a[rt].lsum += a[rson(rt)].lsum; // 左子树左连续包含了整个左子树,则父亲的左连续扩充右子树的左连续
if(a[rson(rt)].rsum == r-mid) a[rt].rsum += a[lson(rt)].rsum;
b[rt].lsum = b[lson(rt)].lsum;
b[rt].rsum = b[rson(rt)].rsum;
b[rt].ssum = max(max(b[lson(rt)].ssum,b[rson(rt)].ssum),b[lson(rt)].rsum+b[rson(rt)].lsum);
if(b[lson(rt)].lsum == mid-l+1) b[rt].lsum += b[rson(rt)].lsum;
if(b[rson(rt)].rsum == r-mid) b[rt].rsum += b[lson(rt)].rsum;
}
void push_down(int rt,int l,int r){
int mid = (l+r)>>1;
if(a[rt].ssum == r-l+1){ // 父亲被覆盖 ,子区间也被覆盖
a[lson(rt)].lsum = a[lson(rt)].rsum = a[lson(rt)].ssum = mid-l+1;
a[rson(rt)].lsum = a[rson(rt)].rsum = a[rson(rt)].ssum = r-mid;
}else if(a[rt].ssum == 0){ // 父亲被情空,子区间清空
a[lson(rt)].lsum = a[lson(rt)].rsum = a[lson(rt)].ssum = 0;
a[rson(rt)].lsum = a[rson(rt)].rsum = a[rson(rt)].ssum = 0;
}
if(b[rt].ssum == r-l+1){
b[lson(rt)].lsum = b[lson(rt)].rsum = b[lson(rt)].ssum = mid-l+1;
b[rson(rt)].lsum = b[rson(rt)].rsum = b[rson(rt)].ssum = r-mid;
}else if(b[rt].ssum == 0){
b[lson(rt)].lsum = b[lson(rt)].rsum = b[lson(rt)].ssum = 0;
b[rson(rt)].lsum = b[rson(rt)].rsum = b[rson(rt)].ssum = 0;
}
}
void build(int r,int le,int re){
a[r].lsum = b[r].lsum = (re-le+1);
a[r].rsum = b[r].rsum = (re-le+1);
a[r].ssum = b[r].ssum = (re-le+1);
a[r].l = le,a[r].r = re;
b[r].l = le,b[r].r = re;
if(le==re) return ;
int mid = (le+re)>>1;
build(lson(r),le,mid);
build(rson(r),mid+1,re);
}
void update(int op,int l,int r,int rt){
if(a[rt].l>=l && a[rt].r <=r){
if(op==1){ // ds更新自己
a[rt].lsum = a[rt].rsum = a[rt].ssum = 0;
}else if(op==0){ // ns更新两棵树
a[rt].lsum = a[rt].rsum = a[rt].ssum = 0;
b[rt].lsum = b[rt].rsum = b[rt].ssum = 0;
}else{ // 两棵树清空
a[rt].lsum = a[rt].rsum = a[rt].ssum = a[rt].r-a[rt].l +1;
b[rt].lsum = b[rt].rsum = b[rt].ssum = b[rt].r-b[rt].l +1;
}
return ;
}
int mid = (a[rt].l + a[rt].r)>>1;
push_down(rt,a[rt].l,a[rt].r); // 下方标记
if(l<=mid) update(op,l,r,lson(rt));
if(r>mid) update(op,l,r,rson(rt));
push_up(rt,a[rt].l,a[rt].r); // 上提标记
}
int query(int op,int rt,int len){
if(a[rt].l==a[rt].r) return a[rt].l;
push_down(rt,a[rt].l,a[rt].r);
int mid = (a[rt].l + a[rt].r) >> 1;
if(op){ // ds
if(a[lson(rt)].ssum>=len)
return query(op,lson(rt),len);
else if(a[lson(rt)].rsum + a[rson(rt)].lsum >=len) // 左子树的右区间加右子树的左区间满足
return mid-a[lson(rt)].rsum +1; // 起点一定在左子树
else
return query(op,rson(rt),len);
}else{ // ns
if(b[lson(rt)].ssum>= len)
return query(op,lson(rt),len);
else if(b[lson(rt)].rsum + b[rson(rt)].lsum >=len)
return mid-b[lson(rt)].rsum +1;
else
return query(op,rson(rt),len);
}
}
char op[20];
void solve(int cas){
printf("Case %d:
",cas);
scanf("%d%d",&n,&m);
build(1,1,n);
int l,r;
FOR(i,1,m){
scanf("%s%d",op,&l);
if(op[0]=='D'){
if(a[1].ssum>=l){
int pos = query(1,1,l);
printf("%d,let's fly
",pos);
update(1,pos,pos+l-1,1);
}else{
puts("fly with yourself");
}
}else if(op[0]=='N'){
if(a[1].ssum>=l){
int pos = query(1,1,l);
printf("%d,don't put my gezi
",pos);
update(0,pos,pos+l-1,1);
}else if(b[1].ssum>=l){
int pos = query(0,1,l);
printf("%d,don't put my gezi
",pos);
update(0,pos,pos+l-1,1);
}else{
puts("wait for me");
}
}else{
scanf("%d",&r);
update(2,l,r,1);
printf("I am the hope of chinese chengxuyuan!!
");
}
}
}
int main(){
int t;
scanf("%d",&t);
for(int i=1;i<=t;++i){
solve(i);
}
return 0;
}