LOJ3275

Solution

注意到一个性质: 由二元环连接的点集中每一条可能的边都存在。所以一个点集SS对答案的贡献为S×(S1)+S×indeg(S)|S| \times (|S| - 1) + |S| \times indeg(S),其中indeg(S)indeg(S)表示指向该点集的入点集合大小

于是可以将由二元环连成的点集缩点,用并查集维护,另外再维护两个set用来存每个点集的入点集合和出点集合

维护时使用启发式合并即可做到O(mlog2n)O(m \log^2 n)

Code

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
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 3e5;

int N, M;

map <int, set <int> > out[MAXN + 5], in[MAXN + 5];
int in_deg[MAXN + 5], out_deg[MAXN + 5];

queue <pii> que;

LL ans;

namespace DSU
{
int fa[MAXN + 5], size[MAXN + 5];

inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i, size[i] = 1; }

inline int get_fa (int x) { return fa[x] == x ? x : fa[x] = get_fa (fa[x]); }

inline LL calc (int x) { return (LL) size[x] * (size[x] - 1) + (LL) in_deg[x] * size[x]; }

inline void link (int x, int y)
{
ans -= calc (x) + calc (y);

if (in_deg[x] + out_deg[x] < in_deg[y] + out_deg[y]) swap (x, y);

for (auto &S : in[y]) for (auto &p : S.y)
{
int fp = S.x;

que.push (mp (p, x));

out[fp][y].erase (p);
if (out[fp][y].empty()) out[fp].erase (y);

--out_deg[fp], --in_deg[y];
}

for (auto &S : out[y]) for (auto &p : S.y)
{
int fp = S.x;
que.push (mp (p, fp));

in[fp][y].erase (p);
if (in[fp][y].empty()) in[fp].erase (y);

--in_deg[fp], --out_deg[y];

if (fp != x) ans -= size[fp];
}

size[x] += size[y], fa[y] = x;

ans += calc (x);
}
}

using DSU :: size;

inline void add_edge (int x, int y)
{
int fx = DSU :: get_fa (x), fy = DSU :: get_fa (y);

if ((fx == fy) || (out[fx].count (fy) && out[fx][fy].count (x))) return ;

out[fx][fy].insert (x), in[fy][fx].insert (x);
++out_deg[fx], ++in_deg[fy];

ans += size[fy];

if (in[fx].count (fy)) DSU :: link (fx, fy);
}

inline void Solve ()
{
DSU :: init ();
while (M--)
{
int x = read<int>(), y = read<int>();
add_edge (x, y);
while (!que.empty())
{
add_edge (que.front().x, que.front().y);
que.pop();
}
printf("%lld\n", ans);
}
}

inline void Input ()
{
N = read<int>(), M = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("joitter2.in", "r", stdin);
freopen("joitter2.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}