首页 > 代码库 > bzoj1878 [SDOI2009]HH的项链
bzoj1878 [SDOI2009]HH的项链
1878: [SDOI2009]HH的项链
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 3199 Solved: 1611
[Submit][Status][Discuss]
Description
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此， 他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同 的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解 决这个问题。
Input
第一行：一个整数N，表示项链的长度。 第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。 第三行：一个整数M，表示HH询问的个数。 接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
Output
M行，每行一个整数，依次表示询问对应的答案。
Sample Input
6
1 2 3 4 3 5
3
1 2
3 5
2 6
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output
2
2
4
2
4
HINT
对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。
Source
Day2
分析：看到区间求数量，似乎可以用线段树解决，但是颜色的数量不能直接相加，故用线段树处理有些麻烦，如果不用线段树解决的话所有询问最好都是有序的，因此先按照左端点排序.
如果我们询问区间[x,y],那么如果有一个颜色重复出现了多次，那么只需要计算一次即可，那么就要把区间内所有重复的颜色看成一个，具体是哪一个呢？因为要选一个特殊的点，那么一定要选一个特殊的位置，那么我们选择从左边出现的第一个，记为i,如果i的左边还有与i相同的颜色，那么一定在区间[x,y]之外，因为要求个数，那么就把区间[x,y]左边的颜色的下一个相同颜色的位置+1即可，因为是按照左端点排序的，所以不会重复计算,因为涉及到大量的区间计算，所以用到树状数组和前缀和，说的比较抽象，看一组数据：1 2 1 3，树状数组为：0 0 0 0,首先发现了第一个1，树状数组变成1 0 0 0,然后发现了2，变成了1 1 0 0,然后发现了1，变成了0 1 1 0,然后发现了3，变成0 1 1 1,对于一个询问[2,3],那么答案就是sum(3) - sum(2 - 1).那如果是求[1,1]呢？现在的答案是0！怎么办？其实根据之前的叙述，每次只需要考虑区间[x,y]左边的颜色即可,不好描述，如果不能理解请手动模拟几组数据就能找到规律了.
推荐一篇学习树状数组的博客：http://blog.csdn.net/int64ago/article/details/7429868
#include <cstdio>#include <vector>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 50010, maxm = 200010, maxk = 1000010;struct node{ int x, y, id;}a[maxm];int n,f[maxn],nextt[maxk],head[maxk],tempmax,s[maxn],m,ans[maxm];bool cmp1(node p, node q){ return p.x < q.x; if (p.x == q.x) return p.y < q.y;}void add(int x, int y){ for (;x <= n; x += x&-x) s[x] += y;}int query(int x){ int temp = 0; for (;x;x -= x&-x) temp += s[x]; return temp;}int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &f[i]); for (int i = n; i >= 1; i--) { nextt[i] = head[f[i]]; head[f[i]] = i; tempmax = max(tempmax, f[i]); } scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &a[i].x, &a[i].y); a[i].id = i; } sort(a + 1, a + 1 + m, cmp1); for (int i = 1; i <= tempmax; i++) if (head[i]) add(head[i], 1); int cursor = 1; for (int i = 1; i <= m; i++) { while (cursor < a[i].x) { if (nextt[cursor]) add(nextt[cursor], 1); cursor++; } ans[a[i].id] = query(a[i].y) - query(a[i].x - 1); } for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0;}
bzoj1878 [SDOI2009]HH的项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。