DDOSvoid's Blog

2020年广西省CCPC大学生程序设计竞赛 C Low Power

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

给定一个 $1\le r,c \le 10^3$ 的矩形，这之中有 $n$ 个矩形，同时有 $m$ 个询问，每次询问去掉至多五个矩形之后有多少点仍然被至少一个矩形覆盖

$n,m\le 10^5$

Solution

我们考虑 $hash$，给每个矩形随机一个 $ull$ 范围内的值，一个格子的值为覆盖这个格子的矩形的值的异或

每次询问只需要判断有哪些点恰好被去掉的矩形覆盖

时间复杂度 $O(m\cdot 5\cdot2^5\log n)$，其中 $5$ 可以通过类似 $dfs$ 的方法去掉

实测 $map$ 比 $vector$ 要慢

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
#include <iostream>
#include <cstdio>
#include <set>
#include <random>
#include <ctime>
#include <map>
#include <algorithm>
#define maxn 1010
#define ll long long
#define cn const node
using namespace std;

int n, m, k, Nx, Ny;

default_random_engine e(19260817);

uniform_int_distribution<ll> Rand(1, 1e18);

ll get(ll l, ll r) {
    return Rand(e) % (r - l + 1) + l;
}

ll a[maxn][maxn], B[100010];

int b[maxn][maxn];

map<ll, int> ma[6];

struct node {
    ll k; int v;

    node() {}
    node(ll _k, int _v) { k = _k; v = _v; } 

    friend bool operator < (cn &u, cn &v) {
        if (u.k == v.k) return u.v < v.v; 
        return u.k < v.k;
    }
}; vector<node> V[6];
vector<node>::iterator it;

int A[5];

void work() {
    cin >> n >> m; int ans = 0;
    for (int i = 0; i < 6; ++i) ma[i].clear(), V[i].clear();
    fill(a[0], a[0] + maxn * maxn, 0);
    fill(b[0], b[0] + maxn * maxn, 0);
    for (int i = 1; i <= n; ++i) {
        int x1, y1, x2, y2; ll v; cin >> x1 >> x2 >> y1 >> y2;
        B[i] = v = get(1, 1e18);
        a[x2][y2] ^= v; a[x1 - 1][y2] ^= v;
        a[x2][y1 - 1] ^= v; a[x1 - 1][y1 - 1] ^= v;
        ++b[x2][y2]; --b[x1 - 1][y2]; --b[x2][y1 - 1]; ++b[x1 - 1][y1 - 1];
        Nx = max(Nx, x2); Ny = max(Ny, y2);
    }
    for (int i = Nx; i; --i)
        for (int j = Ny; j; --j) {
            a[i][j] ^= a[i + 1][j + 1] ^ a[i + 1][j] ^ a[i][j + 1];
            b[i][j] += -b[i + 1][j + 1] + b[i + 1][j] + b[i][j + 1];
            ans += b[i][j] >= 1;
            if (b[i][j] > 5 || !b[i][j]) continue ;
            ma[b[i][j]][a[i][j]]++;
        }
    for (int i = 0; i < 6; ++i) 
        for (auto u : ma[i]) V[i].push_back(node(u.first, u.second));
    for (int o = 1; o <= m; ++o) {
        int n; cin >> n; int sum = 0;
        for (int i = 0; i < n; ++i) cin >> A[i];
        for (int S = 1; S < (1 << n); ++S) {
            int k = 0; ll v = 0;
            for (int i = 0; i < n; ++i)
                if (S >> i & 1) ++k, v ^= B[A[i]];
            it = lower_bound(V[k].begin(), V[k].end(), node(v, 0));
            if (it != V[k].end() && it -> k == v) sum += it -> v;
        } cout << ans - sum << "\n";
    } 
}

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

    int T; cin >> T; 
    while (T--) work(); 
    return 0;
}