Day5

【匹配】
简单的模拟题,这里略过。

【矩形】
题意:给出n条直线,求组成的矩形个数。
60%的做法,先枚举两条平行的直线,再枚举垂直于前两条直线且有交点的线,用排列组合求出答案。这个做法是O(n^3)。
由数据范围可知O(n^3)的时间复杂度刚好超时,考虑优化上面的算法,用bitset记录每两条直线是否相交,那么,求垂直于两条直线且相交就变成了求两条直线bitset的和(&)。由于直线分为两种,垂直于x轴与平行于x轴,可以枚举直线少的来进行&操作。时间复杂的为O(n^3/128)。
正解为树状数组(线段树)来维护两条平行直线间共有的相交直线数。时间复杂度O(n^2longn)。

【历史】
题意:每次连一条边,询问两个点是否在t之前不联通,在当前时刻联通,强制在线。
由于强制在线的是连接的边,对于询问并没有要求强制在线,那么,先将询问存下来,对于t之前的状态可在t时记录,t的状态可直接得到。
正解是可持久化并查集, 用可持久化线段树维护可持久化数组,由于修改的只能是一个数,所以合并并查集时不能用路径压缩,需要用启发式合并,那么,对于每个询问只需查找当前数组和前t的数组即可。

代码如下(可持久化并查集代码明天补充)


【矩形】:


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
#include<iostream>
#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;
}

【历史】


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
#include<cstdio>
#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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注