跳转至

251111 模拟赛

T1

直接单调栈用脚就能做。也可以正难则反钦定每个点为最靠上，其次最靠左的障碍物，即可省去两维限制。也可以不用单调栈。

T2

通过 观察小样例 和 合理猜测 可以得到 做法。

对于一个局面，无论交互库选择哪个球，最终的答案应该都是一样的，否则可以调整为更优的情况。通过手模 \(n\le 3\) 猜测答案（归一化之后）等于多重集排列，发现满足递推关系式。

T3

这里讲讲如何单 \(\log\) 求排列的三维偏序对的数量。按 \((a,b),~(b,c),~(a,c)\) 各跑一遍二维偏序，记总和为 \(M\)。发现每个无序对 \((i,j)\) 要么统计 \(1\) 遍（恰好 \(2\) 维偏序），要么统计 \(3\) 遍（恰好 \(3\) 维偏序）。因此答案为 \(\frac{1}{2}\big(M-n(n-1)\big)\)。

T4

求 \(n\) 个矩形的并的连通块数量。称两个矩形直接连通当且仅当它们公共面积 \(>0\)。

考虑从左向右扫描线，问题转化为插入和删除线段两种操作。插入线段时，把线段树上的节点分为两类：完全包含于当前线段的称为 \(①\)，和当前线段有交但不包含的节点称为 \(②\)。对每个节点分别维护两个 \(col\to cnt\) 的哈希表，表示分别作为 \(①,②\) 两类区间时对应线段的数量。只需要把和当前线段 \([l,r]\) 有交的区间的 \(①\) 哈希表查一下，再把完全包含于当前区间的 \(②\) 哈希表查一下，把所有颜色都启发式合并，即可做到 \(O(n\log^2 n)\)。

注意 std::vector 在 push_back 之后可能会导致迭代器失效。

代码 
  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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 10;
const int m = 1e5 + 5;

struct Op {
    int x, y1, y2, id;
    inline bool operator<(const Op &b) const {
        if(x != b.x) return x < b.x;
        return id < b.id;
    }
};

struct Range {
    int l, r;
};

int n, ans;
int col[N], exist[N];
vector<Op> op;
Range a[N];

vector<int> pos[N];

struct hash_table {
    static const int LOGN = 18;
    static const int MOD = 10000079;
    struct Node {
        ull key; int val, next;
    } pool[4 * N * LOGN];
    int nn, head[MOD];
    inline hash_table() { nn = 0; for(int i = 0; i < MOD; i++) head[i] = 0; }
    inline bool add(ull key, int v = 1) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) {
                if(pool[i].val) return pool[i].val += v, false;
                else return pool[i].val += v, true;
            }
        }
        pool[++nn] = {key, v, head[key % MOD]};
        head[key % MOD] = nn;
        return true;
    }
    inline void erase(ull key) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) return pool[i].val--, void();
        }
        assert(false);
    }
    inline void clear(ull key) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) return pool[i].val = 0, void();
        }
        // assert(false);
    }
    inline int query(ull key) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) return pool[i].val;
        }
        return 0;
    }
} st1, st2;

namespace SegT {
    struct Node {
        ull p;
        vector<int> buf1, buf2;
        inline int cnt1(int c) { return st1.query(p | c); }
        inline void ins1(int c) { if(st1.add(p | c)) buf1.push_back(c); }
        inline void era1(int c) { st1.erase(p | c); }
        inline int cnt2(int c) { return st2.query(p | c); }
        inline void ins2(int c) { if(st2.add(p | c)) buf2.push_back(c); }
        inline void era2(int c) { st2.erase(p | c); }
        inline void merge1(int x, int y) {
            if(st1.add(p | x, st1.query(p | y))) buf1.push_back(x);
            st1.clear(p | y);
        }
        inline void merge2(int x, int y) {
            if(st2.add(p | x, st2.query(p | y))) buf2.push_back(x);
            st2.clear(p | y);
        }
    } tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void build(int p, int l, int r) {
        tr[p].p = (ull)p << 32;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
    }
    void merge(int p, int l, int r, int ql, int qr, int x, int y) {
        if(ql <= l && r <= qr) return tr[p].merge2(x, y);
        tr[p].merge1(x, y);
        int mid = (l + r) >> 1;
        if(ql <= mid) merge(lc(p), l, mid, ql, qr, x, y);
        if(mid < qr) merge(rc(p), mid + 1, r, ql, qr, x, y);
    }
    void merge(int x, int y) {
        if(x == y || !exist[x] || !exist[y]) return;
        if(pos[x].size() < pos[y].size()) swap(x, y);
        for(int i : pos[y]) {
            merge(1, 1, m, a[i].l, a[i].r, x, y);
            col[i] = x;
            pos[x].push_back(i);
        }
        vector<int>().swap(pos[y]);
        exist[y] = 0;
    }
    void insert(int p, int l, int r, int ql, int qr, int x) {
        if(ql <= l && r <= qr) return tr[p].ins2(x);
        tr[p].ins1(x);
        int mid = (l + r) >> 1;
        if(ql <= mid) insert(lc(p), l, mid, ql, qr, x);
        if(mid < qr) insert(rc(p), mid + 1, r, ql, qr, x);
    }
    void assign(int p, int l, int r, int ql, int qr, int x) {
        if(ql <= l && r <= qr) {
            for(int ii = 0; ii < tr[p].buf1.size(); ii++)
                if(tr[p].cnt1(tr[p].buf1[ii])) merge(col[x], tr[p].buf1[ii]);
            for(int ii = 0; ii < tr[p].buf2.size(); ii++)
                if(tr[p].cnt2(tr[p].buf2[ii])) merge(col[x], tr[p].buf2[ii]);
            tr[p].buf1.clear(); tr[p].buf1.push_back(col[x]);
            tr[p].buf2.clear(); tr[p].buf2.push_back(col[x]);
            return;
        }
        for(int ii = 0; ii < tr[p].buf2.size(); ii++)
            if(tr[p].cnt2(tr[p].buf2[ii])) merge(col[x], tr[p].buf2[ii]);
        tr[p].buf2.clear(); tr[p].buf2.push_back(col[x]);
        int mid = (l + r) >> 1;
        if(ql <= mid) assign(lc(p), l, mid, ql, qr, x);
        if(mid < qr) assign(rc(p), mid + 1, r, ql, qr, x);
    }
    void erase(int p, int l, int r, int ql, int qr, int x) {
        if(ql <= l && r <= qr) return tr[p].era2(col[x]);
        tr[p].era1(col[x]);
        int mid = (l + r) >> 1;
        if(ql <= mid) erase(lc(p), l, mid, ql, qr, x);
        if(mid < qr) erase(rc(p), mid + 1, r, ql, qr, x);
    }
}

void insert(int l, int r, int id) {
    SegT::insert(1, 1, m, l, r, id);
    SegT::assign(1, 1, m, l, r, id);
}
void erase(int l, int r, int id) {
    SegT::erase(1, 1, m, l, r, id);
}

int main() {

    freopen("ding.in", "r", stdin);
    freopen("ding.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        op.push_back({x1, y1, y2, i});
        op.push_back({x2 + 1, y1, y2, -i});
        a[i] = {y1, y2};
    }

    SegT::build(1, 1, m);

    sort(op.begin(), op.end());
    for(int i = 1; i <= n; i++) {
        col[i] = i;
        pos[i].push_back(i);
        exist[i] = 1;
    }
    for(Op &o : op) {
        if(o.id > 0) insert(o.y1, o.y2, o.id);
        else erase(o.y1, o.y2, -o.id);
    }

    for(int i = 1; i <= n; i++) ans += exist[i];
    cout << ans << '\n';

    return 0;
}