【匹配】
简单的模拟题，这里略过。
【矩形】
题意：给出n条直线，求组成的矩形个数。
60%的做法，先枚举两条平行的直线，再枚举垂直于前两条直线且有交点的线，用排列组合求出答案。这个做法是O(n^3)。
由数据范围可知O(n^3)的时间复杂度刚好超时，考虑优化上面的算法，用bitset记录每两条直线是否相交，那么，求垂直于两条直线且相交就变成了求两条直线bitset的和（&）。由于直线分为两种，垂直于x轴与平行于x轴，可以枚举直线少的来进行&操作。时间复杂的为O(n^3/128)。
正解为树状数组（线段树）来维护两条平行直线间共有的相交直线数。时间复杂度O(n^2longn)。
【历史】
题意：每次连一条边，询问两个点是否在t之前不联通，在当前时刻联通，强制在线。
由于强制在线的是连接的边，对于询问并没有要求强制在线，那么，先将询问存下来，对于t之前的状态可在t时记录，t的状态可直接得到。
正解是可持久化并查集， 用可持久化线段树维护可持久化数组，由于修改的只能是一个数，所以合并并查集时不能用路径压缩，需要用启发式合并，那么，对于每个询问只需查找当前数组和前t的数组即可。
代码如下（可持久化并查集代码明天补充）
【矩形】：
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
#include<algorithm>
#include<cstdio>
#include<bitset>
using namespace std;
struct E {
int x, y, x2, y2, bo;
friend bool operator <(E a, E b) {
return a.bo > b.bo;
}
}p[2010];
int tot, n, ans, Num;
bitset<2005> Bit[2005];
int fp(int x, int y) {
if (p[x].y < p[x].y2) swap(p[x].y, p[x].y2);
if (p[y].x < p[y].x2) swap(p[y].x, p[y].x2);
if (p[x].y >= p[y].y && p[y].y >= p[x].y2 && p[y].x >= p[x].x && p[x].x >= p[y].x2)
return 1;
return 0;
}
int main(void)
{
//freopen("rect.in","r",stdin);
//freopen("rect.out","w",stdout);
scanf("%d", &n);
for (int i = 1;i <= n; i++) {
scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i].x2, &p[i].y2);
p[i].bo = (p[i].x == p[i].x2);
tot += p[i].bo;
}
sort(p + 1, p + 1 + n);
for (int i = 1;i <= tot; i++)
for (int j = tot + 1;j <= n; j++)
if (fp(i, j)) {
Bit[i].flip(j);
Bit[j].flip(i);
}
if (tot < n / 2)
for (int i = 1;i <= tot; i++)
for (int j = 1;j <= tot; j++) {
Num = (Bit[i] & Bit[j]).count();
ans += Num * (Num - 1) / 2;
}
else
for (int i = tot + 1;i <= n; i++)
for (int j = i + 1;j <= n; j++) {
Num = (Bit[i] & Bit[j]).count();
ans += Num * (Num - 1) / 2;
}
cout << ans;
fclose(stdin);
fclose(stdout);
return 0;
}
【历史】
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
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 3e5 + 10;
struct io {
io() {
freopen("histroy.in", "r", stdin);
freopen("histroy.out", "w", stdout);
}
~io() {
fclose(stdin);
fclose(stdout);
}
}text;
int Read() {
int val = 0, opt = 1;
char ch;
while (!(isdigit( ch = getchar() ) || ch == '-'));
if (ch == '-') opt = -1;
else val = ch - '0';
while (isdigit( ch = getchar())) (val *= 10) += ch - '0';
return val * opt;
}
struct Node {
int ls, rs, fa, dep;
}tr[N * 25];
int n, m, rt[N], tot, Age, Num, c = 0;
void build(int &cnt, int l, int r) {
cnt = ++tot;
if (l == r) {
tr[cnt].fa = l;
tr[cnt].dep = 1;
return ;
}
build(tr[cnt].ls, l, (l + r) / 2);
build(tr[cnt].rs, (l + r) / 2 + 1, r);
}
void cg(int &cnt, int lst, int l, int r, int x, int fat) {
cnt = ++tot;
if (l == r) {
tr[cnt].fa = fat;
return ;
}
tr[cnt] = tr[lst];
if (x <= (l + r) / 2) cg(tr[cnt].ls, tr[lst].ls, l, (l + r) / 2, x, fat);
else cg(tr[cnt].rs, tr[lst].rs, (l + r) / 2 + 1, r, x, fat);
}
int Find(int cnt, int l, int r, int x) {
if (l == r) return cnt;
if (x <= (l + r) / 2) return Find(tr[cnt].ls, l, (l + r) / 2, x);
else return Find(tr[cnt].rs, (l + r) / 2 + 1, r, x);
}
int gf(int x, int cnt) {
int fat = tr[Find(cnt, 1, n, x)].fa;
if (x == fat) return fat;
return gf(fat, cnt);
}
int main(void) {
n = Read(), m = Read();
build(rt[0], 1, n);
char ch;
int u, v, lst = 0, t, f1, f2;
for (int i = 1;i <= m; i++) {
ch = getchar();
while (!(ch == 'R' || ch == 'K' || ch == 'T')) ch = getchar();
if (ch == 'K') {
v = Read();
c = v;
lst = 0;
}
if (ch == 'R') {
++Age;
u = Read(), v = Read();
if (lst) u = (u + c) % n, v = (v + c) % n;
++u, ++v;
u = gf(u, rt[Age - 1]), v = gf(v, rt[Age - 1]);
if (u == v) {
rt[Age] = rt[Age - 1];
continue;
}
f1 = Find(rt[Age - 1], 1, n, u), f2 = Find(rt[Age - 1], 1, n, v);
if (tr[f1].dep > tr[f2].dep) swap(f1, f2);
cg(rt[Age], rt[Age - 1], 1, n, tr[f1].fa, tr[f2].fa);
tr[Find(rt[Age], 1, n, tr[f2].fa)].dep = max(tr[f1].dep + 1, tr[f2].dep);
}
if (ch == 'T') {
u = Read(), v = Read(), t = Read();
++u, ++v;
if (t > Age)
t = Age;
if (gf(u, rt[Age]) == gf(v, rt[Age]) && gf(u, rt[Age - t]) != gf(v, rt[Age - t]))
lst = 0;
else lst = 1;
if (lst) {
putchar('N');
putchar('\n');
}
else {
putchar('Y');
putchar('\n');
}
}
}
return 0;
}