#倒推#洛谷 3998 [SHOI2013]发微博

题目


分析

考虑(x)看到(y)的消息条数等于互删时(y)发的消息条数减去互加时(y)发的消息条数
为了让最后(x)(y)不再为好友,那可以将操作反过来,因为一开始他们一定不是好友,
所以记录某人发的消息条数(cnt),倒序维护发微博,
加好友((ans_x+=cnt_y,ans_y+=cnt_x)),
删好友((ans_x-=cnt_y,ans_y-=cnt_x))即可


代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=500011;
int opt[N],X[N],Y[N],ans[N>>1],cnt[N>>1],n,m;
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
signed main(){
    n=iut(); m=iut();
    for (rr int i=1;i<=m;++i){
        rr char c=getchar();
        while (c!='!'&&c!='+'&&c!='-') c=getchar();
        opt[i]=(c=='!')+(c=='+')*2+(c=='-')*3,X[i]=iut();
        if (opt[i]>1) Y[i]=iut();
    }
    for (rr int i=m;i;--i){
        if (opt[i]==1) ++cnt[X[i]];
        else if (opt[i]==2) ans[X[i]]+=cnt[Y[i]],ans[Y[i]]+=cnt[X[i]];
            else ans[X[i]]-=cnt[Y[i]],ans[Y[i]]-=cnt[X[i]];
    }
    for (rr int i=1;i<=n;++i) print(ans[i]),putchar(32);
    return 0;
}
原文地址:https://www.cnblogs.com/Spare-No-Effort/p/13523755.html