「CC MANYLIST」-树状数组 + map

有 $n$ 个集合,初始都为空,要求支持:

  1. 向第 $[l, r]$ 个集合中加入 $x$。
  2. 求第 $i$ 个集合的元素个数。

链接

CC MANYLIST

题解

对于每个数用 map 维护其出现的区间,每次新加一个区间,将旧的区间合并,并在树状数组上更新就好了。

由于区间一共有 $O(n)$ 个,故时间复杂度为 $O(n \log n)$。

代码

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
/**
* Copyright (c) 2016-2018, xehoth
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* 「CC MANYLIST」12-05-2018
* 树状数组 + map
* @author xehoth
*/
#include <bits/stdc++.h>
const int POOL_SIZE = 20 * 1024 * 1024;
char pool[POOL_SIZE];
void *operator new(size_t size) {
static char *s = pool;
char *t = s;
s += size;
return t;
}
void operator delete(void *) {}
void operator delete(void *, size_t) {}
struct InputOutputStream {
enum { SIZE = 1024 * 1024 };
char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
InputOutputStream() : s(), t(), oh(obuf) {}
~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
inline char read() {
if (s == t) t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin);
return s == t ? -1 : *s++;
}
template <typename T>
inline InputOutputStream &operator>>(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return *this;
iosig |= c == '-';
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
if (iosig) x = -x;
return *this;
}
inline void print(char c) {
if (oh == obuf + SIZE) {
fwrite(obuf, 1, SIZE, stdout);
oh = obuf;
}
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[21], cnt;
if (x != 0) {
if (x < 0) {
print('-');
x = -x;
}
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
} else {
print('0');
}
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
} io;
const int MAXN = 250000 + 9;
int n, m;
struct BinaryIndexedTree {
int d[MAXN], n;
inline void add(int k, int v) {
for (; k <= n; k += k & -k) d[k] += v;
}
inline void modify(int l, int r, int v) {
add(l, v);
add(r + 1, -v);
}
inline int query(int k) {
int ret = 0;
for (; k; k ^= k & -k) ret += d[k];
return ret;
}
} d;
std::map<int, int> range[MAXN];
inline void add(std::map<int, int> &map, int l, int r) {
auto it = map.lower_bound(l);
if (it != map.begin()) {
--it;
if (it->second >= r) return;
if (it->second >= l) {
l = it->first;
d.modify(it->first, it->second, -1);
map.erase(it);
}
}
it = map.lower_bound(l);
while (it != map.end() && it->first <= r) {
r = std::max(it->second, r);
d.modify(it->first, it->second, -1);
it = map.erase(it);
}
map.insert(it, {l, r});
d.modify(l, r, 1);
}
int main() {
// freopen("test/in.in", "r", stdin);
io >> n >> m;
d.n = n;
for (int cmd, l, r, v; m--;) {
io >> cmd;
switch (cmd) {
case 0: {
io >> l >> r >> v;
add(range[v], l, r);
break;
}
case 1: {
io >> l;
io << d.query(l) << '\n';
break;
}
}
}
return 0;
}
分享到