HDU 4553 约会安排
线段树区间合并+标记优先级
题目描述：小明需要安排和基友开黑和和女神约会的时间。这两个时间总是一段连续的时间，小明总是会找最早的时间来开始这些事。当有基友找他开黑的时候，他会先在时间表里找最早的连续时间，如果有，就开黑，没有就不开黑。当有女神和他约会，他先在时间表里找最早的连续时间，如果有就约会，没有他会先不考虑和基友开黑，先和女神约会，如果有时间就约会。
解题分析：POJ 3667的加强版。因为涉及到基友和女神，那线段树里就需要维护两种连续区间，分别为女神的和***丝的，区间维护三个，左边最大连续区间，右边最大连续区间，和总的最大连续区间。下推标记有三个：学习，***丝，女神。最容易错的地方是下推标记。当标记学习的时候，***丝和女神标记应当还原，当标记女神的时候，***丝标记也应当标记上（因为更新女神所占用的时间的时候，其实***丝的时间也需要更新）.注意pushdown的编写，先处理学习，再处理女神和***丝.
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100000 + 10;
struct Node
{
int l,r;
int n,d,s;//下推标记，女神，***丝，学习。处理的优先级是学习 > 女神 > ***丝。
int nsum,nls,nrs;//女神
int dsum,dls,drs;//***丝
} P[maxn << 2];
int n,m;
void build(int l,int r,int pos)
{
P[pos].l = l;
P[pos].r = r;
P[pos].n = P[pos].d = P[pos].s = -1;
P[pos].nsum = P[pos].nls = P[pos].nrs = r - l + 1;
P[pos].dsum = P[pos].dls = P[pos].drs = r - l + 1;
if(l == r) return ;
int mid = (l + r) / 2;
build(l,mid,pos << 1);
build(mid + 1, r , pos << 1 | 1);
}
void pushup(int pos)
{
P[pos].dls = P[pos << 1].dls;
P[pos].drs = P[pos << 1 | 1].drs;
if(P[pos << 1].dls == (P[pos << 1].r - P[pos << 1].l + 1) ) P[pos].dls += P[pos << 1 | 1].dls;
if(P[pos << 1 | 1].drs == (P[pos << 1 | 1].r - P[pos << 1 | 1].l + 1) ) P[pos].drs += P[pos << 1].drs;
P[pos].dsum = max(P[pos].dls,P[pos].drs);
P[pos].dsum = max( max(P[pos << 1].dsum , P[pos << 1 | 1].dsum),max(P[pos << 1].drs + P[pos << 1 | 1].dls,P[pos].dsum) );
P[pos].nls = P[pos << 1].nls;
P[pos].nrs = P[pos << 1 | 1].nrs;
if(P[pos << 1].nls == (P[pos << 1].r - P[pos << 1].l + 1) ) P[pos].nls += P[pos << 1 | 1].nls;
if(P[pos << 1 | 1].nrs == (P[pos << 1 | 1].r - P[pos << 1 | 1].l + 1) ) P[pos].nrs += P[pos << 1].nrs;
P[pos].nsum = max(P[pos].nls,P[pos].nrs);
P[pos].nsum = max( max(P[pos << 1].nsum , P[pos << 1 | 1].nsum),max(P[pos << 1].nrs + P[pos << 1 | 1].nls, P[pos].nsum) );
}
//尽管是先处理学习，再处理女神和***丝，但注意到，下面第一个if()语句处理完，还会执行下面的if()语句，换言之，下面的if()语句可能会覆盖上面的
void pushdown(int pos)
{
if(P[pos].s == 1)
{
P[pos << 1].dls = P[pos << 1].drs = P[pos << 1].dsum = (P[pos << 1]. r - P[pos << 1].l + 1);
P[pos << 1 | 1].dls = P[pos << 1 | 1].drs = P[pos << 1 | 1].dsum = (P[pos << 1 | 1].r - P[pos << 1 | 1].l + 1);
P[pos << 1].nls = P[pos << 1].nrs = P[pos << 1].nsum = (P[pos << 1]. r - P[pos << 1].l + 1);
P[pos << 1 | 1].nls = P[pos << 1 | 1].nrs = P[pos << 1 | 1].nsum = (P[pos << 1 | 1]. r - P[pos << 1 | 1].l + 1);
P[pos << 1].s = P[pos << 1 | 1].s = P[pos].s;// = 1
P[pos << 1].n = P[pos << 1 | 1].n = -1;
P[pos << 1].d = P[pos << 1 | 1].d = -1;
P[pos].s = -1;
//return ;
}
if(P[pos].n == 1)
{
P[pos << 1].nls = P[pos << 1].nrs = P[pos << 1].nsum = P[pos << 1 | 1].nls = P[pos << 1 | 1].nrs = P[pos << 1 | 1].nsum = 0;
P[pos << 1].n = P[pos << 1 | 1].n = P[pos].n;// = 1
P[pos].n = -1;
}
if(P[pos].d == 1)
{
P[pos << 1].dls = P[pos << 1].drs = P[pos << 1].dsum = P[pos << 1 | 1].dls = P[pos << 1 | 1].drs = P[pos << 1 | 1].dsum = 0;
P[pos << 1].d = P[pos << 1 | 1].d = P[pos].d;
P[pos].d = -1;
}
}
void update(int L,int R,int pos,int flag)
{
if(L <= P[pos].l && P[pos].r <= R)
{
if(flag == 1)//女神
{
P[pos].nls = P[pos].nrs = P[pos].nsum = P[pos].dls = P[pos].drs = P[pos].dsum = 0;
P[pos].n = 1;
P[pos].d = 1;
}
else
{
P[pos].dls = P[pos].drs = P[pos].dsum = 0;
P[pos].d = 1;
}
return ;
}
pushdown(pos);
int mid = (P[pos].l + P[pos].r) / 2;
if(L <= mid) update(L,R,pos << 1,flag);
if(mid < R) update(L,R,pos << 1 | 1,flag);
pushup(pos);
}
int queryD(int pos,int k)
{
if(P[pos].l == P[pos].r) return P[pos].l;
pushdown(pos);
if(P[pos << 1].dsum >= k) return queryD(pos << 1,k);
else if(P[pos << 1].drs + P[pos << 1 | 1].dls >= k)
{
return P[pos << 1].r - P[pos << 1].drs + 1;
}
else return queryD(pos << 1 | 1,k);
}
int queryN(int pos,int k)
{
if(P[pos]. l == P[pos].r) return P[pos].l;
pushdown(pos);
if(P[pos << 1].nsum >= k) return queryN(pos << 1,k);
else if(P[pos << 1].nrs + P[pos << 1 | 1].nls >= k)
{
return P[pos << 1].r - P[pos << 1].nrs + 1;
}
else return queryN(pos << 1 | 1 , k);
}
void clean(int L,int R,int pos)
{
if(L <= P[pos].l && P[pos].r <= R)
{
P[pos].dls = P[pos].drs = P[pos].dsum = P[pos].nls = P[pos].nrs = P[pos].nsum = (P[pos].r - P[pos].l + 1 );
P[pos].s = 1;
P[pos].n = -1;
P[pos].d = -1;
return ;
}
pushdown(pos);
int mid = ( P[pos].l + P[pos].r ) / 2;
if(L <= mid) clean(L,R,pos << 1);
if(mid < R) clean(L,R,pos << 1 | 1);
pushup(pos);
}
int main()
{
int tt;
int kase = 0;
scanf("%d",&tt);
while(tt--)
{
scanf("%d %d",&n,&m);
build(1,n,1);
printf("Case %d:\n",++kase);
while(m--)
{
int t,x,y;
char str[10];
scanf("%s",str);
if(str[0] == 'D')
{
scanf("%d",&t);
if(P[1].dsum < t) printf("fly with yourself\n");
else
{
int ans = queryD(1,t);
printf("%d,let's fly\n",ans);
update(ans,ans + t - 1,1,2);
}
}
else if(str[0] == 'N')
{
scanf("%d",&t);
if(P[1].nsum < t) printf("wait for me\n");
else
{
if(P[1].dsum >= t)
{
int ans = queryD(1,t);
printf("%d,don't put my gezi\n",ans);
update(ans,ans + t - 1,1,1);
}
else if(P[1].nsum >= t)
{
int ans = queryN(1,t);
printf("%d,don't put my gezi\n",ans);
update(ans,ans + t - 1,1,1);
}
}
}
else
{
scanf("%d %d",&x,&y);
clean(x,y,1);
printf("I am the hope of chinese chengxuyuan!!\n");
}
}
}
return 0;
}
细节很多，容易写挫，关键是理清逻辑上的关系，标记一多我就理不清，还是得多思考，多练习啊.
查看5道真题和解析