bzoj 4419 发微博

Posted on | Views:

乱搞.

  • 对每个人 $i$ 维护一个标记 $val_i$ ,表示这个人发过了多少条微博.
  • 如果新连上一个点 $j$ , $ans_j-=val_i$ ,若断开一个点 $j$ , $ans_j+=val_i$ .
  • 最后再将所有边断掉即可.

注意自己发的微博不计入自己的贡献.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,m,ans[MAXN],val[MAXN];
set<int> s[MAXN];
set<int>::iterator it;
int main()
{
	n=read(),m=read();
	while(m--)
	{
		char buf[2];
		scanf("%s",buf);
		if(buf[0]=='!')
		{
			int x=read();
			++val[x];
		}
		else if(buf[0]=='+')
		{
			int x=read(),y=read();
			ans[x]-=val[y];
			ans[y]-=val[x];
			s[x].insert(y);
			s[y].insert(x);
		}
		else
		{
			int x=read(),y=read();
			ans[x]+=val[y];
			ans[y]+=val[x];
			s[x].erase(y);
			s[y].erase(x);
		}
	}
	for(int i=1;i<=n;++i)
		for(it=s[i].begin();it!=s[i].end();++it)
		{
			int j=*it;
			s[i].erase(j);
			s[j].erase(i);
			ans[i]+=val[j];
			ans[j]+=val[i];
		}
	printf("%d",ans[1]);
	for(int i=2;i<=n;++i)
		printf(" %d",ans[i]);
	return 0;
}