[数据结构与算法]合适数对——树状数组，离散化

合适数对

题意：

给定一个长度为 $n$ 的整数数列 $a_1,a_2,\dots ,a_n$ 和一个整数 $t$。

请你判断共有多少个数对 $(l,r)$ 同时满足：

• $1\le l\le r\le n$
• $a_l+a_{l+1}+\dots +a_{r?1}+a_r<t$

也就是，统计总和小于 $t$ 的区间个数。
$1\le n\le 2\times 10^5，|t|\le 2\times 10^{14}，|ai|\le 10^9。$

分析：

用前缀和的思想，[l, r] 的区间和可以转化为：$s[r]?s[l?1]$.
那么要求：　$s[r]?s[l?1]<t$
即，　$s[r]?t<s[l?1]$。

那么枚举每个位置 i 作为 r 的话，所要求的便是，当前位置之前一共有多少位置 j 满足： $s[j]>s[i]?t$，$j$ 从 $0$ 开始。

如果我们在数值范围上建立一个树状数组，如果数 $s[i]$ 出现过的话，就让第 $s[i]$ 个位置的值+1。
这样便能够利用前缀和来查询一段区间中一共出现过多少数。

所以对于每个位置 i，都查询从 0 开始的前面所有位置的比 s[i] - t 大的 s[j] 出现次数，答案累加。

	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		ans += query(M) - query(s[i]-m); //得到前面比当前位置比s[i]-m大的个数 
		add(s[i], 1);
	}
	cout << ans;

但是这个数值范围 1e9 太大了，树状数组开不了这么大。但是发现一共 2e5 个位置，那么 s[i] 和 s[i]-t 的种类最多不超过 4e5 个，所以需要先离散化。

离散化的时候要注意：
1.要把所有数离散到从1开始，因为树状数组不好处理0。
2.要把 $s[i]?t$ 一起离散化了，如果只把 $s[i]$ 给离散化了，那 $s[i]?t$ 的值不就乱了？

离散化板子：

vector<int> v; //把所有待离散化的值存起来
sort(v.begin(), v.end()); //排序
v.erase(unique(v.begin(), v.end()), v.end()); //去重

int get(int x){ //得到每个值离散化后的值
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

完整Code：

//https://www.acwing.com/problem/content/4319/
#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

map<int,int> mp;

const int N = 500010, mod = 1e9+7, M = 400000; //最多4e5+2个点 
int T, n, m, k;
int a[N];
vector<int> v;
int c[N], s[N];

int get(int x)
{
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

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

void add(int x, int y){
	for(int i=x;i<=M;i+=lbit(i)) c[i]+=y;
}

int query(int x){
	int sum = 0;
	for(int i=x;i;i-=lbit(i)) sum += c[i];
	return sum;
}

signed main(){
	Ios;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i], s[i]=s[i-1]+a[i];
	
	v.pb(0); //记得把第0个位置放进去 
	v.pb(-m);
	
	for(int i=1;i<n;i++)
	{
		v.pb(s[i]);
		v.pb(s[i]-m);
	}
	
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	add(get(0), 1); //先把第0个位置放进去 
	
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		ans += query(M) - query(get(s[i]-m)); //得到前面比当前位置比s[i]-m大的个数 
		add(get(s[i]), 1);
	}
	cout << ans;
	
	return 0;
} 

练习树状数组很不错的一道题。
但是当时没做出来，只想着用单调队列啥的，没想着转化成前缀和搞。。
还得多练！