线段树暂时最后一题了吧，线段树果然可以做的很多很多，和DP结合起来对自己的要求更高了。
自己要做的还差很远～
这题调试了好长时间。。。
题意:1a:询问是不是有连续长度为a的空房间,有的话住进最左边
2a b:将[a,a+b-1]的房间清空
思路:记录区间中最长的空房间
线段树操作:update:区间替换query:询问满足条件的最左断点
主要难点在于
void pushup(int rt,int m)
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1]; //这几步的处理！
if(lsum[rt]==(m-m/2))
lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt]==m/2)
rsum[rt]+=rsum[rt<<1];
msum[rt]=max(rsum[rt<<1]+lsum[rt<<1|1],max(msum[rt<<1],msum[rt<<1|1]));
}
理解了就好了～
顺便自己对pushdown又错了一次，pushdown是传给子孙结点的。
#include
#include
#include
using namespace std;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
const int maxn=50005;
//经典做法 //msum最大一段连续区间 lsum,rsum从左，右边起最大连续区间
int cover[maxn<<8],msum[maxn<<8],lsum[maxn<<8],rsum[maxn<<8];
void build(int rt,int l,int r)
{
cover[rt]=-1;
msum[rt]=lsum[rt]=rsum[rt]=r-l+1;
if(l==r) return;
int m=(l+r)>>1;
build(lson);
build(rson);
}
void pushdown(int rt,int m) {
if (cover[rt] != -1) {
cover[rt<<1] = cover[rt<<1|1] = cover[rt];
msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] 0 : m - (m >> 1);
msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] 0 : (m >> 1);
cover[rt] = -1;
}
}
void pushup(int rt,int m)
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1]; //这几步的处理！
if(lsum[rt]==(m-m/2))
lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt]==m/2)
rsum[rt]+=rsum[rt<<1];
msum[rt]=max(rsum[rt<<1]+lsum[rt<<1|1],max(msum[rt<<1],msum[rt<<1|1]));
}
void update(int ql,int qr,int ch,int rt,int l,int r)
{
if(ql<=l&&qr>=r)
{
cover[rt]=ch;
if(ch==0)
msum[rt]=lsum[rt]=rsum[rt]=r-l+1;
else if(ch==1)
msum[rt]=lsum[rt]=rsum[rt]=0;
return;
}
pushdown(rt,r-l+1);
int m=(l+r)>>1;
if(ql<=m)
update(ql,qr,ch,lson);
if(qr>m)
update(ql,qr,ch,rson);
pushup(rt,r-l+1);
}
int query(int ch,int rt,int l,int r)
{
//要返回的是左坐标
if(l==r) return l;
//呵呵。。。
pushdown(rt,r-l+1);
int m=(l+r)>>1;
if(msum[rt<<1]>=ch)
return query(ch,lson);
else if((rsum[rt<<1]+lsum[rt<<1|1])>=ch)
return m-rsum[rt<<1]+1; //这一步return最为经典
else
return query(ch,rson);
}
int main()
{
int n,m,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d",&a);
if(a==1)
{
scanf("%d",&b);
if(msum[1]