bzoj4419: [Shoi2013]发微博（三种做法）

阅读量：314 次

发布时间：2019-03-03

本文共 2571 字，大约阅读时间需要 8 分钟。

Description

刚开通的SH微博共有n个用户（1..n标号），在短短一个月的时间内，用户们活动频繁，共有m条按时间顺序的记录：

! x 表示用户x发了一条微博；

+ x y 表示用户x和用户y成为了好友

- x y 表示用户x和用户y解除了好友关系

当一个用户发微博的时候，所有他的好友（直接关系）都会看到他的消息。

假设最开始所有人之间都不是好友关系，记录也都是合法的（即+ x y时x和y一定不是好友，而- x y时x和y一定是好友）。

问这m条记录发生之后，每个用户分别看到了多少条消息。

Input

第1行2个整数n,m。

接下来m行，按时间顺序读入m条记录，每条记录的格式如题目所述，用空格隔开。

Output

输出一行n个用空格隔开的数（行末无空格），第i个数表示用户i最后看到了几条消息。

Sample Input

2 8

! 1

! 2

! 1

! 2

! 1

! 2

Sample Output

1 1

只有第4和第5条记录对应的消息被看到过。其他消息发送时，1和2不是好友。

对100%的数据，N<=200000，M<=500000

感想

这题我有三个方法..

我的是最垃圾的。。

别的都很好

题解

1 线段树（我的）

这个做法很蠢啊。。写了4000B。。

最近思维退化，只会用线段树了

我们可以吧+和,-分开弄

然后离线可以知道每个人按时间顺序依次影响到的是哪些人。。

然后按顺序可以弄成一段连续的区间。。

对于每个人维护一个当前扫到右边的坐标，然后每一次他发信息就整体加上就好了

不想写了

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=200005;const int M=500005;int n,m;struct qq{    int c;//0:发微博     1:删除     2:加上     int x,y,id;}s[M],s1[M],s2[M];//原来的操作   增加操作   删除操作 bool cmp (qq a,qq b){    return a.x==b.x?a.id
       
        
         >1; tr[a].s1=num+1;bt(l,mid); tr[a].s2=num+1;bt(mid+1,r);}void update (int now){ int s1=tr[now].s1,s2=tr[now].s2; tr[s1].c+=tr[now].c; tr[s2].c+=tr[now].c; tr[now].c=0;}void change (int now,int l,int r){ //printf("%d %d\n",l,r); if (l>r||l==0) return ; if (tr[now].l==l&&tr[now].r==r) { tr[now].c++; return ; } update(now); int s1=tr[now].s1,s2=tr[now].s2; int mid=(tr[now].l+tr[now].r)>>1; if (r<=mid) change(s1,l,r); else if (l>mid) change(s2,l,r); else change(s1,l,mid),change(s2,mid+1,r);}int ans[N];void dfs (int now,int f){ if (tr[now].l==tr[now].r) { ans[a[tr[now].l]]=ans[a[tr[now].l]]+tr[now].c*f; return ; } update(now); dfs(tr[now].s1,f);dfs(tr[now].s2,f);}void dfs1 (int now,int f){ if (tr[now].l==tr[now].r) { ans[b[tr[now].l]]=ans[b[tr[now].l]]+tr[now].c*f; return ; } update(now); dfs1(tr[now].s1,f);dfs1(tr[now].s2,f);}void solve (){//0:发微博 1:删除 2:加上 if (cnt>=1) { num=0;bt(1,cnt); for (int u=1;u<=m;u++) { if (s[u].c==2)//第一次我只弄减法 continue; //printf("%d %d %d %d %d\n",s[u].c,s[u].x,s[u].y,L[s[u].x],R[s[u].x]); if (s[u].c==0) change(1,L[s[u].x],R[s[u].x]); if (s[u].c==1)//减法 { R[s[u].x]++; R[s[u].y]++; } } dfs(1,-1); } /*for (int u=1;u<=n;u++) printf("%d ",ans[u]); printf("\n");*/ if (cnt1>=1) { num=0;bt(1,cnt1); for (int u=1;u<=m;u++) { if (s[u].c==1)//第一次我只弄加 continue; if (s[u].c==0)//加法 change(1,L1[s[u].x],R1[s[u].x]); if (s[u].c==2) { R1[s[u].x]++; R1[s[u].y]++; } } dfs1(1,1); } for (int u=1;u