【题目描述】
和又在研究Gty的妹子序列了!但他们遇到了一个难题 。
对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数 。
为了方便,我们规定妹子们的美丽度全都在[1,n]中 。
给定一个长度为n(1≤n≤)的正整数序列s(1≤si≤n),对于m(1≤m≤)次询问“l,r,a,b”,每次输出sl...sr中,权值∈[a,b]的权值的种类数 。
【bzoj3809:Gty的二逼妹子序列】【输入】
第一行包括两个整数n,m(1≤n≤,1≤m≤),表示数列s中的元素数和询问数 。
第二行包括n个整数s1...sn(1≤si≤n) 。
接下来m行,每行包括4个整数l,r,a,b(1≤l≤r≤n,1≤a≤b≤n),意义见题目描述 。
保证涉及的所有数在C++的int内 。
保证输入合法 。
【输出】
对每个询问,单独输出一行,表示sl...sr中权值∈[a,b]的权值的种类数 。
【输入样例】
10 104 4 5 1 4 1 5 1 2 15 9 1 23 4 7 94 4 2 52 3 4 75 10 4 43 9 1 11 4 5 98 9 3 32 2 1 68 9 1 4
【输出样例】
2002111012
【提示】
v>样例的部分解释:
5 9 1 2
子序列为4 1 5 1 2
在[1,2]里的权值有1,1,2,有2种,因此答案为2 。
3 4 7 9
子序列为5 1
在[7,9]里的权值有5,有1种,因此答案为1 。
4 4 2 5
文章插图
子序列为1
没有权值在[2,5]中的,因此答案为0 。
2 3 4 7
子序列为4 5
权值在[4,7]中的有4,5,因此答案为2 。
建议使用输入/输出优化 。
题解:
莫队,将询问以左端点所处块的位置为第一关键字,右端点位置为第二关键字排序,保证对于左端点在同一块内的所有询问,其右端点单增
然后对权值分块,即可O(1)修改,O(sqrt(n))查询
#include
View Code
- 交换机维修维保:交换机常见的故障解决办法
- 全球人工智能高峰论坛演讲实录 王坚眼中的互联网、数据和AI
- 哭了,软件测试面试中十有八九会问到的问题,后悔没有早知道
- 橄榄树丰产的栽培技术
- 【CVPR2019】“识面知心”——基于自监督学习的微表情特征表达
- fastica和pca区别_ICA与PCA的区别
- 辣椒落叶的原因是什么
- 解决 Ubuntu cherry键盘 三键同时按切换大写的问题
- 大姜死苗的原因
- bzoj 3720 Gty的妹子树