2024.8.17-第三题-数组

会员或题库专享

请先，开通会员或购买题库米哈游机考编程题库，可解锁完整内容。

购买米哈游机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（米哈游机考编程题库），可解锁完整内容。

购买题库开通会员

思路:区间容斥计算

首先，据考生反应，这个题目并没有给数据范围，但是 $O(n^2)$ 的复杂度并过不去。那么我们就假设n , q <= 100000。

考虑这种区间问题一般都能用前缀和或者差分来解决。回忆求区间和，我们可以用前缀和 + 差分的方式来解决。

那么这种区间计数的问题，我们可以用前缀和 + 差分的方式来解决吗？

米小游有一个长度为 $n$ 的数组 $a$ ，她会询问 $q$ 次，每次会问你区间 $[l,r]$ 中有多少个连续子数组包含 $x$ 。