?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
236614457 |
Дорешивание: pengyantong |
1140F - 11 | C++14 (GCC 6-32) | Полное решение | 1076 мс | 181864 КБ | 2023-12-10 08:40:24 | 2023-12-10 08:40:24 |
// LUOGU_RID: 139045485 #include<bits/stdc++.h> using namespace std; #define N 1050500 #define pr pair<int,int> #define mk make_pair #define lc x<<1 #define rc x<<1|1 #define int long long #define u first #define v second pr sta[N]; int f[N],sl[N],sr[N],top,n; vector<pr>g[N<<2]; int find(int x){ return x==f[x]?x:find(f[x]); } int res=0; void merge(int x,int y){ x=find(x),y=find(y); if(x==y){ sta[++top]=mk(-1,-1);return ; } if(sl[x]<sl[y])swap(x,y); f[y]=x;sta[++top]=mk(x,y); res-=sl[x]*sr[x]+sl[y]*sr[y]; sl[x]+=sl[y],sr[x]+=sr[y]; res+=sl[x]*sr[x]; } void move(){ pr x=sta[top--]; if(x.u==-1)return ; res-=sl[x.u]*sr[x.u]; sl[x.u]-=sl[x.v];sr[x.u]-=sr[x.v];f[x.v]=x.v; res+=sl[x.u]*sr[x.u]+sl[x.v]*sr[x.v]; } void insert(int x,int l,int r,int L,int R,pr e){ if(L<=l&&r<=R){ g[x].push_back(e);return ; } int mid=l+r>>1; if(L<=mid)insert(lc,l,mid,L,R,e); if(mid<R)insert(rc,mid+1,r,L,R,e); } void solve(int x,int l,int r){ for(auto e:g[x])merge(e.u,e.v); if(l==r){ cout<<res<<" "; } else { int mid=l+r>>1; solve(lc,l,mid); solve(rc,mid+1,r); } for(auto e:g[x])move(); } map<pr,int>h; signed main(){ ios::sync_with_stdio(false); cin>>n;for(int i=1;i<=n<<1;i++)f[i]=i,sl[i]=(i<=n),sr[i]=(i>n); for(int i=1;i<=n;i++){ pr x;cin>>x.u>>x.v;x.v+=n; if(h.find(x)==h.end())h[x]=i; else { insert(1,1,n,h[x],i-1,x); h.erase(h.find(x)); } } for(auto x:h){ insert(1,1,n,x.v,n,x.u); } solve(1,1,n); }
?
?
?
?