hdu3667：
题意：定义两种操作，询问最大连续的空间，返回首地址；清除以及将一段区间置1。
思路：线段树，定义三个数组分别表示从左，右，中，的最大连续长度，注意向上更新时合并区间的操作。
写了一段时间，错了很多地方。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 55555
using namespace std;
int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2];
int col[maxn<<2];
void PushUp(int rt,int m)
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
if(lsum[rt]==m-(m>>1)) lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt]==(m>>1)) rsum[rt]+=rsum[rt<<1];//写错了
msum[rt]=max(max(msum[rt<<1],msum[rt<<1|1]),rsum[rt<<1]+lsum[rt<<1|1]);//写错了
}
void PushDown(int rt,int m)
{
if(col[rt]!=-1)
{
col[rt<<1]=col[rt<<1|1]=col[rt];
lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=col[rt]?0:m-(m>>1);
lsum[rt<<1|1]=rsum[rt<<1|1]=msum[rt<<1|1]=col[rt]?0:(m>>1);
col[rt]=-1;
}
}
void build(int l,int r,int rt)
{
lsum[rt]=msum[rt]=rsum[rt]=r-l+1;
col[rt]=-1;
if(l==r)
{
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
}
int query(int c,int l,int r,int rt)
{
if(l==r)
{
return l;//直到一个点为止
}
PushDown(rt,r-l+1);
int m=(l+r)>>1;
if(msum[rt<<1]>=c) return query(c,lson);
else if(rsum[rt<<1]+lsum[rt<<1|1]>=c) return m-rsum[rt<<1]+1;
else return query(c,rson);
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
lsum[rt]=rsum[rt]=msum[rt]=c?0:r-l+1;
col[rt]=c;
return ;//第二个错
}
PushDown(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m)
update(L,R,c,lson);
if(R>m)
update(L,R,c,rson);
PushUp(rt,r-l+1);
}
int main()
{
int n,m,ord,cc,p,a,b;
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=0;i<m;i++)
{
scanf("%d",&ord);
if(ord==1)
{
scanf("%d",&cc);
if(msum[1]<cc)
printf("0\n");
else
{
p=query(cc,1,n,1);
printf("%d\n",p); //第一个错
update(p,p+cc-1,1,1,n,1);//1表示覆盖
}
}
else
{
scanf("%d%d",&a,&b);
update(a,a+b-1,0,1,n,1);//0表示清除
//错误三 区间写错了
}
}
return 0;
}