D Friend Suggestions
题面
某平台有 $n$ 个用户 , 有 $m$ 对是互相关注的 , 有 $k$ 对是互相拉黑的 .
对于用户 $i$ 和 $j$ , 当 $i$ 和 $j$ 满足以下条件时 , $j$ 就是 $i$ 的 “ 推荐用户 “ :
$i$ 和 $j$ 可以通过若干对互相关注的用户连接起来 .
$i$ 和 $j$ 没有互关或者互黑 .
求每位用户的 “ 推荐用户 “ 的数量.
解题思路
并查集再加上容斥原理 . 统计有多少人有 “ 推荐用户 “ 关系 , 多少人不能有该关系 , 根据容斥原理 , 答案就是不考虑条件 2 的每个用户的 “ 推荐用户 “ 的数量 , 再扫一遍互关和互黑的人 , 如果连同 , 答案把 ta 们的 “ 推荐用户 “ -1 .
E Simple String Queries
题面
给定长度为 $n$ 的字符串 $S$ , 以及 $Q$ 次询问 . 其格式如下 :
输入 1 $i_q$ , $c_q$ , 将 $S$ 的第 $i_q$ , 位字符改为 $c_q$ ;
输入 2 , $l_q$ , $r_q$ , 询问区间 $[l , r]$ 不同的字符个数 .
解题思路
开 26 个独立的树状数组 , 每一个存放该字符出现的位置 . 在询问的时候直接询问树状数组 $[l,r]$ 的和 ( $ans$ ) , 如果 $ans > 0$ , 则把 $ans + 1$ 输出即可 .