yjq_1999

Solution:

考虑枚举每条边的贡献，一条边(x,y,l,r)表示x，y这条边在l到r时间内出现过，对y的贡献是x在这段时间内发的微博数，对x贡献同理。

考虑用前缀和进行优化，倒过来做，加入一条边的时候加入反序前缀和，不然减去反序前缀和，发微博就使x点的前缀和++

代码：

#include <cstdio>
#define N 500010
using namespace std;
int x[N],y[N],v[N],n,m,i;char S[10],t[N];long long s[N];
int main() {
  for (scanf("%d%d",&n,&m),i=1;i<=m;i++) {scanf("%s%d",S,&x[i]),t[i]=S[0];if(S[0]!='!')scanf("%d",&y[i]);}
  for (i=m;i;i--) if (t[i]=='!')v[x[i]]++;else if (t[i]=='+')s[x[i]]+=v[y[i]],s[y[i]]+=v[x[i]];else s[x[i]]-=v[y[i]],s[y[i]]-=v[x[i]];
  for (i=1;i<=n;i++) printf("%lld",s[i]),putchar(i==n?10:' ');
}