?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
194545568 |
Дорешивание: Ieihonglongyin |
1140F - 11 | C++17 (GCC 9-64) | Полное решение | 1310 мс | 147552 КБ | 2023-02-22 11:31:22 | 2023-02-22 11:31:22 |
// LUOGU_RID: 102716781 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=6e5+5,M=3e5; int n,q,top,fa[N],sz1[N],sz2[N]; ll ans; pair<int,int>st[N]; map<pair<int,int>,int>mp; struct tree{ int l,r; vector<pair<int,int> >c; }t[N<<2]; int gf(int x){return x==fa[x]?x:gf(fa[x]);} void link(int x,int y) { x=gf(x),y=gf(y); if(x==y)return; if(sz1[x]+sz2[x]>sz1[y]+sz2[y])swap(x,y); fa[x]=y,ans-=1ll*sz1[y]*sz2[y]+1ll*sz1[x]*sz2[x]; st[++top]={x,y},sz1[y]+=sz1[x],sz2[y]+=sz2[x],ans+=1ll*sz1[y]*sz2[y]; } void del(int now) { while(top>now) { int x=st[top].first,y=st[top].second;ans-=1ll*sz1[y]*sz2[y]; fa[x]=x,sz1[y]-=sz1[x],sz2[y]-=sz2[x],top--,ans+=1ll*sz1[y]*sz2[y]+1ll*sz1[x]*sz2[x]; } } void build(int p,int l,int r) { t[p]={l,r}; if(l==r)return; int mid=l+r>>1; build(p<<1,l,mid),build(p<<1|1,mid+1,r); } void change(int p,int l,int r,int x,int y) { if(t[p].l>r||t[p].r<l)return; if(t[p].l>=l&&t[p].r<=r)return t[p].c.push_back({x,y}),void(); change(p<<1,l,r,x,y),change(p<<1|1,l,r,x,y); } void solve(int p) { int now=top; for(auto i:t[p].c)link(i.first,i.second); if(t[p].l==t[p].r) { printf("%lld ",ans); return del(now),void(); } solve(p<<1),solve(p<<1|1),del(now); } int main() { scanf("%d",&q); for(int i=1;i<=2*M;i++)fa[i]=i,sz1[i]=(i<=M),sz2[i]=(i>M); build(1,1,q); for(int i=1,x,y;i<=q;i++) { scanf("%d%d",&x,&y),y+=M; if(mp[{x,y}])change(1,mp[{x,y}],i-1,x,y),mp[{x,y}]=0; else mp[{x,y}]=i; } for(auto i:mp)if(i.second)change(1,i.second,q,i.first.first,i.first.second); solve(1); return 0; }
?
?
?
?