辛勤星月

文章
6
资源
1
加入时间
3年2月4天

合适数对——树状数组,离散化

合适数对题意:给定一个长度为 nnn 的整数数列 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​ 和一个整数 ttt。请你判断共有多少个数对 (l,r)(l,r)(l,r) 同时满足:1≤l≤r≤n1≤l≤r≤n1≤l≤r≤nal+al+1+…+ar−1+ar<ta_l+a_{l+1}+…+a_{r−1}+a_r<tal​+al+1​+…+ar−1​+ar​<t也就是,统计总和小于 ttt 的区间个数。1≤n≤2×105,∣t∣