D - 数对

题目要求我们找出满足 $al+al+1+\dots +ar-1+ar\le x+y\times (r-l+1)$ 数对 $(l,r)$ 的 $(al-y)+(al+1-y)+\dots +(ar-1-y)+(ar-y)\le x$，令 $bi=ai-y$，在对数组 $b$ 进行预处理得到前缀和数组 $sum$，上面的公式
又可以变成 $sumr-suml-1<=x$，进而得到 $sumr-x<=suml-1$，这样
我们就可以在值域上维护一个树状数组，维护每个前面的前缀和数值的个数的
和，枚举每个右端点 $r$，每次将答案累加上树状数组中大于等于 $sumr-x$ 的总个数，也就是所有满足上述条件的左边界，然后再给 $sumr$ 这个位置的个数加上 $1$ 。

由于值域很大很大，树状数组开不下，所以我们要先将前缀和数组离散化。

时间复杂度：$O(nlog(n))$

#include
using namespace std;

typedef long long LL;
const int N = 200010;

int n;
LL a[N],x,y;
int tr[N*2];
vector<LL> numbers;

int lowbit(int x)
{
	return x&-x;
}

void add(int x,int v)
{
	for(int i=x;i<=(int)numbers.size();i+=lowbit(i))
		tr[i]+=v;
}

int query(int x)
{
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
		ans+=tr[i];
	return ans;
}

int get(LL x)//获取离散化之后的值
{//树状数组是从1开始的，所以一定要加1，保证所有下标从1开始
	return lower_bound(numbers.begin(),numbers.end(),x)-numbers.begin()+1;
}

int main()
{
	scanf("%d%lld%lld",&n,&x,&y);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) a[i]+=a[i-1]-y;
	
	numbers.push_back(0);//左边界l是1-n，但是我们查询的是sumr-suml-1，所以要把sum[0]放到离散化数组中
	for(int i=1;i<=n;i++)
	{//将所有前缀和以及后续询问用到的数值全部离散化，保证他们之间的大小关系正确
		numbers.push_back(a[i]);
		numbers.push_back(a[i]-x);
	}
	sort(numbers.begin(),numbers.end());//离散化操作
	numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());
	
	add(get(0),1);//同样的道理先将sum[0]加到树状数组中
	LL ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=i-query(get(a[i]-x)-1);
		//求树状数组中大于等于sumr-x的总个数，即满足条件左边界的个数
		add(get(a[i]),1);
	}
	printf("%lld\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61