题目链接
题意:
三种操作:
\(t\) \(a\) \(b\)
\((1)\)\(t=1\)时,\(a\)加入团体\(b\)
\((2)\)\(t=2\)时,\(a\)离开团体\(b\)
\((3)\)\(t=3\)时,\(a\)在团体\(b\)发送一条消息,团队中除自己外的人都能接收到。
求每个人接收到的消息条数。
思路:
\(set\)+差分。
\(set[i]\)保存团体\(i\)中的人员。
\(sum[i]\)表示当前团体\(i\)接收到的消息数,若\(k\)在时刻\(t_1\)加入团体\(i\),在\(t_2\)时离开团体\(i\)(中途\(k\)没有发消息),则接收到的消息数\(=sum[i](t2时刻)-sum[i](t1时刻)\)。
最后遍历所有的\(set\)集合,更新结束时还没有离开团体的人员接收到的消息数。
code:
#include <iostream>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
set<int> st[maxn];
int n, m, s;
int ans[maxn], sum[maxn];
int main(){
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i <= s; i ++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a == 1){
ans[b] -= sum[c];
st[c].insert(b);
}
else if(a == 2){
ans[b] += sum[c];
st[c].erase(b);
}
else{
ans[b] --;
sum[c] ++;
}
}
for(int i = 1; i <= n; i ++){
for(int k : st[i])ans[k] += sum[i];
}
for(int i = 1; i <= m; i ++)printf("%d\n", ans[i]);
return 0;
}