P2161 [SHOI2009]会场预约（线段树：线段树上的不重复覆盖数）

题目描述

PP大厦有一间空的礼堂，可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。一般来说，如果PP大厦方面事先已经接受了一个会场预约，例如从10日到15日，就不会在接受与之相冲突的预约，例如从12日到17日。不过，有时出于经济利益，PP大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。于是，礼堂管理员QQ的笔记本上笔记本上经常记录着这样的信息：本题中为方便起见，所有的日期都用一个整数表示。例如，如果一个为期10天的会议从“90日”开始到“99日”，那么下一个会议最早只能在“100日”开始。最近，这个业务的工作量与日俱增，礼堂的管理员QQ希望参加SHTSC的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作： A操作：有一个新的预约是从“start日”到“end日”，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便QQ与自己的记录相校对。 B操作：请你的系统返回当前的仍然有效的预约的总数。

输入输出格式

输入格式：

输入文件的第一行是一个整数n，表示你的系统将接受的操作总数。接下去n行每行表示一个操作。每一行的格式为下面两者之一： “A start end”表示一个A操作； “B”表示一个B操作。

输出格式：

输出文件有n行，每行一次对应一个输入。表示你的系统对于该操作的返回值。

输入输出样例

输入样例#1

输出样例#1：

说明

N< = 200000

1< = Start End < = 100000

进入正题

先把题目看成一个仅实现区间修改的线段树，用tagtag数组打打标记即可

为了方便理解，以下把预约序号看成颜色

A操作的真实目的：查询一个区间中有多少种颜色，然后清空数列中所有在该区间中出现的颜色，最后把这个区间修改成另一种颜色（先别急着看B操作qwq）

简而言之就是查询->清空->修改

对于查询操作，我们可以引入findfind函数和samesame数组。findfind函数的职能是遍历给定区间。当same[o]==1same[o]==1时，该区间内只有一种颜色，这时就可以得知该区间的颜色了；否则继续向下遍历。

对于清空操作：其实不用真的清空，只需要引入一个deldel数组，存储该颜色是否已被删除即可

对于修改，不在话下

对于B操作.....，用一个ansans储存还剩几种颜色未被删除，

应该在线离线都支持，不过离线的话可以用st,edst,ed存线段树的左右端点，建的树小（当然在线的话直接开到最大对吧）

复杂度大概O(nlogn)O(nlogn)吧

#include<bits/stdc++.h>

using namespace std ;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

const int maxn = ;

int ans,era,v,n,st=0x3f3f3f3f,en=-0x3f3f3f3f;

bool same [maxn],del[maxn];

int tag[maxn];

struct no

{

    int l,r;

    char op[];

}a[maxn];

void build(int l , int r , int rt)

{

    same[rt]=;tag[rt]=;//记得初始化：刚开始的树无修改标记且整棵树都只有一个颜色（无色==0）

    if(l==r) return ;

    int mid=(l+r)>>;

    build(lson);

    build(rson);

}

void find(int l , int r , int rt)

{

    if(same[rt]==)

    {

        if(!del[tag[rt]] && tag[rt])//有颜色，这个颜色没有被桑过了拉

        {

            --ans;

            ++era;//用ans记录还剩几种颜色，era记录这次删除了几种颜色（注意判无色

        }

        del[tag[rt]]=;//删除

        tag[rt]=v;//修改

        return ;

    }

    int mid=(l+r)>>;

    find(lson);

    find(rson);

    tag[rt]=v;

    same[rt]=;//这个区间都是一样的颜色

}

void pushdown(int l , int r , int rt)///标记下传

{

    same[rt]=;//可以下传肯定这个区间不是同色

    if(!tag[rt])

    return ;

    tag[rt<<]=tag[rt<<|]=tag[rt];

    tag[rt]=;

}

void update(int L , int R , int l , int r , int rt)

{

    if(L<=l&&r<=R)

    {

        find(l,r,rt);//加入一个find函数对所求区间进行更深一层的遍历

        return ;

    }

    pushdown(l,r,rt);

    int mid=(l+r)>>;

    if(L<=mid)

    update(L,R,lson);

    if(R>mid)

    update(L,R,rson);

}

int main( )

{

    scanf("%d",&n);

    for(int i= ; i<=n ; i++)

    {

        scanf("%s",a[i].op);

        if(a[i].op[]=='B')

        continue;

        scanf("%d%d",&a[i].l,&a[i].r);

        st=min(st,a[i].l);

        en=max(en,a[i].r);

    }

    build(st,en,);

    int cnt =  ;///当前颜色的标号

    for(int i= ; i<=n ; i++)

    {

        if(a[i].op[]=='A')

        {

            ++ans;

            v=++cnt ; era=;

            update(a[i].l,a[i].r,st,en,);

            printf("%d\n",era);

        }else

        printf("%d\n",ans);

    }

    return ;

}

预约