yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P4632 New Home 题解

发表于 更新于 分类于

P4632 New Home 题解

题面

题目链接

解法

把询问离线下来，考虑3种操作：新开一家商店，关掉一家商店，查询一个点的不方便指数。

先考虑查询。显然具有二分性，考虑判断一个区间 $[l,r]$ 是否包含了所有的颜色。这种区间统计颜色的题目有一个套路的解法，即对于一个点$i$，保存 $prei$ 表示 $i$ 的上一个相同颜色出现的位置，区间 $[l,r]$ 的答案即为 $\sum\limits{i=l}^{r}{(pre_i \lt l)}$ 。

但是这样不太便于维护，于是思考到$pre$数组的另一个性质：若$\min\limits_{i=r+1}^{n}{pre_i} \lt l$，则说明必有一种颜色没有出现在$[l,r]$中。而我们二分+判断并不需要统计颜色的个数，而是只需要统计是否为k个。

于是就很容易维护这个$pre$数组并统计答案：将$pre$放在最小值线段树上即可。注意如果某个颜色没有出现在$[r+1,n]$的话会少被考虑到，所以在最左边和最右边各开一个大节点，作为所有颜色公用。

但是这道题有个很恶心的地方，在于每个点可能有多个不同颜色的商店。所以一种做法为在线段树的每个叶子节点开一个set暴力维护。

最后对于修改操作也只需要对每个颜色暴力维护一个set，找到前驱和后继并在线段树上修改即可。

时间复杂度$O(n\log^3{n})$（跑得飞快）

AC代码

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
/**
 * @file:           P4632.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P4632
*/
// #pragma GCC optimize ("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 3e5 + 10;
const int INFL = 0x3f3f3f3f3f3f3f3f;
using pii = pair<int, int>;
struct node {
    int t, p, c, id;
    bool operator<(const node &o) const {
        return t < o.t;
    }
};
struct query {
    int t, p, id;
    bool operator<(const query &o) const {
        return t < o.t;
    }
};
#define li (i << 1)
#define ri (i << 1) | 1
#define lson li, l, mid
#define rson ri, mid + 1, r
struct segment_tree {
    int mn[MAXN * 12];
    set<pii> st[MAXN * 3];
    void pushup(int i) {
        mn[i] = min(mn[li], mn[ri]);
    }
    void build(int i, int l, int r) {
        mn[i] = INFL;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(lson), build(rson);
    }
    void insert(int i, int l, int r, int q, int c, int p) {
        if (l == r) {
            st[l].insert({p, c});
            mn[i] = st[l].size() ? st[l].begin()->first : INFL;
            return;
        }
        int mid = (l + r) >> 1;
        if (q <= mid)
            insert(lson, q, c, p);
        else
            insert(rson, q, c, p);
        pushup(i);
    }
    void erase(int i, int l, int r, int q, int c, int p) {
        if (l == r) {
            st[l].erase({p, c});
            mn[i] = st[l].size() ? st[l].begin()->first : INFL;
            return;
        }
        int mid = (l + r) >> 1;
        if (q <= mid)
            erase(lson, q, c, p);
        else
            erase(rson, q, c, p);
        pushup(i);
    }
    int query(int i, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return mn[i];
        int mid = (l + r) >> 1, ret = INFL;
        if (ql <= mid)
            ret = min(ret, query(lson, ql, qr));
        if (qr > mid)
            ret = min(ret, query(rson, ql, qr));
        return ret;
    }
};
int n, k, q, sig, len;
int pos[MAXN * 3], answ[MAXN];
node bd[MAXN * 2];
query qr[MAXN];
multiset<int> col[MAXN];
segment_tree tr;
void insert(node x) {
    if (x.id > 0) {
        col[x.c].insert(x.p);
        if (col[x.c].count(x.p) == 1) {
            auto pre = prev(col[x.c].lower_bound(x.p));
            auto nxt = col[x.c].upper_bound(x.p);
            tr.erase(1, 1, sig, *nxt, x.c, *pre);
            tr.insert(1, 1, sig, *nxt, x.c, x.p);
            tr.insert(1, 1, sig, x.p, x.c, *pre);            
        }
    } else {
        col[x.c].erase(col[x.c].find(x.p));
        if (col[x.c].count(x.p) == 0) {
            auto pre = prev(col[x.c].lower_bound(x.p));
            auto nxt = col[x.c].upper_bound(x.p);
            tr.erase(1, 1, sig, *nxt, x.c, x.p);
            tr.insert(1, 1, sig, *nxt, x.c, *pre);
            tr.erase(1, 1, sig, x.p, x.c, *pre);            
        }
    }
}
bool check(int ps, int ln) {
    int u = lower_bound(pos + 1, pos + sig + 1, ps - ln) - pos - 1;
    int v = upper_bound(pos + 1, pos + sig + 1, ps + ln) - pos;
    return tr.query(1, 1, sig, v, sig) > u;
}
signed main() {
    read(n), read(k), read(q);
    for (int i = 1; i <= n; ++i) {
        int x, t, a, b;
        read(x), read(t), read(a), read(b);
        bd[++len] = {a, x, t, i};
        bd[++len] = {b + 1, x, t, -i};
    }
    for (int i = 1; i <= q; ++i)
        read(qr[i].p), read(qr[i].t), qr[i].id = i;
    pos[++sig] = INFL;
    for (int i = 1; i <= len; ++i)
        pos[++sig] = bd[i].p;
    for (int i = 1; i <= q; ++i)
        pos[++sig] = qr[i].p;
    sort(pos + 1, pos + sig + 1);
    sig = unique(pos + 1, pos + sig + 1) - pos - 1;
    for (int i = 1; i <= len; ++i)
        bd[i].p = lower_bound(pos + 1, pos + sig + 1, bd[i].p) - pos;
    for (int i = 1; i <= q; ++i)
        qr[i].p = lower_bound(pos + 1, pos + sig + 1, qr[i].p) - pos;
    sort(bd + 1, bd + len + 1);
    sort(qr + 1, qr + q + 1);
    tr.build(1, 1, sig);
    for (int i = 1; i <= k; ++i) {
        col[i].insert(0), col[i].insert(sig);
        tr.insert(1, 1, sig, sig, i, 0);
    }
    int cbd = 1, cqr = 1;
    while (cqr <= q) {
        while (cbd <= len && bd[cbd].t <= qr[cqr].t)
            insert(bd[cbd++]);
        int l = 0, r = 0x3f3f3f3f, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(pos[qr[cqr].p], mid))
                r = mid - 1, ans = mid;
            else
                l = mid + 1;
        }
        answ[qr[cqr++].id] = ans;
    }
    for (int i = 1; i <= q; ++i)
        write(answ[i]), putchar('\n');
    return 0;
}