改题进度

  • [x] forgive
  • [x] palingenesis
  • [x] destiny

Review

人要有梦想，暴力还是要打的，没准就过了呢。

Solution

T1 forgive

平面内 nn 个点 (xi,yi)(x_i,y_i)，每个点有 pp 的概率出现，保证三点不共线。可以在两个点之间连一条线段，线段之间不能相交，求最多可以连的线段数的期望。

考虑一个平面图，一定是三角剖分时连的线段最多。

对于一个三角剖分

我们想求的就是剖分的线段数。

设边数为 EE ，点数为 VV ，凸包上有 kk 个点，FF 个有界面，则有结论 E=3V−k−3E=3V-k-3

下面证明这个结论。

对于平面图，有欧拉公式 V+F−E=1V+F-E=1 ，又有 2E=3F+k2E=3F+k （三角形三条边，加上凸包上的边就都算了两次）

将两个式子做一些运算，即可得到 E=3V−k−3E=3V-k-3 。

期望即为 E[E]=E[3V−k−3]=3E[V]−E[k]−3E[E]=E[3V-k-3]=3E[V]-E[k]-3 。

E[V]E[V] 显然为 n×pn\times p，问题转变为求 E[k]E[k] 的值。

发现很难判断一个点是否在凸包上，而判断一个边很容易。

设这条边的左侧有 aa 个点，右侧 bb 个点，则它作为凸包边要求两侧至少一侧没有点出现，概率就是 p2×((1−p)a+(1−p)b)p^2\times\left((1-p)^a+(1-p)^b\right) 。

所以

E[k]=\sum_\limits{i}\left\{p^2\left[(1-p)^{a_i}+(1-p)^{b_i}\right]\times 1\right\}

因为没有点的时候上式会出现问题计算结果成为 −3-3 ，所以答案要加上 −3×P(只有一个点)-3\times P(只有一个点) 。

求 ai,bia_i,b_i 的时候可以固定一个点 uu ，对其所有射线按极角排序，再枚举 vv 点，同一侧的点范围双指针 [l,r][l,r] 可以同步移动，所以求一个点的答案的瓶颈在排序上，总复杂度 O(n2log⁡n)O(n^2\log n)。

卡常小技巧：现将点排序这样可以暴力 O(n^3)​ 跑，cpu 会 if 分支预测，常数极小

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
//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

const int MAXN = 1010;
const int mod = 100000007;

int n, p;
int mul[MAXN], lum[MAXN];
struct Point {
    double x, y;
    bool operator < (Point a) {
        if (x == a.x) return y < a.y;
        else return x < a.x;
    }
} t[MAXN];

double cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
}

int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            (res *= a) %= mod;
        }
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

int ev, et;

signed main() {
    //freopen("forgive0.in", "r", stdin);
    //freopen("forgive0.ans", "w", stdout);
    cin >> n >> p;
    //debug(power(p, mod - 2));
    ev = p * n % mod;
    for (int i = 1; i <= n; i++) {
        cin >> t[i].x >> t[i].y;
    }
    sort(t + 1, t + n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1, a, b; j <= n; j++) {
            a = 0, b = 0;
            for (int u = 1; u <= n; u++) {
                if (u == i || u == j) continue;
                if (cross(t[i], t[j], t[u]) < 0) {
                    a++;
                } else {
                    b++;
                }
            }
            //debugf("i = %lld, j = %lld, a = %lld, b = %lld\n", i, j, a, b);
            (et += p * p % mod * (power(mod + 1 - p, a) + power(mod + 1 - p, b)) % mod) %= mod;
        }
    }
    int ans = ev * 3 % mod - et - 3 + mod;
    //(ans += (1) * (power(mod + 1 - p, n - 1) * p % mod) % mod) %= mod;
    (ans += 3 * power(mod + 1 - p, n) % mod) %= mod;
    cout << ans << endl;
    return 0;
}

T2 palingenesis

四元环计数问题，但是我还在学，于是可以用 O(m2log⁡n)O(m^2\log n) 的做法艹过去。

考虑一个四元环的“对角线”两个点 uu 和 vv

设中间的点有 g(u,v)g(u,v) 个，则对答案贡献是 (g(u,v)2)\dbinom{g(u,v)}{2} 。

考虑枚举 u∈[1,n]u\in[1,n] 作为中间点，它能直接到达两个点 xx yy ，则对 g(x,y)g(x,y) 贡献加一。

复杂度 O(m2log⁡n)O(m^2\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
//author: ycp | https://ycpedef.github.io
#pragma GCC diagnostic error "-std=c++11"
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

int n, m;
map<pair<int, int>, int> g;
vector<int> e[50010];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        e[x].push_back(y), e[y].push_back(x);
    }
    for (int p = 1; p <= n; p++) {
        for (auto u : e[p]) {
            if (u <= p) continue;
            for (auto v : e[p]) {
                if (u <= v) continue;
                g[make_pair(u, v)]++;
            }
        }
    }
    long long ans = 0, v = 0;
    for (auto it : g) {
        v = it.second;
        if (v < 2) continue;
        ans = ans + v * (v - 1) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

T3 destiny

对于每个询问 qq，只需要找出离它最近的 1 修改操作 pp 和时间戳在 [p.t,q.t][p.t,q.t] 范围内的 2 操作取 min⁡\min 即可。

考虑对修改时间分块，维护一个 bitset<SQRTN> b[MAXN]，b[i][j] 存当前块内的第 jj 个修改操作能否到达点 ii，再维护一个 cover[] ，存每个点能否被这个块内的覆盖操作影响到，minv[] ，表示块内 2 操作的最小值，再对询问存储时间戳判断。

块倒序枚举

对于询问 qq （其时间戳为 tt，节点为 uu） ，若 t>r.tt>r.t ，则判断 uu 是否被当前块内的 11 操作覆盖，是的话就暴力倒序枚举这 n\sqrt n 个修改操作，对 ans[t] 取 min⁡\min ，然后删去这个询问

每过 n\sqrt n 个修改清空 bitset cover[] 和 minv[]，然后按拓扑序重构这几个数组，具体可以看代码，应该还是看得懂的。

O(nn+n2ω)O(n\sqrt n+\frac{n^2}{\omega})

用 cout 跑了 8000+ms，printf只用了 3000+ms，printf就是神.jpg

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <bitset>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <cmath> 
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 1e5 + 10;
int n, m, q, tot, head[MAXN], t_tot;
int root[MAXN], indeg[MAXN];
int list[MAXN];

struct Edge {
    int to;
    int next;
} e[MAXN << 1];

void add_edge(int u, int v) {
    tot++;
    e[tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

void topo(int rt) {
    list[++t_tot] = rt;
    //debugf("list[%d] = %d\n", t_tot, rt);
    for (int i = head[rt]; i; i = e[i].next) {
        if (--indeg[e[i].to] == 0) {
            topo(e[i].to);
        }
    }
}

struct Modify {
    int opt, u, x, t;
} modify[MAXN];
int m_tot;

struct Query {
    int u, t;
} query[MAXN];
int q_tot;

int ans[MAXN], cover[MAXN], minv[MAXN], inf;

const int bsiz = 1000;
bitset<bsiz + 10> b[MAXN];

int main() {
    //freopen("destiny7.in", "r", stdin);
    //freopen("destiny7.ans", "w", stdout);
    fastin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        root[i] = 1;
    }
    for (int i = 1, x, y; i <= m; i++) {
        fastin >> x >> y;
        add_edge(x, y);
        root[y] = 0;
        indeg[y]++;
    }
    for (int i = 1; i <= n; i++) {
        if (root[i]) {
            topo(i);
        }
    }
    for (int i = 1; i <= q; i++) {
        fastin >> modify[m_tot].opt;
        if (modify[m_tot].opt <= 2) {
            fastin >> modify[m_tot].u >> modify[m_tot].x;
            modify[m_tot].t = i;
            m_tot++;
        } else {
            fastin >> query[q_tot].u;
            query[q_tot].t = i;
            q_tot++;
        }
    }
    memset(ans, 0x3f, sizeof(ans));
    inf = ans[0];
    int p_siz = m_tot - 1, block = min(sqrt(p_siz) * 5, (double)bsiz);
    for (int l = p_siz - p_siz % block, r = p_siz; l >= 0; r = l - 1, l -= block) {
        //debugf("l = %d, r = %d\n", l, r);
        for (int i = 1; i <= n; i++) {
            b[i].reset();
        }
        for (int i = l; i <= r; i++) {
            b[modify[i].u][i - l] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = head[list[i]]; j; j = e[j].next) {
                b[e[j].to] |= b[list[i]];
            }
        }
        //for (int i = 1; i <= n ;i++) {
            //cerr << i << ": " << b[i] << endl;
        //}
        memset(cover, 0, sizeof(cover));
        for (int i = l; i <= r; i++) {
            //debugf("%d %d %d\n", modify[i].opt, modify[i].u, modify[i].x);
            if (modify[i].opt == 1) {
                cover[modify[i].u] = 1;
                //debugf("modify cover[%d] = %d\n", modify[i].u, cover[modify[i].u]);
            }
        }
        for (int i = 1; i <= n; i++) {
            //debugf("cover[%d] = %d\n", list[i], cover[list[i]]);
            if (!cover[list[i]]) continue;
            //debugf("work on %d\n", list[i]);
            for (int j = head[list[i]]; j; j = e[j].next) {
                //debugf("%d -> %d\n", list[i], e[j].to);
                cover[e[j].to] = 1;
            }
        }
        //for (int i = 1; i <= n ;i++) {
            //debugf("cover[%d] = %d\n", i, cover[i]);
        //}
        memset(minv, 0x3f, sizeof(minv));
        for (int i = l; i <= r; i++) {
            if (modify[i].opt == 1) continue;
            cmin(minv[modify[i].u], modify[i].x);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = head[list[i]]; j; j = e[j].next) {
                cmin(minv[e[j].to], minv[list[i]]);
            }
        }
        //for (int i = 1; i <= n; i++) {
            //debugf("minv[%d] = %d\n", i, minv[i]);
        //}
        int i = q_tot;
        //debug(q_tot);
        while (i && query[i - 1].t > modify[l].t) i--;
        while (i < q_tot) {
            if (query[i].t > modify[r].t) {
                if (cover[query[i].u]) {
                    int j = r;
                    for (j = r; j >= l && (modify[j].opt == 2 || !b[query[i].u][j - l]); j--) {
                        if (modify[j].opt == 2 && b[query[i].u][j - l]) {
                            cmin(ans[query[i].t], modify[j].x);
                        }
                    }
                    cmin(ans[query[i].t], modify[j].x);
                    swap(query[i], query[--q_tot]);
                } else {
                    cmin(ans[query[i].t], minv[query[i].u]);
                    i++;
                }
            } else {
                int j = r;
                while (modify[j].t > query[i].t) j--;
                for (; j >= l; j--) {
                    if (!b[query[i].u][j - l]) continue;
                    cmin(ans[query[i].t], modify[j].x);
                    if (modify[j].opt == 1) {
                        swap(query[i], query[--q_tot]);
                        break;
                    }
                }
                if (j < l) i++;
            }
        }
    }
    while (q_tot--) ans[query[q_tot].t] = 0;
    for (int i = 1; i <= q; i++) {
        if (ans[i] != inf) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}