LOJ6131 -「2017 山东三轮集训 Day1」Fiend

考虑到原问题等价于以下行列式的值:

$$
第 i 行的 l_i 到 r_i 的值为 1 ,其他为 0 。
$$

我们采用高斯消元,复杂度 $O(n ^ 3)$ ,可以获得 70 pts.

考虑优化,由于 $1$ 的位置是连续的区间,采用左偏树维护每个左端点的右端点最小值即可。

注意行列式中交换两列,行列式的值取相反数;如果不能消成单位矩阵,则行列式的值为 $0$ 。

代码:

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
// =================================
// author: memset0
// date: 2019.01.12 13:44:20
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 1e5 + 10;
int T, n, m, ans, cnt;
int rt[N], l[N], r[N], id[N], val[N], ch[N][2], dis[N], pos[N];

inline int new_node(int w, int i) { val[i] = w, dis[i] = 1; return id[i] = i; }

inline int merge(int x, int y) {
if (!x || !y) return x | y;
if (val[x] > val[y] || (val[x] == val[y] && id[x] > id[y])) std::swap(x, y);
ch[x][1] = merge(ch[x][1], y);
if (dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
dis[x] = dis[ch[x][0]] + 1;
return x;
}

void main() {
for (read(T); T--; ) {
read(n), cnt = 0;
for (int i = 1; i <= n; i++) rt[i] = ch[i][0] = ch[i][1] = 0, pos[i] = i;
for (int i = 1; i <= n; i++) {
read(l[i]), read(r[i]);
rt[l[i]] = merge(rt[l[i]], new_node(r[i], i));
}
ans = 1;
for (int i = 1, nxt, x, y; i <= n; i++) {
while (rt[i] && val[rt[i]] < i)
rt[i] = merge(ch[rt[i]][0], ch[rt[i]][1]);
if (rt[i]) {
// std::cout << rt[i] << " " << val[rt[i]] << " " << id[rt[i]] << std::endl;
if (id[rt[i]] != i) {
// printf("%d %d : %d %d\n", rt[i], pos[i], id[rt[i]], id[pos[i]]);
x = rt[i], y = pos[i];
std::swap(id[x], id[y]);
std::swap(pos[id[x]], pos[id[y]]);
ans *= -1;
}
nxt = val[rt[i]];
rt[i] = merge(ch[rt[i]][0], ch[rt[i]][1]);
if (nxt + 1 <= n) {
// printf("%d => %d\n", i, nxt + 1);
rt[nxt + 1] = merge(rt[i], rt[nxt + 1]);
}
} else {
ans = 0;
break;
}
}
// std::cout << ans << std::endl;
putchar("FDY"[ans + 1]), putchar('\n');
}
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×