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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;
const int MAXM = 1e5 + 10;
const int MAXT = MAXN * 4 + MAXM * 4;
struct Type {
int t, p;
Type(int x = 0, int y = 0) {t = x, p = y;}
bool operator < (const Type& rhs) const {
if (p != rhs.p) return p < rhs.p;
return t < rhs.t;
}
};
int T, n, m;
map<Type, int> mp;
int cnt;
vector<int> G[MAXT];
bitset<16668> s[MAXT], delta;
bool vis[MAXT];
int ans[MAXN], delt;
bool noans[MAXN];
inline void AddEdge(int u, int v) {
G[u].push_back(v);
}
int l, r;
void dfs(int u) {
if (vis[u]) return;
vis[u] = 1;
if (u <= 2 * n && (u & 1)) {
int p = (u + 1) >> 1;
if (l <= p && p <= r)
s[u][p - l + 1] = 1;
return;
}
for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
int v = *it;
dfs(v);
s[u] |= s[v];
}
return;
}
int main() {
scanf("%d%d%d", &T, &n, &m);
for (int i = 1; i <= n; ++i) {
mp[Type(T + 1, i)] = ++cnt, ++cnt;
}
for (int i = 1; i <= m; ++i) {
int c, t, x, y;
scanf("%d%d%d%d", &c, &t, &x, &y);
if (c == 0) {
if (mp[Type(t, x)] == 0)
mp[Type(t, x)] = ++cnt, ++cnt;
if (mp[Type(t + 1, y)] == 0)
mp[Type(t + 1, y)] = ++cnt, ++cnt;
AddEdge(mp[Type(t, x)], mp[Type(t + 1, y)]),
AddEdge(mp[Type(t + 1, y)] + 1, mp[Type(t, x)] + 1);
} else {
if (mp[Type(t, x)] == 0)
mp[Type(t, x)] = ++cnt, ++cnt;
if (mp[Type(t, y)] == 0)
mp[Type(t, y)] = ++cnt, ++cnt;
AddEdge(mp[Type(t, x)] + 1, mp[Type(t, y)]),
AddEdge(mp[Type(t, y)] + 1, mp[Type(t, x)]);
}
}
int lt = 0, lp = 0, lc = 0;
for (auto it : mp) {
int t = it.first.t, p = it.first.p, c = it.second;
if (lt) {
if (lp == p) {
AddEdge(lc, c), AddEdge(c + 1, lc + 1);
}
}
lt = t, lp = p, lc = c;
}
for (l = 1; l <= n; l += 16667) {
r = min(n, l + 16666);
for (int i = 1; i <= cnt; ++i)
s[i].reset();
delta.reset();
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; ++i)
dfs(i << 1);
for (int i = l; i <= r; ++i) {
if (s[i << 1][i - l + 1]) {
noans[i] = 1;
delta[i - l + 1] = 1;
}
}
for (int i = 1; i <= n; ++i) {
s[i << 1] |= delta;
ans[i] += r - l + 1 - s[i << 1].count();
}
}
for (int i = 1; i <= n; ++i)
printf("%d ", noans[i] ? 0 : ans[i] - 1);
return 0;
}
|