区间和2
题意简述
$T$ 组数据。
每次给定长度为 $n$ 的序列，$q$ 组询问，每次询问 $l,r$ ，表示询问 $l-r$ 小的区间和。
$T\leq 10,n\leq 2\times 10^5,q\leq 20$。
时间 $7s$
$solution:$
这种题一看就知道会是差分后二分答案吧，所以现在的问题变为求前 $k$ 小区间和。
设 $S_k=\sum_{i=1}^k a_i$ 。则现在要统计的是 $S_r-x\leq S_{l-1}$ 的个数，和也这样统计即可。
树状数组优化即可，时间复杂度 $O(T\times n\log^2 n\times q)=TLE$ 。
思考哪步能优化，通过简单思考发现 $S_r-x\leq S_{l-1}$ 这个式子 $S$ 是单调递增的，所以直接单调队列优化即可。
时间复杂度 $O(T\times n\log n\times q)$ 。
安全路径
题意简述
给定一棵有 $n$ 个点的树，每条边有颜色。
求满足条件的三元组 $(u,v,w)$ ，满足 $u-v,u-w,v-w$ 之间都有红边经过。
$solution:$
想过容斥原理，但是没有想到可以这么草率。
通过容斥原理我们可以简单的将问题转化为求至少要一对只能走蓝边到达。
我们将只能用蓝边互相到达的放到一个连通块中，设当前考虑的联通块为 $i$ ，其里面数量为 $g$ 。
则 $Ans=\dbinom{n}{3}-\sum_{i=1} \dbinom{g}{3}+(n-g)\times \dbinom{g}{2}$ 。
时间复杂度 $O(n)$ 。
小朋友的笑话
$solution:$
题目告诉了我们说听过 $i$ 号笑话的人再听也不会在笑。
考虑同 $set$ 维护当前听过故事的人，每次只要将要加入的 $l,r$ 与 $set$ 中的元素查交集即可，因为每次将有交集的和为一个整体保证了每个信息只会最多出现两次。
利用线段树维护区间赋值。
时间复杂度 $O(n\log n)$ 。