题目

给定一个整数数组 $a$，返回区间和在 $[lower, upper]$ 之间的个数，包含 $lower$ 和 $upper$。
区间和 $S(i, j)$ 表示在 $a$ 中，位置从 $i$ 到 $j$ 的元素之和，包含 $i$ 和 $j$ $(i ≤ j)$。

Solution

一个简单的整数问题

题目

第一类指令形如 “C-l-r-d”，表示把数列中第 $l-r$ 个数都加 $d$。

第二类指令形如 “Q-X”，表示询问数列中第 $x$ 个数的值。

题意

$n$ 支队伍一共参加了三场比赛。
一支队伍 $x$ 认为自己比另一支队伍 $y$ 强当且仅当 $x$ 在至少一场比赛中比 $y$ 的排名高。
求有多少组 $(x,y)$，使得 $x$ 自己觉得比 $y$ 强，$y$ 自己也觉得比 $x$ 强，$(x, y)$, $(y, x)$算一组。

solution

题意

给定长度为 $n$ 的数组，$q$ 次询问 $[1,l]+[r,n]$ 组成的新数组中不相同的元素个数。$(1<=n,q<=1e5)$

solution1

一眼莫队题，主要是要想怎么样把它变成一个连续的区间。其实只要把整个数组再复制一遍接上就可以了，则原来查询的 $r$ 变为 $l$，$l$ 变为 $l+n$，区间连续。

题意

给定一个长度为 $(1<=n<=1e5)$ 的数组，$(1<=q<=1e5)$ 次询问查询区间 $[l,r]$ 内 $<=k$ 的元素个数。

solution

考虑树状数组。我们在查询区间 $<=k$ 的个数时，为了更好计数，这个区间应该不包含 $>k$ 的元素才行。因此我们不妨离线，将询问的 $k$ 从小到大排序，将数组也从小到大排序，这样从小到大处理询问，每次处理时只将 $<=k$ 的数挂到树的对应下标上（因为询问的 $k$ 是从小到大的，因此之前树上的数一定比当前询问的 $k$ 要小），维护答案为 $query(r) - query(l-1)$。