题目描述
给定一个长度为 n nn 的整数数列 和两个整数 x xx、y yy。
请你判断一共有多少个数对 ( l , r ) (l, r)(l,r) 同时满足以下条件：
输入描述
输出描述
输出一个整数，表示满足条件的数对的数量。
示例1#
输入：
5 3 3
4 6 5 3 7
输出：
5
说明：
满足要求的数对一共 5组，分别是 (1,1)、(2,2)、(3,3)、(4,4)、(3,4)
分析
代码
注意 i ii从1开始，那么s [ l − 1 ] s[l - 1]s[l−1]中即从0 00开始，所以事先需要插入 s [ 0 ] s[0]s[0]这个节点。
然后就是套动态开点线段树的模板了。
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 500010; struct node { int l, r; int v, add; }tr[N << 6]; int n, x, y; int a[N], ans, s[N]; int root, idx; int L = -(1ll << 60), R = (1ll << 60); void pushdown(int p, int l, int r) { if(tr[p].add) { int mid = l + r >> 1; tr[tr[p].l].add += tr[p].add, tr[tr[p].l].v += (mid - l + 1) * tr[p].add; tr[tr[p].r].add += tr[p].add, tr[tr[p].r].v += (r - mid) * tr[p].add; tr[p].add = 0; } } void pushup(int p) { tr[p].v = tr[tr[p].l].v + tr[tr[p].r].v; } void modify(int &p, int l, int r, int ql, int qr, int v) { if(!p) p = ++idx; if(l >= ql && r <= qr) { tr[p].add += v; tr[p].v += (r - l + 1) * v; return ; } pushdown(p, l, r); int mid = l + r >> 1; if(ql <= mid) modify(tr[p].l, l, mid, ql, qr, v); if(qr > mid) modify(tr[p].r, mid + 1, r, ql, qr, v); pushup(p); return ; } int query(int p, int l, int r, int ql, int qr) { if(!p) return 0; if(l >= ql && r <= qr) return tr[p].v; int mid = l + r >> 1; pushdown(p, l, r); int res = 0; if(ql <= mid) res += query(tr[p].l, l, mid, ql, qr); if(qr > mid) res += query(tr[p].r, mid + 1, r, ql, qr); return res; } signed main() { cin >> n >> x >> y; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] -= y; s[i] = s[i - 1] + a[i]; } modify(root, L, R, s[0], s[0], 1); for (int i = 1; i <= n; i++) { ans += query(root, L, R, s[i] - x, R); modify(root, L, R, s[i], s[i], 1); } cout << ans << endl; return 0; }
