[SHOI2009] 会场预约

发表于 | 分类于 >
字数统计 : 484   |   阅读时长 ≈ 2 mins.

题目

链接

[SHOI2009]会场预约

题意简述

编写一个数据结构支持 种 次操作。

  • 删除与 有交集的区间，插入并输出删除数。
  • 查询区间数。

思路

std::set

因为区间不相交，所以以 $x$ 为第一关键字排序后是单调递增的。
很明显就是找包含这个区间前驱与后继。
$std::set$ 就行，注意细节处理，主要是 $set.end()$ 很麻烦。
不得不说 $std::pair$ 实在是很方便。
还有注意相同区间。
时间复杂度： $O(nlogn)$ 。

平衡树

也是找包含这个区间前驱与后继。
不过要手打，这里因为懒就只打了 $std::set$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e6 + 10, kmax_int = 2147483647, kmod = 99999997;

#define pii std::pair<int, int>
#define mp std::make_pair
#define x first
#define y second

int n;
std::set<pii> tim;
std::set<pii>::iterator it1, it2;
std::stack<pii> stack;

int main() {
    std::cin >> n;

    REG char cmd = 0;
    REG int ax, ay, bx, by, ans;
    FOR(i,0,n)  {
        while(!isalpha(cmd = getchar()) continue;

        if(cmd == 'A')  {
            ans = 0;
            std::cin >> ax >> ay;
            
            if(tim.count(mp(ax, ay)))   {
                printf("1\n");
                continue;
            }
            
            tim.insert(mp(ax, ay));
            it1 = tim.find(mp(ax, ay));
            
            it2 = it1;
            if(it1 != tim.begin())  {
                --it2;
                for( ; ; --it2) {
                    if((*it2).y >= ax)  stack.push(mp((*it2).x, (*it2).y));
                    else    break;
                    if(it2 == tim.begin())  break;
                }
            }
            
            it2 = it1;
            if(++it1 != tim.end())  {
                ++it2;
                for( ; ; ++it2) {
                    if(it2 == tim.end())  break;
                    if((*it2).x <= ay)  stack.push(mp((*it2).x, (*it2).y));
                    else    break;
                }
            }

            while(!stack.empty())   {
                ++ans, tim.erase(tim.find(stack.top()));
                stack.pop();
            }
            printf("%d\n", ans);
        }
        else    {
            printf("%d\n", tim.size());
        }
    }
    return 0;
}

杂项

  • 这里用了 $std::pair$ 和 $std::set$ 实现， $std::pair$ 和 $std::set$ 大法好！
  • 两个都用上了，乌拉！