SDOI2009-HH的项链

题目描述

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

输入

一行一个正整数 n，表示项链长度。
第二行 n 个正整数 a_i，表示项链中第 i 个贝壳的种类。
第三行一个整数 m，表示 H 询问的个数。
接下来 m 行，每行两个整数 l,r，表示询问的区间。

输出

输出 m 行，每行一个整数，依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

思路

核心思路在于如何用区间和去表示种类的多少。
我们很容易想到，如果一种类型选出一个代表，而且这个代表恰好就在我们所选的范围内。那么我们直接用前区间和的方法就可以算出来结果。
eg.
1 2 2 3 4 4
我们要查询区间2-5，那么我们可以这么标记每一个位置
1 1 0 1 1 0如此，我们查询可以得到2-5之间是3种。
下面就要介绍一种思维，叫做离线处理。
问题：什么是离线？
我们所说的在线是指每当出现一次询问就要立即做出回应。
那么我们这里就要相反，我们先接收所有的信息，最后做统一处理后，最后一起输出。
这就是离线和在线的区别。

好我们已经知道了什么是离线，那么我们这里为什么要用离线呢？
下面正式介绍本题的核心思路。
首先我们先标记每种类型第一次出现的点，这里我们标记成1，而重复的就标记成0。
接下来，我们重前往后遍历，如果当前的点是在我们所规定的区间内，那么我们就把他最后一次出现的位置标记成1，其余标记成0。那么我们知道从前往后标记，这在某种意义上是不可逆的过程，所以我们必须先排序，再计算，再还原。

Accept Code

//#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const ll less_inf = 0x3f3f3f3f;
const char char_inf = 127;
#pragma GCC optimize(2)
#define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false);
#define PI 3.141592653589793
#define EPS 1.0e-8
ll gcd(ll a, ll b) {
    
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    
	return a / gcd(a, b) * b;
}
inline ll read() {
    
	ll c = getchar(), Nig = 1, x = 0;
	while (!isdigit(c) && c != '-')c = getchar();
	if (c == '-')Nig = -1, c = getchar();
	while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
	return Nig * x;
}
inline void out(ll a) {
    
	if (a < 0)putchar('-'), a = -a;
	if (a > 9)out(a / 10);
	putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
    
	ll res = 1;
	while (n > 0) {
    
		if (n & 1)res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}
#define read read()
const int N = 1e6 + 7;
struct node
{
    
	int sum;
}tree[N * 4];
struct Info {
    
	int l, r, pos, val;
}info[N];
int save[N];
int mark[N];
void pushup(int rt)
{
    
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
void update(int aim, int val, int l, int r, int rt)
{
    
	if (l == r)
	{
    
		tree[rt].sum = val;
		return;
	}
	int mid = l + r >> 1;
	if (aim <= mid)update(aim, val, l, mid, rt << 1);
	else update(aim, val, mid + 1, r, rt << 1 | 1);
	pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
    
	if (L <= l && r <= R)
		return tree[rt].sum;
	int val = 0;
	int mid = l + r >> 1;
	if (L <= mid)val += query(L, R, l, mid, rt << 1);
	if (R > mid)val += query(L, R, mid + 1, r, rt << 1 | 1);
	return val;
}
bool cmp(Info a, Info b)
{
    
	return a.r < b.r;
}
bool cmp2(Info a, Info b)
{
    
	return a.pos < b.pos;
}
int main()
{
    
	int n = read;
	for (int i = 1; i <= n; i++)
	{
    
		save[i] = read;
		if (!mark[save[i]])
		{
    
			mark[save[i]] = i;
			update(i, 1, 1, n, 1);
		}
	}
	int m = read;
	for (int i = 0; i < m; i++)
	{
    
		info[i].l = read;
		info[i].r = read;
		info[i].pos = i;
	}
	sort(info, info + m, cmp);
	int pos = 1;
	for (int i = 0; i < m; i++)
	{
    
		while (pos <= info[i].r)
		{
    
			update(mark[save[pos]], 0, 1, n, 1);
			update(pos, 1, 1, n, 1);
			mark[save[pos]] = pos;
			pos++;
		}
		info[i].val = query(info[i].l, info[i].r, 1, n, 1);
	}
	sort(info, info + m, cmp2);
	for (int i = 0; i < m; i++)
	{
    
		out(info[i].val);
		puts("");
	}
}

By-Round Moon