洛谷 P3998 [SHOI2013]发微博
题目描述
刚开通的 SH 微博共有n个用户（1Ln标号），在这短短一个月的时间内，
用户们活动频繁，共有m 条按时间顺序的记录：
! x 表示用户x发了一条微博；
+ x y 表示用户x和用户y成为了好友
− x y 表示用户x和用户y解除了好友关系
当一个用户发微博的时候，所有他的好友（直接关系）都会看到他的消息。
假设最开始所有人之间都不是好友关系，记录也都是合法的（即+ x y时x和
y一定不是好友，而− x y时x和y一定是好友）。
问这 m 条记录发生之后，每个用户分别看到了多少条消息。
输入格式
第 1行 2个整数n,m。
接下来m 行，按时间顺序读入m 条记录，每条记录的格式如题目所述，用
空格隔开。
输出格式
输出一行 n 个用空格隔开的数（行末无空格），第i 个数表示用户i 最后看到
了几条消息。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
n<=200000
m<=500000
题解：
2019双十模拟赛（蒟蒻正在文化课月考的考场上瑟瑟发抖）
后来7哥@littleseven带我做了这道题...
当时只想出了50分的暴力思路，非常容易想，就是开一个数组\(f[i] [j]\)（开bool数组，可以节约一些空间，让其能开到\(10^8\)），表示\(i\)，\(j\)是不是朋友。然后每次有人发消息，就把它的所有朋友的答案\(+1\)。
50pts代码如下：
#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
bool f[10000][10000];
int ans[10000];
int main()
{
// freopen("qq.in","r",stdin);
// freopen("qq.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
char ch;
cin>>ch;
if(ch=='+')
{
scanf("%d%d",&x,&y);
f[x][y]=1,f[y][x]=1;
}
else if(ch=='-')
{
scanf("%d%d",&x,&y);
f[x][y]=0,f[y][x]=0;
}
else
{
scanf("%d",&x);
for(int j=1;j<=n;j++)
if(f[x][j])
ans[j]++;
}
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
然后介绍一下正解。
其实我上面的暴力思路如果再深入一下也就是正解了，思路都是：记录朋友，累加答案。那么，为什么上面的代码叫暴力，下面的代码叫正解，就是因为复杂度不一样。正解可以跑更大的数据。所以通过这道题，还能教会我们在考场上的一个答题技巧：当我们只能想出暴力思路的时候，想一想怎么通过已知手段优化暴力算法，说不定搞一搞正解就出来了。
闲话少叙，直奔主题：
我们已经得出了暴力的思路：记录朋友，累加答案。我们刚刚采用的记录朋友的办法是开矩阵数组。但这样肯定开不下空间（\(n\le 2\times 10^5\)）。于是我们开始想：什么东西可以使得我们对\(1-n\)每个人都记录一个序列，同时做到方便地加入和删除呢？
\(STL\)大法：\(set\)容器。
使用了\(set\)的代码就变成了80分，剩下的两个点\(TLE\)了。
80pts代码如下：
#include<cstdio>
#include<iostream>
#include<set>
using namespace std;
const int maxn=2*1e5+1;
int n,m;
set<int> s[maxn];
set<int>::iterator it;
int ans[maxn];
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0,f=1;
char ch=nc();
while(ch<48){if(ch=='-')f=-1;ch=nc();}
while(ch>47) x=x*10+ch-'0',ch=nc();
return x*f;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int x,y;
char ch=nc();
if(ch=='+')
{
x=read();y=read();
s[x].insert(y);
s[y].insert(x);
}
else if(ch=='-')
{
x=read();y=read();
s[x].erase(y);
s[y].erase(x);
}
else
{
x=read();
for(it=s[x].begin();it!=s[x].end();it++)
ans[*it]++;
}
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
加了读入优化，然而并没有用......
那我们继续去想......
因为\(TLE\)了，那么显然是统计答案时出的问题。80分的思路统计答案的时候使用迭代器从头到尾给\(x\)的每个答案\(+1\)，这种复杂度差不多是\(O(n\times m)\)显然是不行的。
那么我们这样考虑：既然一次加一个不行，我们就一次加一堆。
具体实现的原理是这样的：
设想一下，现在你是个包工头，有一个人要给你打工，工钱每天一块钱。然后有一天这个人不干了，于是你把他这些天的工钱一起结算给他，你们愉快地一拍两散~
迁移到这道题：当你每次更博的时候，就相当于工地干了一天活，你要给你的工人们（朋友）发一块钱的工资。你觉得一天一结算太麻烦，于是你记录下来了每个工人第一天来上班的日子和退休的日子，然后一起把钱结算给它们。
这是个差分思想么！
我们开一个数组\(cnt[i]\)，表示截止到目前，\(i\)已经发了多少条微博。当一个人加了\(i\)的好友，那么就记录这个人什么时候加的\(i\)，具体实现方法是把\(cnt[i]\)减掉，什么时候删除了\(i\)的好友，再把删除时的\(cnt[i]\)加回来。这样，\(cnt[i_1]\)和\(cnt[i_2]\)的差就代表了这个人成为\(i\)的好友的这一段时间内接收的微博数量。
当然，这样处理完\(m\)个询问的时候，还会有一些人仍然是其他人的好友。而我们的这个算法只在删除好友的时候统计答案。这就相当于工地有一天倒闭了，但是有一些工人仍在跟着你，你就算当裤子也必须得给他们发钱。
这道题不需要我们当裤子，只需要在处理完\(m\)个操作之后再加双层\(for\)循环强制统计答案即可。
（个人认为这个比喻好形象啊，如果你认为这对你的理解有所帮助，那我顺手求个推荐和好评~）
100pts代码如下：
#include<cstdio>
#include<set>
#include<iostream>
using namespace std;
const int maxn=2*1e5+1;
int n,m;
int cnt[maxn],ans[maxn];
set<int> s[maxn];
set<int>::iterator it;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
char opt;
cin>>opt;
int x,y;
if(opt=='!')
{
scanf("%d",&x);
cnt[x]++;
}
else if(opt=='+')
{
scanf("%d%d",&x,&y);
ans[x]-=cnt[y];
ans[y]-=cnt[x];
s[x].insert(y);
s[y].insert(x);
}
else
{
scanf("%d%d",&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++)
printf("%d ",ans[i]);
return 0;
}