提议描述非常清楚，就是求有多少个区间满足区间的和 >= k
依旧是从暴力入手：
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
if s >= k:
cnt += 1
其中，a指的是输入数组，
展开全文
离散化 + 树状数组
求解所有元素之和不小于k的非空区间数量：
求解前缀和
对前缀和进行排序然后离散化
树状数组维护小于s[i] - k的值的数量
因为树状数组需要查询小于s[i] - k的数量，所以离散化时需要把每个s[i] - k一起排序离散化
add(get(0), 1) 把0首先加
展开全文
F. 小红统计区间（hard）
动态开点线段树的板子题, 直接贴板子, 每输入一个 就 update 一下, 查询时, 查询范围 Maxl (左极限值)到 范围的个数.
直接贴代码:
(有没有佬教教我, 成员函数内调用成员函数时, 不通过传入 tr 的引用, 调用 tr 的成员函数, 而是直接调
展开全文
解题思路本题由于原数组a中存在负数，扩大区间范围可能会导致区间和反倒减少，因此不能简单使用滑动窗口。假设已知前缀和数组sum，那么区间和 s[l, r] = sum[r] - sum[l - 1] >= k的必要条件为sum[l - 1] <= sum[r] - k。我们对于每一个右边界
展开全文
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
