琉焰

C++(clang++ 11.0.1) 解法, 执行用时: 561ms, 内存消耗: 57520K, 提交时间: 2023-02-16 20:14:40

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
const int mod=998244353;

struct dsu {
	int fa[N],siz[N],st[N],top;
	void send(int n) {
		for (int i=1;i<=n;i++) {
			fa[i]=i,siz[i]=1;
		}
	}
	int find(int x) {
		return fa[x]==x?x:find(fa[x]);
	}
	void merge(int u,int v) {
		int x=find(u),y=find(v);
		if (x==y) {
			return;
		}
		if (siz[x]>siz[y]) swap(x,y);
		fa[x]=y;
		siz[y]+=siz[x];
		st[++top]=x;
	}
	void roll_back(int x) {
		while (top>x) {
			int now=st[top--];
			siz[fa[now]]-=siz[now];
			fa[now]=now;
		}
	}
}d;
int n,m,ans[N],pw[N];
struct segment_tree {
	#define ls (w<<1)
	#define rs (w<<1|1)
	#define mid ((l+r)>>1)
	vector<pair<int,int>>t[N*4];
	void add(int w,int l,int r,int ql,int qr,pair<int,int>x) {
		if (ql<=l&&r<=qr) {
			t[w].emplace_back(x);
			return;
		}
		if (ql<=mid){
			add(ls,l,mid,ql,qr,x);
		}
		if (qr>mid) {
			add(rs,mid+1,r,ql,qr,x);
		}
	}
	void dfs(int w,int l,int r) {
		int tmp=d.top;
		for (auto [u,v]:t[w]) {
			d.merge(u,v);
		}
		if (l==r) {
			ans[l]-=d.top;
		} else {
			dfs(ls,l,mid);
			dfs(rs,mid+1,r);
		}
		d.roll_back(tmp);
	}
	#undef mid
	#undef rs
	#undef ls
}t;
void work() {
	cin>>n>>m;
	map<pair<int,int>,int>mp;
	for (int i=pw[0]=1;i<=m;i++) {
		pw[i]=pw[i-1]*2%mod;
		int u,v;
		cin>>u>>v;
		if (mp.count({u,v})) {
			t.add(1,1,m,mp[{u,v}],i-1,{u,v});
			mp.erase({u,v});
		} else {
			mp[{u,v}]=i;
		}
		ans[i]=mp.size();
	}
	for (auto [a,b]:mp) {
		t.add(1,1,m,b,m,a);
	}
	d.send(n);
	t.dfs(1,1,m);
	for (int i=1;i<=m;i++) {
		cout<<pw[ans[i]]-1<<"\n";
	}
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0);
	cout.precision(10),cout.setf(ios::fixed);
	
	int T=1;
	while (T--) {
		work();
	} 
	
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 590ms, 内存消耗: 57648K, 提交时间: 2023-06-23 03:47:11

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;
typedef long long ll;
const int maxn=2e5,N=maxn+10,mod=998244353;
typedef pair<int,int> P;
map<P,int> last;
vector<P>dat[4*N];
int n,m,cnt,par[N],sz[N];
P a;
int tot,ans[N],two[N];
int find(int x){
	return par[x]==x?x:find(par[x]);
}
bool merge(int x,int y,stack<P> &q){
	x=find(x),y=find(y);
	if(x==y)return 1;
	if(sz[x]<sz[y])swap(x,y);
	q.push(P(x,y));
	sz[x]+=sz[y];
	par[y]=x;
    return 0;
}
void undo(stack<P> &q){
	while(!q.empty()){
		int x=q.top().fi;
		int y=q.top().se;
		q.pop();
		sz[x]-=sz[y];
		par[y]=y;
	} 
} 
void update(int p,int l,int r,int ql,int qr,P v){
	if(ql<=l&&r<=qr){
		dat[p].pb(v);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid)update(lson,ql,qr,v);
	if(qr>mid)update(rson,ql,qr,v);
}
void dfs(int p,int l,int r){
	stack<P>q;
    int cnt=0;
	for(auto v:dat[p])
	cnt+=merge(v.fi,v.se,q); // 非树边的数量的变更
	tot+=cnt;
    if(l==r)ans[l]=two[tot]-1;
	else{
		int mid=(l+r)/2;
		dfs(lson);
		dfs(rson);
	}
	undo(q);
    tot-=cnt;
}
int main(){
	scanf("%d%d",&n,&m);
    two[0]=1;
	for(int i=1;i<=m;++i){
        two[i]=two[i-1]*2%mod;
		scanf("%d%d",&a.fi,&a.se);
		if(last.count(a)){
			update(1,1,m,last[a],i-1,a);
			last.erase(a); 
		}
		else last[a]=i;
	}
	for(auto v:last) 
	update(1,1,m,v.se,m,v.fi);
	for(int i=1;i<=m;++i)
	par[i]=i,sz[i]=1;
	dfs(1,1,m);
	for(int i=1;i<=m;++i)
	printf("%d\n",ans[i]);
	return 0;
}

详情