P3998 [SHOI2013]发微博

题目

P3998 [SHOI2013]发微博

分析

大水题。

很经典的套路：直接维护并不好维护，于是考虑给自身打上加法标记，而如果和带有加法标记的点断开，则这个点的答案加上加法标记的值，如果需要连接，则这个点先减去当前的加法标记再连接。

而这里连/删得是无向边，所以两端都要减掉对方的加法标记，也要同时加上对方的加法标记。

然后连边就直接随便用个什么维护一下就行了，这里用的 (map) 。

代码

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
#define ll long long
#define ull unsigned long long
#define inc(x,y,mod) (((x)+(y))>=(mod)?(x)+(y)-(mod):(x)+(y))
#define dec(x,y,mod) ((x)-(y)<0?(x)-(y)+(mod):(x)-(y))
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define dep(i,y,x) for(int i=(y);i>=(x);i--)
const int N=2e5+5,NM=62,M=2e5+5,INF=1e9+7;
int n,m;
#define PII pair<int,int>
#define mp make_pair
int sum[N],tag[N];
namespace Map{
	const int Size=1e6+5;
	int head[Size],nex[Size],val[Size],idx;
	PII to[Size];
	const int mod=999983;
	inline void Insert(PII x,int v){
		int key=(1ll*x.first*x.second%mod*131)%mod*13%mod;
		for(int i=head[key];i;i=nex[i]) if(to[i]==x) return val[i]+=v,void();
		nex[++idx]=head[key],to[idx]=x,val[idx]+=v,head[key]=idx;
		return ;
	}
	/*
	遍历所有元素：
	for(int i=1;i<=idx;i++) if(val[i]) now=to[i];
	*/
}
inline void Link(int u,int v){
	if(u>v) swap(u,v);
	sum[v]-=tag[u],sum[u]-=tag[v];
	Map::Insert(mp(u,v),1);
	return ;
}
inline void Cut(int u,int v){
	if(u>v) swap(u,v);
	sum[u]+=tag[v],sum[v]+=tag[u];
	Map::Insert(mp(u,v),-1);
	return ;
}
signed main(){
	read(n);read(m);
	while(m--){
		char op[5];int x,u,v;
		scanf("%s",op);
		if(op[0]=='!') read(x),tag[x]++;
		else if(op[0]=='-') read(u),read(v),Cut(u,v);
		else read(u),read(v),Link(u,v);
	}
	for(int i=1;i<=Map::idx;i++){
		if(!Map::val[i]) continue;
		PII t=Map::to[i];
		int u=t.first,v=t.second;
		sum[u]+=tag[v],sum[v]+=tag[u];
	}
	for(int i=1;i<=n;i++) write(sum[i]),putchar(' ');
	return 0;
}