类似求逆序对个数的题目,需要离散化。
题意
问你有多少段区间满足a[l] + a[..] +a[r] < t
思路
实际上就是求sum[r] - sum[l] < t ,我们可以遍历r,然后利用权值线段树求有多少个l满足sum[r] - t< sum[l]。
需要注意的一点是,如果getid越界的话,就只是Update就行。
在POJ里没有判断越界也过了,结果CF上就过不了,数据真的强呀!
1 |
|
云腾致雨,露结为霜
类似求逆序对个数的题目,需要离散化。
问你有多少段区间满足a[l] + a[..] +a[r] < t
实际上就是求sum[r] - sum[l] < t ,我们可以遍历r,然后利用权值线段树求有多少个l满足sum[r] - t< sum[l]。
需要注意的一点是,如果getid越界的话,就只是Update就行。
在POJ里没有判断越界也过了,结果CF上就过不了,数据真的强呀!
1 | #include <iostream> |