2020 ICPC 威海 H. Message Bomb(差分)

题目链接
题意:
三种操作:
\(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;
}
上一篇:河南十三届ICPC部分题解


下一篇:2020 ICPC 亚洲区域赛 上海站