gym344448C线段树/树状数组 离线查询区间小于等于k的数的数量
题目
求解
其实就是求
$\sum_{i=1}^{n}\sum_{j=i+1}^{n} a_i+i>=j{&&} j-a_j<=i$
两个条件可以写成:$j<=a_i+i&&j-a_j<=i$
问题转化为,对于每个$a_i$,要查询区间$[i+1,a_i+i]$有多少数满足$j-a_j<=i$
将$j-a_j$作为新值,也就是查询区间小于等于$k$的数的数量。在线查询可以用二分主席树等求解,这题没有强制在线,可以将询问按照k值从小到大排序,每次插入新值,用树状数组查询区间数量。
代码:
1 |
|
其实也可以按照$a_i$从大到小插入,然后区间查询即可。这样一来,当前插入的点可以碰到的点前面插入的点也一定可以碰到该点。