当前位置：首页 > news >正文

[线段树] 回转寿司

news 来源：原创 2025/6/26 4:16:23

题目描述

酷爱日料的小 $Z$ 经常光顾学校东门外的回转寿司店。在这里，一盘盘寿司通过传送带依次呈现在小Z眼前。

不同的寿司带给小Z的味觉感受是不一样的，我们定义小 $Z$ 对每盘寿司都有一个满意度。

例如小 $Z$ 酷爱三文鱼，他对一盘三文鱼寿司的满意度为 $10$ ；小 $Z$ 觉得金枪鱼没有什么味道，他对一盘金枪鱼寿司的满意度只有 $5$ ；小Z最近看了电影《美人鱼》，被里面的八爪鱼恶心到了，所以他对一盘八爪鱼刺身的满意度是 $- 100$ 。

特别地，小 $Z$ 是个著名的吃货，他吃回转寿司有一个习惯，我们称之为“狂吃不止”。具体地讲，当他吃掉传送带上的一盘寿司后，他会毫不犹豫地吃掉它后面的寿司，直到他不想再吃寿司了为止。

今天，小Z再次来到了这家回转寿司店， $N$ 盘寿司将依次经过他的面前。其中，小 $Z$ 对第 $i$ 盘寿司的满意度为 $a_i$ 。
小 $Z$ 可以选择从哪盘寿司开始吃，也可以选择吃到哪盘寿司为止。他想知道共有多少种不同的选择，使得他的满意度之和不低于 $L$ ，不高于 $R$ 。

注意，虽然这是回转寿司，但是我们不认为这是一个环上的问题，而是一条线上的问题。即，小 $Z$ 能吃到的是输入序列的一个连续子序列；最后一盘转走之后，第一盘并不会再出现一次。

输入格式

第一行三个正整数 $N, L, R$ ，表示寿司盘数，满意度的下限和上限。
第二行包含 $N$ 个整数 $a_i$ ，表示小 $Z$ 对寿司的满意度。

输出格式

一行一个整数，表示有多少种方案可以使得小 $Z$ 的满意度之和不低于 $L$ ，不高于 $R$ 。

样例

样例输入1：

5 5 9
1 2 3 4 5

样例输出1：

数据范围

$\le N \le 10^5$
$\lvert a_i \rvert \le 10^5$
$\le L, R \le 10^9$

题解

如果直接暴力枚举左端点和右端点进行求解，复杂度为 $O(n^2)$ ，显然不能通过此题。

考虑只枚举左端点和右端点中的一个。
固定右端点 $r$ ，假设左端点为 $l$ 。
则答案应满足 $\le \sum_{i=l}^{r}a_i \le R$ 。
用前缀和来表示： $\le s_r - s_{l - 1} \le R$ 。
先看左边 $\le s_r - s_{l - 1}$ ，将 $L$ 移到右边， $s_{l - 1}$ 移到左边，得到 $s_{l - 1} \le s_r - L$ 。
同理，对右边进行移项，得到 $s_r - R \le s_{l - 1}$ 。
因此， $l$ 需要满足 $sum_r - R \le sum_{l - 1} \le sum_{r} - L$ 。

将前缀和用 值域线段树 + 动态开点 进行维护，枚举到 $i$ 时，先查询在上式范围内的 $s u m$ 的个数，再将 $sum_i$ 加入线段树。

ll,rr 为 L 和 R，其余同上文
struct node{long long l, r;//左右孩子编号int p;//值
}tr[3000010];//线段树
int cnt = 1;//总节点数
void insert(long long &bh, long long l, long long r, long long pp){//插入if(bh == 0){bh = ++ cnt;//增加点}if(l == r){//边界tr[bh].p ++;return;}long long mid = (l + r) >> 1;if(pp <= mid){insert(tr[bh].l, l, mid, pp);}else{insert(tr[bh].r, mid + 1, r, pp);}tr[bh].p = tr[tr[bh].l].p + tr[tr[bh].r].p;
}
long long query(int bh, long long l, long long r, long long x, long long y){//查询if(x <= l && r <= y){return tr[bh].p;}long long mid = (l + r) >> 1, s = 0;if(x <= mid && tr[bh].l){s += query(tr[bh].l, l, mid, x, y);}if(y > mid && tr[bh].r){s += query(tr[bh].r, mid + 1, r, x, y);}return s;
}输入并求前缀和
long long t = 1;//因为引用
insert(t, -1e10, 1e10, 0);
for(int i = 1; i <= n; ++ i){long long p = query(t, -1e10, 1e10, sum[i] - rr, sum[i] - ll);//查询ans += p;insert(t, -1e10, 1e10, sum[i]);//加入
}

题目描述

输入格式

输出格式

样例

数据范围

题解

相关文章：