关键字：区间种类询问。
Link&Limit
[洛谷1972] [codevs2307] [BZOJ1878]
时间限制：1000ms 空间限制：262144kb
Description
HH 有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链 实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
Input Format
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
Output Format
M 行，每行一个整数，依次表示询问对应的答案。
Sample Input #1
6
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output #1
2
2
4
Hint
对于100%的数据，N <= 50000，M <= 200000.
首先，对于无修改的离线区间询问问题，一定有一个O(n^1.5)的算法——莫队算法可以解决。莫队算法的详细内容请参考：http://blog.csdn.net/bossup/article/details/39236275
然而，我们也可以用树状数组非常巧妙地解决这个问题。先把所有区间按照右端点从小到大排序，我们只需要找到某一种贝壳最后出现的位置，就能不重不漏地统计 区间内贝壳的种数。因为右端点已经排序，所以如果连最后出现的位置都不在区间内，那么该贝壳一定不在区间内。
这样，我们在回答询问时，只需要不断维护某种贝壳最后出现的位置即可。
本题做为一道区间种类询问的模版题，两种方法都非常值得学习。
#include <stdio.h>
#include <stdlib.h>
int n,m,num[50010],last[1000010],q[200010][3],ans[200010];
int sum[50010];
int comp(const void *a, const void *b)
{
return ((int*)a)[1] - ((int*)b)[1];
}
int lowbit(int x)
{
return x&(-x);
}
void add(int pos, int x)
{
for(;pos<=n;pos+=lowbit(pos)) sum[pos] += x;
}
int query(int pos)
{
int tans = 0;
for(;pos;pos-=lowbit(pos)) tans += sum[pos];
return tans;
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&num[i]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&q[i][0],&q[i][1]);
q[i][2] = i;
}
qsort(q+1,m,sizeof(q[0]),comp);
for(i=1,j=1;i<=m;i++)
{
for(;j<=q[i][1];j++)
{
if(last[num[j]]) add(last[num[j]],-1);
add(j,1);
last[num[j]] = j;
}
ans[q[i][2]] = query(q[i][1]) - query(q[i][0]-1);
}
for(i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
评论 (0)
