好友狀态的變化次數不會超過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;
}