DDOSvoid's Blog

The 18th Zhejiang Provincial Collegiate Programming Contest B Restore Atlantis

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

题目描述

http://codeforces.com/gym/103055/problem/B

简要题意：给定 $n$ 个矩形 $(x_a,x_b,y_a,y_b)$ 以及 $m$ 次询问，每次询问给定 $[l,r]$，求如果不考虑编号在 $[l,r]$ 的矩形，其它矩形的并的面积

$n,q\le 10^5,0\le x,y\le 2000$

Solution

非常具有欺诈性的题目

首先注意到整个矩形一共只有 $4e6$ 个点

也就是说我们完全可以记录每个点被编号最小和编号最大的矩形覆盖，记作 $mn[i][j]$ 和 $mx[i][j]$

然后我们考虑如何求这个东西，参考扫描线求矩形覆盖的模型

我们同样考虑扫描线，我们用扫描线扫描一个矩阵的行，也就是说我们将一个从 $x_1$ 到 $x_2$ 的矩形在 $x_1$ 加入，在 $x_2+1$ 退出

同时我们考虑在线段树上维护列，每个点开两个可删除堆，维护最大和最小值

但这个时候我们要出叶子节点的历史最值，注意到线段树只有 $2000$ 所以我们在每一次扫描线移动前 $dfs$ 整棵树去维护最大和最小值即可，由于堆求堆顶的复杂度是 $O(1)$ 的，所以这一块的复杂度为 $O(C^2+n\log C)$

接下来我们对于每个询问要求这个东西 $\sum_{(i,j)} [mn[i][j]r]$ 这个东西稍微变换一下就可以用树状数组 $O(n\log c)$ 解决

总的时间复杂度为 $O(C^2+n\log C)$

话说这也算小学数据结构题?

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <tuple>
#include <queue>
#define maxn 2010
#define maxm 100010
#define lowbit(i) ((i) & (-i))
using namespace std;

const int r = 2000;
const int c = 2000;

int n, q;

struct HeapMax {
    priority_queue<int> add, del;

    inline void push(int x) { add.push(x); }

    inline void erase(int x) { del.push(x); }

    inline int top() {
        while (!del.empty() && del.top() == add.top()) del.pop(), add.pop();
        return add.top();
    }

    inline void pop() {
        while (!del.empty() && del.top() == add.top()) del.pop(), add.pop();
        add.pop();
    }

    inline bool empty() { return add.size() - del.size() == 0; }
};

struct HeapMin {
    priority_queue<int, vector<int>, greater<int>> add, del;

    inline void push(int x) { add.push(x); }

    inline void erase(int x) { del.push(x); }

    inline int top() {
        while (!del.empty() && del.top() == add.top()) del.pop(), add.pop();
        return add.top();
    }

    inline void pop() {
        while (!del.empty() && del.top() == add.top()) del.pop(), add.pop();
        add.pop();
    }

    inline bool empty() { return add.size() - del.size() == 0; }
};

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    HeapMin s;
    HeapMax t; 
} T[maxn * 4];
void build(int i, int l, int r) {
    T[i].s.push(n + 1), T[i].t.push(0);
    if (l == r) return ; int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r); 
} 

void update(int i, int l, int r, int L, int R, int v, int opt) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) {
        if (opt > 0) T[i].s.push(v), T[i].t.push(v);
        else T[i].s.erase(v), T[i].t.erase(v);
        return ; 
    }
    int m = l + r >> 1;
    update(lc, l, m, L, R, v, opt); update(rc, m + 1, r, L, R, v, opt); 
}

int mn[maxn][maxn], mx[maxn][maxn];
void query(int i, int l, int r, int s, int t, int k) {
    if (l == r) return mn[k][l] = min(T[i].s.top(), s), mx[k][l] = max(T[i].t.top(), t), void();
    int m = l + r >> 1; s = min(s, T[i].s.top()); t = max(t, T[i].t.top()); 
    query(lc, l, m, s, t, k); query(rc, m + 1, r, s, t, k); 
}

vector<tuple<int, int, int>> A[maxn], B[maxn];

int ans[maxm];
vector<int> C[maxm];
vector<pair<int, int>> D[maxm];

int Bit[maxm];
void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }

int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; ++x1; ++y1; 
        A[x1].emplace_back(y1, y2, i);
        B[x2].emplace_back(y1, y2, i);
    }
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j) mn[i][j] = n + 1, mx[i][j] = 0;
    build(1, 1, c); 
    for (int i = 1; i <= r; ++i) {
        for (auto t : A[i]) {
            int l, r, v; tie(l, r, v) = t;
            update(1, 1, c, l, r, v, 1); 
        }
        query(1, 1, c, n + 1, 0, i);
        for (auto t : B[i]) {
            int l, r, v; tie(l, r, v) = t; 
            update(1, 1, c, l, r, v, -1); 
        } 
    }
    for (int i = 1; i <= q; ++i) {
        int x, y; cin >> x >> y;
        D[y].emplace_back(x, i);
    }
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            if (mn[i][j] < n + 1 && mx[i][j] > 0)
                C[mx[i][j]].push_back(mn[i][j]);
    int sum = 0; 
    for (int i = 1; i <= n; ++i) {
        for (auto t : C[i]) ++sum, add(t, 1);
        for (auto t : D[i]) ans[t.second] = sum - get_sum(t.first - 1);
    }
    for (int i = 1; i <= q; ++i)
        cout << sum - ans[i] << "\n"; 
    return 0;
}