[线段树 || (STL)set ] 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：
6
A 10 15
A 17 19
A 12 17
A 90 99
A 11 12
B
输出样例#1：
0
0
2
0
1
2
说明
N< = 200000

1< = Start End < = 100000

线段树解法

把不同任务当作颜色看待
线段树维护这区间是上面颜色管理同时我们认为这一区间超过一种颜色用 -1 标记 0 表示没有被覆盖大于0表示这一区间有第几个出现的任务颜色管理

在pushup 时有

if (tree[rt<<1] == tree[rt<<1|1]) tree[rt] = tree[rt<<1];
else if (!tree[rt<<1] || !tree[rt<<1|1]) tree[rt] = tree[rt<<1] + tree[rt<<1|1];// 有个子树是0的话直接拿另一个标记
else tree[rt] = -1; // 区间颜色不同时 -1

所以对于A操作，我们只需要在线段树上查询询问的区间[x,y]，并在查询的时候在全局开数组，记录一下有哪几个颜色（记得处理过的颜色标记一下，因为颜色只会出现一次，不需要也不能重复删除）。
会重复删也是因为lazy 0 是无色都是 0的时候补下推导致一些区间地下没有更新所以vis去个重防止减多

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, N = 1e5;

int x[maxn], y[maxn];
int que[maxn], tail,cnt;
bool vis[maxn];
int n, sum = 0;

int tree[maxn<<2], lazy[maxn<<2];

void pushup(int rt) {
    if (tree[rt<<1] == tree[rt<<1|1]) tree[rt] = tree[rt<<1];
    else if (!tree[rt<<1] || !tree[rt<<1|1]) tree[rt] = tree[rt<<1] + tree[rt<<1|1];
    else tree[rt] = -1;
}

void pushdown(int rt) {
    if (lazy[rt]) {
        tree[rt<<1] = tree[rt<<1|1] = lazy[rt];
        lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
        lazy[rt] = 0;
    }
}

void query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R && (~tree[rt])) { 
        if(tree[rt]) que[++tail] = tree[rt];
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(L<=mid) query(L,R,l,mid,rt<<1);
    if(mid<R) query(L,R,mid+1,r,rt<<1|1);
    pushup(rt);
}

void update(int L, int R, int l, int r, int rt, int k) {
    if (L <= l && r<= R) {
        tree[rt] = lazy[rt] = k;
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(L<=mid) update(L,R,l,mid,rt<<1,k);
    if(mid<R) update(L,R,mid+1,r,rt<<1|1,k);
    pushup(rt);
}


signed main() {
    cin>>n;
    string cmd;
    for (int i = 1; i <= n; i++) {
        cin>>cmd;
        if (cmd[0] == 'A') {
            cin>>x[i]>>y[i];
            tail = 0;
            query(x[i], y[i], 1, N, 1);
            cnt = 0;
            for (int j = 1; j <= tail; j++)
                if (!vis[que[j]]) { 
                    int s = x[que[j]], t = y[que[j]];
                    update(s,t,1,N,1,0);
                    vis[que[j]] = true;
                    cnt++;
                }
            update(x[i],y[i],1,N,1,i);
            cout<<cnt<<endl;
            sum = sum - cnt + 1;
        }
        else
            cout<<sum<<endl;
    }
    return 0;
}

orz stl解法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, N = 1e5;

struct node{
    int l,r;
    bool operator < (const node &x) const{
        return r<x.l;
    }
};

int n;
set<node> s;

int main(){
    cin>>n;
    while(n--){
        string op;
        cin>>op;
        if(op=="A"){
           	int l,r,ans=0;
           	cin>>l>>r;
            node x=(node){l,r};
            set<node>::iterator i=s.find(x);
            while(i!=s.end()){
                ans++;
                s.erase(i);
                i=s.find(x);
            }
            s.insert(x);
            cout<<ans<<endl;
        }
        else cout<<s.size()<<endl;
    }
    return 0;
}