题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入输出格式

输入格式:

第一行:一个整数N,表示项链的长度。

第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。

第三行:一个整数M,表示HH 询问的个数。

接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

输出格式:

M 行,每行一个整数,依次表示询问对应的答案

什么描述啊……

我们可以 简单地 发现对于每次区间询问,如果一种编号出现了多次,那么只有最后一次才是有意义的。

那么离线询问并按照R为第一关键字,L为第二关键字排序。

然后从当前位置指针(初始为1,当然)扫到R统计有没有新出现的和重复出现的

如果是新出现的那么标记一下再扔到树状数组里(哦,忘记了,树状数组是按位置建的,也就是下标和项链是对应的)

如果是重复出现的,那么,有一个数组保存之前出现的位置,get到这个位置然后往树状数组里这个位置扔一个-1就行了。

之后更新前一次出现位置数组并扔进树状数组里。

最后求区间和……

真是一道好题。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<utility>
using namespace std;

//data
struct qu
{
	int left,right,code;
}query[50010]={0};
int len,nec[50010]={0},qnum;
//tree
int fwt[50010]={0};
bool have[1000010]={0};
int firstplace[1000010]={0};
//count ans
int ans[100010]={0};

bool cmp(qu a,qu b)
{
	if (a.right==b.right) return a.left<b.left;
	return a.right<b.right;
}

void add(int pos,int val)
{
	while (pos<=len)
	{
		fwt[pos]+=val;
		pos+=pos&(-pos);
	}
}

int getsum(int pos)
{
	int res=0;
	while (pos)
	{
		res+=fwt[pos];
		pos-=pos&(-pos);
	}
	return res;
}

int main()
{
	scanf("%d",&len);
	for (int i=1;i<=len;i++) scanf("%d",&nec[i]);
	scanf("%d",&qnum);
	for (int i=1;i<=qnum;i++) 
	{
		scanf("%d%d",&query[i].left,&query[i].right);
		query[i].code=i;
	}
	sort(query+1,query+qnum+1,cmp);
	
	int totp=0;
	for (int i=1;i<=qnum;i++)
	{
		while (totp<query[i].right)
		{
			totp++;
			if (!have[nec[totp]]) have[nec[totp]]=true;
			else add(firstplace[nec[totp]],-1);
			
			firstplace[nec[totp]]=totp;
			add(totp,1);
		}
		
		ans[query[i].code]=getsum(query[i].right)-getsum(query[i].left-1);
	}
	
	for (int i=1;i<=qnum;i++)  printf("%d\n",ans[i]);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.