BZOJ4627: [BeiJing2016]回转寿司

这题调了一晚上快调死了= = 

此题看着很奇怪，我们先搞一搞式子看看它到底要我们求什么

大概是 ∑ⁿ_i=1 [L <= Σ^k_j=i a_i <= R] (k >= i)

发现这可以转成前缀和的形式

就是 ∑ⁿ_i=1 [L <= s[k] - s[j] <= R] (i <= j <= k)

发现它就是求对于每一个 s[k] 满足 s[j] ∈ [s[k] - R, s[k] - L] 的 s[j] 个数

可以权值线段树区间求和搞啊！

然后就是一个裸的线段树了

二分和离散化总容易出一些奇怪的小锅

---

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
#define lson (x << 1)
#define rson ((x << 1) | 1)
using namespace std;
 
typedef long long ll;
const int MAXN = 100005;
 
struct Node{
	ll sum;
}t[(MAXN * 3) << 2];
int n, sizb, rnk[MAXN];
ll lll, rrr, res;
ll num[MAXN], uni[MAXN * 3];
 
inline void pushup(int x) {
	t[x].sum = t[lson].sum + t[rson].sum;
	return;
}
void update(int dst, int l, int r, int x) {
	if(l == r) {
		++t[x].sum;
		return;
	}
	int mid = ((l + r) >> 1);
	if(dst <= mid) update(dst, l, mid, lson);
	else update(dst, mid + 1, r, rson);
	pushup(x);
	return;
}
ll query(int L, int R, int l, int r, int x) {
	if(L > R) return 0ll;
	if(L <= l && r <= R) {
		return t[x].sum;
	}
	int mid = ((l + r) >> 1);
	ll ans = 0ll;
	if(L <= mid) ans = query(L, R, l, mid, lson);
	if(mid < R) ans += query(L, R, mid + 1, r, rson);
	return ans;
}
inline int lower(int l, int r, ll val, ll *arr) {
	register int mid;
	while(l < r) {
		mid = ((l + r) >> 1);
		if(arr[mid] >= val) r = mid;
		else l = mid + 1;
	}
	return l;
}
inline int upper(int l, int r, ll val, ll *arr) {
	register int mid;
	while(l < r) {
		mid = ((l + r + 1) >> 1);
		if(arr[mid] <= val) l = mid;
		else r = mid - 1;
	}
	return l;
}
 
int main() {
	scanf("%d%lld%lld", &n, &lll, &rrr);
	uni[++sizb] = 0ll;
	register ll pres = 0ll;
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &num[i]);
		pres += num[i];
		uni[++sizb] =  pres;
		uni[++sizb] = pres - rrr;
		uni[++sizb] = pres - lll;
	}
	sort(uni + 1, uni + sizb + 1);
	sizb = unique(uni + 1, uni + sizb + 1) - uni - 1;
	pres = 0ll;
	for(int i = 1; i <= n; ++i) {
		pres += num[i];
		rnk[i] = lower_bound(uni + 1, uni + sizb + 1, pres) - uni;
	}
	update(lower_bound(uni + 1, uni + sizb + 1, 0) - uni, 1, sizb, 1);
	pres = 0ll;
	for(int i = 1; i <= n; ++i) {
		pres += num[i];
		int lef = lower(1, sizb, pres - rrr, uni), rig = upper(1, sizb, pres - lll, uni);
		res += query(lef, rig, 1, sizb, 1);
		update(rnk[i], 1, sizb, 1);
	}
	printf("%lld\n", res);
	return 0;
}