uva 11983(扫描线)_小蓝要给墙面上的 n 个矩形区域粉刷涂料,给出每个矩形左下角和右上角的两个坐标(x

题意：有n个矩形，给出每个矩形的左下角坐标和右上角坐标，问所有矩形重叠k次以上的面积并。
题解：因为k最大是10，直接用线段树维护重叠1到k-1次的面积并和大于等于k的面积并，pushup函数更新每个重叠次数。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#define ll long long
using namespace std;
const int N = 60005;
struct Line {
    int lx, rx, h, flag;
    Line(int a, int b, int c, int d): lx(a), rx(b), h(c), flag(d) {}
    bool operator < (const Line& a) const { return h < a.h; }
};
int n, m, flag[N << 2];
ll tree[12][N << 2];
vector<int> a;
vector<Line> line;
map<int, int> mp;

void pushup(int k, int left, int right) {
    if (flag[k] >= m) {
        tree[m][k] = tree[0][k];
        for (int i = 1; i < m; i++)
            tree[i][k] = 0;
    }
    else if (flag[k] > 0) {
        if (left + 1 == right) {
            for (int i = 1; i <= m; i++)
                tree[i][k] = 0;
            tree[flag[k]][k] = tree[0][k];
        }
        else {
            tree[m][k] = 0;
            for (int i = m - flag[k]; i <= m; i++)
                tree[m][k] += tree[i][k * 2] + tree[i][k * 2 + 1];
            for (int i = 1; i + flag[k] < m; i++)
                tree[i + flag[k]][k] = tree[i][k * 2] + tree[i][k * 2 + 1];
            tree[flag[k]][k] = tree[0][k];
            for (int i = flag[k] + 1; i <= m; i++)
                tree[flag[k]][k] -= tree[i][k];
            for (int i = 1; i < flag[k]; i++)
                tree[i][k] = 0;
        }
    }
    else {
        if (left + 1 == right) {
            for (int i = 1; i <= m; i++)
                tree[i][k] = 0;
        }
        else {
            for (int i = 1; i <= m; i++)
                tree[i][k] = tree[i][k * 2] + tree[i][k * 2 + 1];
        }
    }
}

void build(int k, int left, int right) {
    flag[k] = 0;
    tree[0][k] = a[right] - a[left];
    for (int i = 1; i <= m; i++)
        tree[i][k] = 0;
    if (left + 1 != right) {
        int mid = (left + right) / 2;
        build(k * 2, left, mid);
        build(k * 2 + 1, mid, right);
    }
}

void modify(int k, int left, int right, int l, int r, int v) {
    if (l <= left && right <= r) {
        flag[k] += v;
        pushup(k, left, right);
        return;
    }
    int mid = (left + right) / 2;
    if (l < mid)
        modify(k * 2, left, mid, l, r, v);
    if (r > mid)
        modify(k * 2 + 1, mid, right, l, r, v);
    pushup(k, left, right);
}

int main() {
    int t, cas = 1;
    scanf("%d", &t);
    while (t--) {
        a.clear(), line.clear(), mp.clear();
        scanf("%d%d", &n, &m);
        int x1, y1, x2, y2;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x2++, y2++;
            line.push_back(Line(x1, x2, y1, 1));
            line.push_back(Line(x1, x2, y2, -1));
            a.push_back(x1);
            a.push_back(x2);
        }
        sort(line.begin(), line.end());
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        int sz = a.size(), sz2 = line.size();
        for (int i = 0; i < sz; i++)
            mp[a[i]] = i;
        build(1, 0, sz - 1);
        ll res = 0;
        for (int i = 0; i < sz2; i++) {
            if (i != 0)
                res += tree[m][1] * (ll)(line[i].h - line[i - 1].h);
            modify(1, 0, sz - 1, mp[line[i].lx], mp[line[i].rx], line[i].flag);
        }
        printf("Case %d: %lld\n", cas++, res);
    }
    return 0;
}
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