Description
刚开通的SH微博共有n个用户（1..n标号），在短短一个月的时间内，用户们活动频繁，共有m条按时间顺序的记录：
! x 表示用户x发了一条微博；
+ x y 表示用户x和用户y成为了好友
- x y 表示用户x和用户y解除了好友关系
当一个用户发微博的时候，所有他的好友（直接关系）都会看到他的消息。
假设最开始所有人之间都不是好友关系，记录也都是合法的（即+ x y时x和y一定不是好友，而- x y时x和y一定是好友）。
问这m条记录发生之后，每个用户分别看到了多少条消息。
Input
第1行2个整数n,m。
接下来m行，按时间顺序读入m条记录，每条记录的格式如题目所述，用空格隔开。
Output
输出一行n个用空格隔开的数（行末无空格），第i个数表示用户i最后看到了几条消息。
Sample Input
2 8 ! 1 ! 2 + 1 2 ! 1 ! 2 - 1 2 ! 1 ! 2
Sample Output
1 1 只有第4和第5条记录对应的消息被看到过。其他消息发送时，1和2不是好友。 对100%的数据，N<=200000，M<=500000
题解Here!
题意看了我半小时。。。
然后发现，是要求每个人看到别人发了多少条围脖。。。
题意看懂了，第一反应是$LCT$。。。
果然数据结构学傻了。。。
考虑一个用户$x$发微博的时候，他会对所有$x$当前的好友$y$产生一点答案贡献。
于是从$x,y$成为好友，一直到$x,y$解除好友关系，$x$对$y$产生的总贡献一共是：解除好友关系时$x$的微博数-成为好友时$x$的微博数。
那么我们记录一个$num[x]$，表示到目前为止$x$共发了多少条微博。
对于每个点建立一个$set$记录$x$的当前好友集合。
每次加（减）点的同时，把$ans[x]$减去（加上）$num[y]$（有点像差分？）
但是因为只有在解除好友的时候贡献才会被完整统计，所以最后要手动解除所有人的好友关系，即遍历一遍每个人的$set$。
但是这样是$O(m\log_2n)$的，虽然能过，这个$set$感觉有点常数大啊。。。
我们考虑怎样不用$set$。
因为我们最后需要手动解除一遍所有人的好友关系，才需要用$set$来维护每个人的好友集合，这样可以知道每个人剩下的好友都是谁。
那么能不能让他们到最后所有人都没有好友关系呢？
反着处理所有操作就可以啦，因为一开始所有人都没有好友关系。
这个问题就可以被$O(m)$解决了。
附代码：
#include#include #include #define MAXN 500010using namespace std;int n,m;int ans[MAXN],num[MAXN];struct Question{ int f,x,y;}a[MAXN];inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w;}void work(){ for(int i=m;i>=1;i--){ if(a[i].f==1)num[a[i].x]++; else if(a[i].f==2){ ans[a[i].x]+=num[a[i].y]; ans[a[i].y]+=num[a[i].x]; } else{ ans[a[i].x]-=num[a[i].y]; ans[a[i].y]-=num[a[i].x]; } } for(int i=1;i<=n;i++)printf("%d ",ans[i]); printf("\n");}void init(){ char ch[2]; n=read();m=read(); for(int i=1;i<=m;i++){ scanf("%s",ch);a[i].x=read(); if(ch[0]=='!')a[i].f=1; else{ a[i].y=read(); if(ch[0]=='+')a[i].f=2; else a[i].f=3; } }}int main(){ init(); work(); return 0;}