【bzoj2028】[SHOI2009]会场预约

2015.06.18 09:46 Thu | 26次阅读 | 旧日oi | 固定链接 | 源码

题目大意:按顺序给出一些区间,每次加入一个区间时要把所有和这个区间有交集的区间都删掉,并统计这个数目。还要求查询当前的区间个数。
题解
我就是个傻叉……人家set代码不到1000B1秒过,我写个区间合并线段树写了两个多小时3000多Btm6秒才过……
维护两颗线段树(其实可以变成一颗),一颗维护每个点所在区间的左端点和右端点,另一颗维护每段里不同区间的个数,然后再记录是否和左边连续,右边连续就行了……
贴个sb代码……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 400005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define M 100000
int n;
struct seg1
{
    int w[2];
}t1[N];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        t1[rt].w[0]=t1[rt].w[1]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    t1[rt].w[0]=t1[rt].w[1]=-1;
}
void pushdown(int rt)
{
    if(t1[rt].w[0]!=-1)
    {
        t1[rt<<1].w[0]=t1[rt<<1|1].w[0]=t1[rt].w[0];
        t1[rt].w[0]=-1;
    }
    if(t1[rt].w[1]!=-1)
    {
        t1[rt<<1].w[1]=t1[rt<<1|1].w[1]=t1[rt].w[1];
        t1[rt].w[1]=-1;
    }
}
int find(int l,int r,int rt,int x,int k)
{
    if(l==r) return t1[rt].w[k];
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid) return find(lson,x,k);
    else return find(rson,x,k);
}
void update(int l,int r,int rt,int L,int R,int x)
{
    if(L<=l&&R>=r)
    {
        if(x) t1[rt].w[0]=L,t1[rt].w[1]=R;
        else t1[rt].w[0]=0,t1[rt].w[1]=0;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt);
    if(L<=mid) update(lson,L,R,x);
    if(R>mid) update(rson,L,R,x);
}
struct node
{
    int sum,ls,rs,flag;
}t2[N],t;
node merge(node x,node y)
{
    memset(&t,0,sizeof(t));
    t.sum=x.sum+y.sum;
    t.ls=x.ls;t.rs=y.rs;
    if(x.rs&&y.ls&&x.rs==y.ls) t.sum--;
    return t;
}
void pushdown2(int rt)
{
    if(t2[rt].flag==-1)
    {
        t2[rt<<1].flag=t2[rt<<1|1].flag=-1;
        t2[rt<<1].sum=t2[rt<<1|1].sum=0;
        t2[rt<<1].ls=t2[rt<<1|1].ls=0;
        t2[rt<<1].rs=t2[rt<<1|1].rs=0;
    }
    else if(t2[rt].flag>0)
    {
        t2[rt<<1].flag=t2[rt<<1|1].flag=t2[rt].flag;
        t2[rt<<1].sum=t2[rt<<1|1].sum=1;
        t2[rt<<1].ls=t2[rt].ls;t2[rt<<1|1].rs=t2[rt].rs;
        t2[rt<<1].rs=t2[rt<<1|1].ls=t2[rt].flag;
    }
    t2[rt].flag=0;
    return;
}
node get_ans(int l,int r,int rt,int L,int R)
{
    if(L==l&&R==r) return t2[rt];
    int mid=(l+r)>>1;
    pushdown2(rt);
    if(R<=mid) return get_ans(lson,L,R);
    else if(L>mid) return get_ans(rson,L,R);
    else return merge(get_ans(lson,L,mid),get_ans(rson,mid+1,R));
}
void update2(int l,int r,int rt,int L,int R,int k)
{
    if(L<=l&&R>=r)
    {
        t2[rt].flag=k?k:-1;
        if(!k)
        {
            t2[rt].sum=0;
            t2[rt].ls=t2[rt].rs=0;
        }
        else
        {
            t2[rt].sum=1;
            if(L<l) t2[rt].ls=k;else t2[rt].ls=0;
            if(R>r) t2[rt].rs=k;else t2[rt].rs=0;
        }
        return;
    }
    pushdown2(rt);
    int mid=(l+r)>>1;
    if(L<=mid) update2(lson,L,R,k);
    if(R>mid) update2(rson,L,R,k);
    t2[rt]=merge(t2[rt<<1],t2[rt<<1|1]);
}
int main()
{
    cin>>n;
    build(1,M,1);
    char s[2];int x,y,tx,ty,cnt=0;
    while(n--)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            scanf("%d%d",&x,&y);
            tx=find(1,M,1,x,0);
            ty=find(1,M,1,y,1);
            if(!tx) tx=x;if(!ty) ty=y;
            update(1,M,1,tx,ty,0);
            update(1,M,1,x,y,1);
            node tmp=get_ans(1,M,1,tx,ty);
            update2(1,M,1,tx,ty,0);
            //for(int i=1;i<N;i++) printf("%d ",t2[i].flag);puts("");
            update2(1,M,1,x,y,++cnt);
            printf("%d\n",tmp.sum);
            //for(int i=1;i<N;i++) printf("%d ",t2[i].flag);puts("");
        }
        else printf("%d\n",t2[1].sum);
    }
}```