CF1140F

link

给定一个点集,初始为空。

q次操作,每次操作给定一个点,若点集中存在这个点就删除这个点,否则插入这个点。

每次操作完之后,输出反复执行如下操作后点集的大小:

找出x1,x2,y1,y2使得(x1,y1)(x1,y2)(x2,y1)都在点集中,且(x2,y2)不在,并将(x2,y2)加入点集。

$q\le 3\cdot 10^5,TL=3.5s,ML=1G$

题解

考虑每个点相当于二分图中的一条边,那么答案就是二分图每个联通块中x方点和y方点点数乘积之和。

删除看上去很麻烦,可以考虑离线之后变成对区间内的询问。

对询问建一棵线段树,最后dfs的时候,每遍历到一个节点,先插入并记录修改的部分,然后如果是叶子就输出答案,否则递归,最后撤回修改。

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: F.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define inf 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline bool read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}

inline bool read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}
inline bool read (char &x) {
x=gc();
return x!=EOF;
}
inline bool read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r')if(*x==EOF)return 0;
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
return 1;
}
template<typename A,typename ...B>
inline bool read(A &x,B &...y){
return read(x)&&read(y...);
}
// prll a signed lleger
inline bool write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}

inline bool write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}
inline bool write (char x) {
putc(x);
return 0;
}
inline bool write(const char *x){
while(*x){putc(*x);++x;}
return 0;
}
inline bool write(char *x){
while(*x){putc(*x);++x;}
return 0;
}
template<typename A,typename ...B>
inline bool write(A x,B ...y){
return write(x)||write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
map<pii,ll> qwq;
ll fa[600005],cnt0[600005],cnt1[600005],ans;
ll a[600005],b[600005],c[600005],d[600005],t;
ll find(ll x){return x==fa[x]?x:find(fa[x]);}
struct smt{
ll ls,rs;
vector<pii> addlist;
smt *l,*r;
smt(ll la,ll ra){
ls=la;rs=ra;
addlist.clear();
if(ls==rs){l=r=0;return;}
ll mid=(ls+rs)>>1;
l=new smt(ls,mid);
r=new smt(mid+1,rs);
}
void add(ll la,ll ra,pii w){
if(la<=ls && rs<=ra){addlist.push_back(w);return;}
if(la<=l->rs)l->add(la,ra,w);
if(r->ls<=ra)r->add(la,ra,w);
}
void calc(){
ll nt=t,oa=ans;
for(auto i:addlist){
if(find(i.x)!=find(i.y+300000)){
ll u=find(i.x),v=find(i.y+300000);
if(cnt0[u]+cnt1[u]>cnt0[v]+cnt1[v])swap(u,v);
++t;
c[t]=cnt0[v];d[t]=cnt1[v];
b[t]=v;
a[t]=u;
fa[u]=v;
ans-=cnt0[u]*cnt1[u]+cnt0[v]*cnt1[v];
cnt0[v]+=cnt0[u];
cnt1[v]+=cnt1[u];
ans+=cnt0[v]*cnt1[v];
}
}
if(ls==rs){write(ans,' ');}
else{
l->calc();
r->calc();
}
while(t>nt){
fa[a[t]]=a[t];
cnt0[b[t]]=c[t];
cnt1[b[t]]=d[t];
--t;
}
ans=oa;
}
};
smt *rt;
int main(){
#ifdef QAQAutoMaton
freopen("F.in","r",stdin);
freopen("F.out","w",stdout);
#endif
for(ll i=1;i<=600000;++i){fa[i]=i;cnt0[i]=i<=300000;cnt1[i]=!cnt0[i];}
ll q;
pii a;
read(q);
rt=new smt(1,q);
for(ll i=1;i<=q;++i){
read(a.x,a.y);
if(qwq.count(a)){
rt->add(qwq[a],i-1,a);
qwq.erase(a);
}
else qwq[a]=i;
}
for(auto i:qwq){
rt->add(i.y,q,i.x);
}
rt->calc();
return 0;
}

评论

Your browser is out-of-date!

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

×