题解 P3998 【发微博】

午夜飘雪 · 2017-12-14 19:38:27 · 题解

考虑一个用户x发微博的时候，他会对所有x当前的好友y产生一点答案贡献

于是从xy成为好友，一直到xy解除好友关系，x对y产生的总贡献一共是（解除好友关系时x的微博数-成为好友时x的微博数）

那么我们记录一个cnt[x]，表示到目前为止x共发了多少条微博

对于每个点建立一个set记录x的当前好友集合

每次加（减）点的同时，把ans[x]减去（加上）cnt[y]（有点像差分？）

但是因为只有在解除好友的时候贡献才会被完整统计，所以最后要手动解除所有人的好友关系，即遍历一遍每个人的set

时间复杂度O(mlogn)，具体实现见代码

    #include<iostream>
    #include<cstdio>
    #include<set>
    using namespace std;
    const int N=200009;
    int n,m,cnt[N],ans[N];
    set<int>s[N];
    set<int>::iterator it;
    int main(){
        ios::sync_with_stdio(0);
        cin>>n>>m;
        for(int i=1;i<=m;++i){
            char opt;cin>>opt;
            if(opt=='!'){
                int x;cin>>x;
                ++cnt[x];
            }
            if(opt=='+'){
                int x,y;cin>>x>>y;
                ans[x]-=cnt[y];ans[y]-=cnt[x];
                s[x].insert(y);s[y].insert(x);
            }
            if(opt=='-'){
                int x,y;cin>>x>>y;
                ans[x]+=cnt[y];ans[y]+=cnt[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){
            ans[i]+=cnt[*it];
        }
        for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
        return 0;
    }

做完之后一想，总觉得这个set大材小用了，能不能不用啊

于是……开始考虑这个set到底起了什么作用

归根结底就是因为最后需要手动解除一遍所有人的好友关系，才需要用set来维护每个人的好友集合，这样可以知道每个人剩下的好友都是谁

那么能不能让他们到最后所有人都没有好友关系呢？

反着处理所有操作就可以啦，因为一开始所有人都没有好友关系

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=200009,M=500009;
    int n,m,data[M][2],cnt[N],ans[N];
    char opt[M];
    int main(){
        ios::sync_with_stdio(0);
        cin>>n>>m;
        for(int i=1;i<=m;++i){
            cin>>opt[i];
            if(opt[i]=='!')cin>>data[i][0];
            if(opt[i]=='+')cin>>data[i][0]>>data[i][1];
            if(opt[i]=='-')cin>>data[i][0]>>data[i][1];
        }
        for(int i=m;i;--i){
            if(opt[i]=='!')++cnt[data[i][0]];
            if(opt[i]=='+'){
                ans[data[i][0]]+=cnt[data[i][1]];ans[data[i][1]]+=cnt[data[i][0]];
            }
            if(opt[i]=='-'){
                ans[data[i][0]]-=cnt[data[i][1]];ans[data[i][1]]-=cnt[data[i][0]];
            }
        }
        for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
        return 0;
    }

这样只用O(m)就解决了问题 虽然mlogn就能过

顺手安利一发博客