合适数对

[Link](4316. 合适数对 - AcWing题库)

题意

思路

• 树状数组

设$s_i$为$a_i$的前缀和，等价于$s_r-s_{l-1}<t\to s_r-t<s_{l-1}$，就是对于每一个$s_i$找$s_0到s_{i-1}$中有多少个大于$s_r-t$的数，由于值域太大我们先对所有可能用到的数进行离散化，然后对值域进行动态前缀和即可。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 4e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
LL n, m, k, t;
vector<LL> ve;
int g(LL x) {return lower_bound(ve.begin(), ve.end(), x) - ve.begin() + 1;
}
int tr[N];
int lowbit(int x) {return x & -x;
}
void add(int x) {for ( ; x < N; x += lowbit(x)) tr[x] ++;
}
int sum(int x) {int res = 0;for (; x; x -= lowbit(x)) res += tr[x];return res;
}
int main() {ios::sync_with_stdio(false), cin.tie(0);cin >> n >> t;vector<LL> s(n + 1);for (int i = 1; i <= n; i ++) cin >> s[i], s[i] += s[i - 1], ve.push_back(s[i]), ve.push_back(s[i] - t);ve.push_back(0), ve.push_back(-t);sort(ve.begin(), ve.end());ve.erase(unique(ve.begin(), ve.end()), ve.end());LL res = 0;add(g(0));for (int i = 1; i <= n; i ++) {res += i - sum(g(s[i] - t));add(g(s[i]));}cout << res << '\n';return 0;
}

• 归并排序

我们要找的是$s_r-s_l<t$的数有多少个，仿照归并排序求逆序对的方法，对于两个有序的数组$a,b$我们可以这样划分方案，对于$a$中的每个位置$i$，$b$中有多少个位置与之合法，当$i->i+1$时相当于$s_l$增大，因此之前成立的$b$中的位置依旧成立因此类似于双指针的感觉我们可以$O(n)$的维护每个区间的贡献，复杂度$O(nlogn)$。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
LL n, m, k, t;
LL a[N];
LL res;
void merge(int l, int r) {if (l >= r) return ;int mid = l + r >> 1;merge(l, mid), merge(mid + 1, r);    for (int i = l, j = mid + 1; i <= mid; i ++) {while (j <= r && a[j] - a[i] < t) j ++;res += j - mid - 1;}inplace_merge(a + l, a + mid + 1, a + r + 1);
}
int main() {ios::sync_with_stdio(false), cin.tie(0);cin >> n >> t;for (int i = 1; i <= n; i ++) cin >> a[i], a[i] += a[i - 1];merge(0, n);cout << res << '\n';return 0;
}