区间合并

说一道例题：poj3667
题意: 两种操作：
1 s 查询有没有连续为s的区间有的话输出最左端的那个位置并把那个区间里的值都减了
2 a s 左端为a长度为s的房间退房 也就是a~a+s-1这个区间值都加一

考虑怎么做。。
可以给线段树里放一个lnum，rnum，num分别代表左边连续最大，右边连续最大，总的连续最大，的空房，然后up的时候当前的lnum就等于左边的lnum；当前的rnum就等于右儿子的rnum；num就等于目前的和 左儿子的 和 右儿子的 和 左儿子的右加右儿子 的左最大值；这里注意计算lnum和rnum的时候 如果左儿子里的区间是满的然后 lnum就不是左儿子的lnum了，还得加一个右儿子的lnum。然后rnum同理，这里一定不能忘了！

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 50006;
struct Node
{
   
    int l,r,lnum,rnum,num,tag;
}node[maxn<<2];
void build(int l,int r,int no)
{
   
    node[no].l=l;
    node[no].r=r;
    node[no].num=node[no].lnum=node[no].rnum=r-l+1;
    node[no].tag=0;
    if(l==r)
        return;
    int mid=l+r>>1;
    build(l,mid,no<<1);
    build(mid+1,r,no<<1|1);
}

void down(int no)
{
   
    if(node[no].tag==-1)
    {
   
        node[no<<1].num=node[no<<1].lnum=node[no<<1].rnum=0;
        node[no<<1|1].num=node[no<<1|1].lnum=node[no<<1|1].rnum=0;
    }
    else
    {
   
        node[no<<1].num=node[no<<1].lnum=node[no<<1].rnum=node[no<<1].r-node[no<<1].l+1;
        node[no<<1|1].num=node[no<<1|1].lnum=node[no<<1|1].rnum=node[no<<1|1].r-node[no<<1|1].l+1;
    }
    node[no<<1].tag=node[no<<1|1].tag=node[no].tag;
    node[no].tag=0;
}
void up(int no)
{
   
    node[no].lnum=node[no<<1].lnum;
    node[no].rnum=node[no<<1|1].rnum;
    if(node[no<<1].lnum==node[no<<1].r-node[no<<1].l+1)
    {
   
        node[no].lnum+=node[no<<1|1].lnum;
    }
    if(node[no<<1|1].rnum==node[no<<1|1].r-node[no<<1|1].l+1)
    {
   
        node[no].rnum+=node[no<<1].rnum;
    }
    node[no].num=max(node[no<<1].num,node[no<<1|1].num);
    node[no].num=max(node[no<<1].rnum+node[no<<1|1].lnum,node[no].num);
    node[no].num=max(node[no].lnum,node[no].num);
    node[no].num=max(node[no].rnum,node[no].num);
}

void update(int l,int r,int pos,int no)
{
   
    if(node[no].l>r||node[no].r<l)
        return;
    if(node[no].l>=l&&node[no].r<=r)
    {
   
        if(pos==-1)
            node[no].num=node[no].lnum=node[no].rnum=0;
        else
        {
   
            node[no].num=node[no].lnum=node[no].rnum=node[no].r-node[no].l+1;
        }
        node[no].tag=pos;
        return;
    }
    if(node[no].tag!=0)
        down(no);
    update(l,r,pos,no<<1);
    update(l,r,pos,no<<1|1);
    up(no);
}
int query(int sum,int no)
{
   
    if(node[no].l==node[no].r)
        return node[no].l;
    if(node[no].tag!=0)
        down(no);
    if(node[no<<1].num>=sum)
        return query(sum,no<<1);
    if(node[no<<1].rnum+node[no<<1|1].lnum>=sum)
        return node[no<<1].r-node[no<<1].rnum+1;
    return query(sum,no<<1|1);
}
int main()
{
   
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--)
    {
   
        int f;
        scanf("%d",&f);
        if(f==1)
        {
   
            int x;
            scanf("%d",&x);
            if(node[1].num>=x)
            {
   
                int s=query(x,1);
                update(s,s+x-1,-1,1);
                printf("%d\n",s);
            }
            else
                printf("0\n");

        }
        else
        {
   
            int x,y;
            scanf("%d%d",&x,&y);
            update(x,x+y-1,1,1);
        }
    }
}

菜逼李 在线敲代码