合肥比较好的网站制作,什么是网站地址,网站推广方式介绍,长春网站建设首选网诚传媒P5459 [BJOI2016] 回转寿司 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
酷爱日料的小Z经常光顾学校东门外的回转寿司店。在这里#xff0c;一盘盘寿司通过传送带依次呈现在小Z眼前。
不同的寿司带给小Z的味觉感受是不一样的#xff0c;我们定义小Z对每盘寿司…P5459 [BJOI2016] 回转寿司 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
酷爱日料的小Z经常光顾学校东门外的回转寿司店。在这里一盘盘寿司通过传送带依次呈现在小Z眼前。
不同的寿司带给小Z的味觉感受是不一样的我们定义小Z对每盘寿司都有一个满意度。
例如小Z酷爱三文鱼他对一盘三文鱼寿司的满意度为10小Z觉得金枪鱼没有什么味道他对一盘金枪鱼寿司的满意度只有 5小Z最近看了电影《美人鱼》被里面的八爪鱼恶心到了所以他对一盘八爪鱼刺身的满意度是 −100。
特别地小Z是个著名的吃货他吃回转寿司有一个习惯我们称之为“狂吃不止”。具体地讲当他吃掉传送带上的一盘寿司后他会毫不犹豫地吃掉它后面的寿司直到他不想再吃寿司了为止。
今天小Z再次来到了这家回转寿司店N 盘寿司将依次经过他的面前。其中小Z对第 i 盘寿司的满意度为ai。
小Z可以选择从哪盘寿司开始吃也可以选择吃到哪盘寿司为止。他想知道共有多少种不同的选择使得他的满意度之和不低于 L且不高于 R。
注意虽然这是回转寿司但是我们不认为这是一个环上的问题而是一条线上的问题。即小Z能吃到的是输入序列的一个连续子序列最后一盘转走之后第一盘并不会再出现一次。
输入格式
第一行三个正整数 N,L,R表示寿司盘数满意度的下限和上限。 第二行包含 N 个整数ai表示小Z对寿司的满意度。
输出格式
一行一个整数表示有多少种方案可以使得小Z的满意度之和不低于L 且不高于 R。
输入输出样例
输入 #1复制
5 5 9
1 2 3 4 5
输出 #1复制
6
说明/提示
【数据范围】
1≤N≤105 ∣ai∣≤105 0≤L,R≤109
解析离散化树状数组
关于题目的意思既是让我们求有多少个连续的区间满足
Lpre[r]-pre[l]R
其中pre是输入数组的前缀和
我们将上述不等式转化为
pre[r]-Rpre[l]pre[r]-L;
这样我们就可以将上式用树状数组实现
在区间pre[r]-Rpre[r]-L】内满足上式的pre[l]的个数
但注意有意可能出现负数和数字很大我们需要将上面的数据进行离散化处理 #includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemapusing namespace std;
typedef long long LL;
const int N 1e5 5;LL n, L, R, cnt;
LL sum[N], arr[3 * N];
LL C[3*N];int cmp(const LL a, const LL b) {return a b;
}void add(int x, int d) {for (; x cnt; x x -x) {C[x] d;}
}LL ask(int x) {LL ret 0;for (; x; x - x -x) {ret C[x];}return ret;
}int main() {cin n L R;for (int i 1; i n; i) {scanf(%lld, sum[i]);sum[i] sum[i - 1];}cnt 1;for (int i 1; i n; i) {arr[cnt] sum[i];arr[cnt] sum[i] - R;arr[cnt] sum[i] - L;}sort(arr 1, arr 1 cnt, cmp);cnt unique(arr 1, arr 1 cnt) - arr-1;add(lower_bound(arr 1, arr 1 cnt, 0) - arr, 1);LL ans 0;for (int i 1; i n; i) {int l lower_bound(arr 1, arr 1 cnt, sum[i] - R) - arr; //使用 lower_bound 查找第一个大于或等于 sum[i] 的元素位置int r lower_bound(arr 1, arr 1 cnt, sum[i] - L) - arr;//upper_bound 则是查找第一个大于 value 的元素位置ans ask(r) - ask(l - 1);int x lower_bound(arr 1, arr 1 cnt, sum[i]) - arr;add(x, 1);}cout ans endl;return 0;
}
