好友状态的变化次数不会超过m，于是考虑暴力，对每个人记录其好友关系的变化，通过前缀和计算贡献。这需要查询一段前缀时间内某人发的微博数量，可以离线建一棵绝对平衡的平衡树。事实上完全可以线性。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 200010 #define M 500010 int n,m,ans[N],root[N],cnt=0,flag[N]; vector<int> t[N],h[N],op[N],a[N]; struct data{int ch[2],x,s; }tree[M]; void build(int i,int &k,int l,int r) { if (l>r) return; int mid=l+r>>1; k=++cnt;tree[k].x=a[i][mid]; if (l==r) {tree[k].s=1;return;} build(i,tree[k].ch[0],l,mid-1); build(i,tree[k].ch[1],mid+1,r); tree[k].s=tree[tree[k].ch[0]].s+tree[tree[k].ch[1]].s+1; } int query(int k,int x) { if (k==0) return 0; if (x<tree[k].x) return query(tree[k].ch[0],x); else return tree[tree[k].ch[0]].s+1+query(tree[k].ch[1],x); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4419.in","r",stdin); freopen("bzoj4419.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif srand(20020509); n=read(),m=read(); for (int i=1;i<=m;i++) { char c=getchar(); while (c!='!'&&c!='+'&&c!='-') c=getchar(); if (c=='!') a[read()].push_back(i); else { int x=read(),y=read(); t[x].push_back(i),h[x].push_back(y),op[x].push_back(c=='+'?-1:1); t[y].push_back(i),h[y].push_back(x),op[y].push_back(c=='+'?-1:1); } } for (int i=1;i<=n;i++) if (a[i].size()) { sort(a[i].begin(),a[i].end()); build(i,root[i],0,a[i].size()-1); } for (int i=1;i<=n;i++) { for (int j=0;j<t[i].size();j++) ans[i]+=query(root[h[i][j]],t[i][j])*op[i][j],flag[h[i][j]]+=op[i][j]; for (int j=0;j<t[i].size();j++) if (flag[h[i][j]]) flag[h[i][j]]=0,ans[i]+=tree[root[h[i][j]]].s; } for (int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }