2022 Henan Mengxin League game (2): Henan University of technology d-pair

D - Number pair

The topic requires us to find satisfaction $al+al+1+\dots +ar-1+ar\le x+y\times (r-l+1)$ Number pair $(l,r)$ Of $(al-y)+(al+1-y)+\dots +(ar-1-y)+(ar-y)\le x$, Make $bi=ai-y$, On the array $b$ Preprocess to get prefix and array $sum$, The formula above
Can become $sumr-suml-1<=x$, And then you get $sumr-x<=suml-1$, such
We can maintain a tree array on the value field , Maintain the number of prefixes and values in front of each
and , Enumerate each right endpoint $r$, Add the answers to the tree array every time, which is greater than or equal to $sumr-x$ Total number of , That is, all the left boundaries that meet the above conditions , And then to $sumr$ The number of this position plus $1$ .

Because the range of values is very large , Tree array cannot be opened , So we need to discretize the prefix and array first .

Time complexity ：$O(nlog(n))$

#include<bits/stdc++.h>
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)// Get the value after discretization 
{
    // The tree array is from 1 At the beginning , So it must be added 1, Ensure that all subscripts are from 1 Start 
	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);// Left boundary l yes 1-n, But what we inquired about is sumr-suml-1, So we need to sum[0] Put it in the discretized array 
	for(int i=1;i<=n;i++)
	{
    // Discretize all prefixes and and values used in subsequent queries , Ensure that the size relationship between them is correct 
		numbers.push_back(a[i]);
		numbers.push_back(a[i]-x);
	}
	sort(numbers.begin(),numbers.end());// Discrete operation 
	numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());
	
	add(get(0),1);// For the same reason, first sum[0] Add to the tree array 
	LL ans=0;
	for(int i=1;i<=n;i++)
	{
    
		ans+=i-query(get(a[i]-x)-1);
		// Find greater than or equal to... In the tree array sumr-x Total number of , That is, the number of left boundary satisfying the condition 
		add(get(a[i]),1);
	}
	printf("%lld\n",ans);
	return 0;
}