CF1042D Petya and Array（cdq分治/数据结构）

题面

有一个长度为 \(n\) 的序列 \(a\) 和一个数 \(t\)，求有多少个区间 \([l,r]\) 满足 \(a_{l}+a_{l+1}+...+a_{r}<t\)。\((n\le 2×10^5,|t|\le 2×10^{14},|a_i|\le 10^9)\)

题解

将题目转化为“求有多少对 \(l,r\) 满足 \(S_r-S_l<t\)"，其中 \(S\) 为前缀和，\(l\in [0,n-1],r\in [1,n]\)。

法1：CDQ分治

当分治到 \([l,r]\) 时

1. 递归求解 \([l,mid]\) 与 \([mid+1,r]\)。
2. 此时 \([l,mid]\) 与 \([mid+1,r]\) 是有序的，用双指针求出 \([l,r]\) 的答案。
3. 将区间 \([l,r]\) 排序。

#include<bits/stdc++.h>
#define int long long
const int maxn = 2e5 + 5;
int n, t, a[maxn], S[maxn];
int ans = 0;

void solve(int l, int r) {
	if(l == r) return ;
	int mid = (l + r) >> 1;
	solve(l, mid); solve(mid + 1, r);
	
	int L = l, R = mid + 1;
	while(L <= mid && R <= r) {
		if(S[L] + t <= S[R]) {
			++L;
		}
		else {
			ans += mid - L + 1;
			++R;
		}
	}
	std::sort(S + l, S + r + 1);
}
signed main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0), std::cout.tie(0);
	std::cin >> n >> t;
	for(int i = 1; i <= n; ++i) {
		std::cin >> a[i];
		S[i] = S[i - 1] + a[i];
	}
	solve(0, n);
	std::cout << ans;
		
	return 0;
} 

法二：权值线段树

CF1042D Petya and Array（cdq分治/数据结构）

原文：https://www.cnblogs.com/hzy1/p/15058618.html