Day6 - A - HH的项链 HYSBZ - 1878
2024-08-29 22:41:58
------------恢复内容开始------------
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一
段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此他的项链变得越来越长。有一天,他突然提出了一
个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只
好求助睿智的你,来解决这个问题。
Input
第一行:一个整数N,表示项链的长度。
第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。
第三行:一个整数M,表示HH询问的个数。
接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。
N ≤ 50000,M ≤ 200000。
Output
M行,每行一个整数,依次表示询问对应的答案。
Sample Input6 1 2 3 4 3 5 3 1 2 3 5 2 6
Sample Output2 2 4
思路:离线操作,将r排序,利用树状数组快速求和,维护一个pre数组,在i加入时,pre[i]就要减1
#define lowbit(x) ((x)&(-x))
typedef long long LL; const int maxm = 1e6+;
const int maxn = 5e4+; int C[maxn], pre[maxm], N, M, a[maxn], ans[]; struct Node {
int l, r, id;
bool operator<(const Node &t)const {
return r < t.r;
}
}query[]; void add(int x, int val) {
for(; x <= N; x += lowbit(x))
C[x] += val;
} int getsum(int x) {
int ret = ;
for(; x; x -= lowbit(x))
ret += C[x];
return ret;
} int main() {
scanf("%d", &N);
for(int i = ; i <= N; ++i)
scanf("%d", &a[i]);
scanf("%d", &M);
for(int i = ; i < M; ++i) {
scanf("%d%d", &query[i].l, &query[i].r);
query[i].id=i;
} sort(query, query+M);
int k = ;
for(int i = ; i < M; ++i) {
int j = query[i].r;
for(; k <= j; ++k) {
if(pre[a[k]])
add(pre[a[k]], -);
add(k, );
pre[a[k]] = k;
}
ans[query[i].id] = getsum(j) - getsum(query[i].l-);
}
for(int i = ; i < M; ++i)
printf("%d\n", ans[i]);
return ;
}
------------恢复内容结束------------
最新文章
- Win8.1 安装Express 框架
- IOS 使用KBMMW 访问JAVA 服务
- xss漏洞挖掘小结
- HDU 1828 / POJ 1177 Picture --线段树求矩形周长并
- phalcon: 过滤(Phalcon\Filter())
- 为设计师准备的 20 个新的免费 PSD 模板
- Nginx Location配置语法介绍、优先级说明
- CentOS用yum安装X Window
- 为什么虚拟机上刚装的centos7只有lo回环网络接口?
- php的一些基本概念梳理
- 技术七Gitservergitolite要构建和操作方便
- 打开phpmyadmin显示高级功能尚未完全设置部分功能未激活
- 初次接触java中的递归算法
- poj 2892---Tunnel Warfare(线段树单点更新、区间合并)
- 极化码的matlab仿真(1)——参数设置
- Maven合并多个war包的工程需要用到的插件
- 靠谱好用,ANDROID SQLITE 增删查改
- 在Ubuntu中部署并测试HyperLedger Fabric 0.6
- 如何禁止复制电脑文件到U盘、禁止U盘拷贝文件
- matplot绘图