Acwing：合适数对

今天在补AcWing周赛题目的时候遇到了一道很经典的区间和问题&＃xff0c;因此写下本篇博客记录下来。

原题链接&＃xff1a;4316. 合适数对 - AcWing题库

 

输入样例1&＃xff1a;

5 4
5 -1 3 4 -1


输出样例1&＃xff1a;

5


输入样例2&＃xff1a;

3 0
-1 2 -3


输出样例2&＃xff1a;

4


输入样例3&＃xff1a;

4 -1
-2 1 -2 3


输出样例3&＃xff1a;

3


题目描述的很简单&＃xff0c;即我们需要统计区间内所有的两个端点&＃xff0c;判断他们闭区间和是否小于t。

那么朴素的思想自然是前缀和了&＃xff0c;但是如果是使用前缀和的话&＃xff0c;我们不可避免的要枚举左右端点&＃xff0c;这是的复杂度&＃xff0c;注意到数据范围达到了&＃xff0c;因此这个做法肯定会TLE。

那么我们就需要挖掘这道题目他的性质了。

首先&＃xff0c;还是与要根据前缀和思想&＃xff0c;记 维护的是前个数字的前缀和&＃xff0c;根据题目要求&＃xff0c;可以写出以下等式&＃xff1a;

 

观察上面第二个式子&＃xff0c;我们发现&＃xff0c;如果我们枚举每一个区间的右端点&＃xff0c;我们只需要统计一下有多少个小于右端点的点的前缀和大于  就行了。

至此&＃xff0c;正解就呼之欲出了 &＃xff1a; 

我们只需要给所有前缀和维护一个树状数组&＃xff0c;每次枚举右端点时&＃xff0c;计算一下之前枚举的点所产生的前缀和中有多少个是小于 的&＃xff0c;然后用已枚举点的数量减去这个值就是我们要统计的对象。

注意到本题取值范围非常大&＃xff0c;而真正需要用到的点也只有2n个 (n对  和  )&＃xff0c;因此需要离散化&＃xff0c;使取值范围属于

#include
#include
#include
#include
using namespace std ;
const int N &＃61; 4e5 &＃43; 10 ;
typedef long long LL ;
int n, tr[N] ;
LL s[N], t ; // 前缀和数组
vector nums ; // 离散化数组
int lowbit(int x)
{
return x & -x ;
}
void add(int x, int v)
{
for (int i &＃61; x ; i tr[i] &＃43;&＃61; v ;
}
int sum(int x)
{
int res &＃61; 0 ;
for (int i &＃61; x ; i ; i -&＃61; lowbit(i))
res &＃43;&＃61; tr[i] ;
return res ;
}
int get(LL x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin() &＃43; 1 ;
}
int main()
{
cin >> n >> t ;
for (int i &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43; )
{
int x ;
cin >> x ;
s[i] &＃61; s[i - 1] &＃43; x ;
}

for (int i &＃61; 0 ; i <&＃61; n ; i &＃43;&＃43; )
{
nums.push_back(s[i]) ;
nums.push_back(s[i] - t) ;
}

sort(nums.begin(), nums.end()) ;
nums.erase(unique(nums.begin(), nums.end()), nums.end()) ;

LL res &＃61; 0 ;
add(get(s[0]), 1) ;

for (int i &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43; )
{
res &＃43;&＃61; i - sum(get(s[i] - t)) ;
add(get(s[i]), 1) ;
}

cout <
return 0 ;
}