POJ3667[线段树、最大连续区间]
线段树暂时最后一题了吧,线段树果然可以做的很多很多,和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 <iostream> #include <cstdio> #include <cstring> 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]<b) //利用根结点判断是否有大于b的 printf("0\n"); else { int pos=query(b,1,1,n); printf("%d\n",pos); update(pos,pos+b-1,1,1,1,n); } } else { scanf("%d%d",&b,&c); update(b,b+c-1,0,1,1,n); } } } return 0; }
补充:软件开发 , C++ ,