POJ 3320 Jessica's Reading Problem

题目链接：点击这里

题意：

为了准备考试， Jessica 开始读一本很厚的课本。要想通过考试，必须把课本中所有的知识点
都掌握。这本书总共有 $P$P 页，第 $i$i 页恰好有一个知识点 $a_i$ai​（每个知识点都有一个整数编号）。全书中同一个知识点可能会被多次提到，所以她希望通过阅读其中连续的一些页把所有的知
识点都覆盖到。给定每页写到的知识点，请求出要阅读的最少页数。

思路：

我们假设从某一页 $s$s 开始阅读，为了覆盖所有的知识点需要阅读到 $t$t。这样的话可以知道如果从 $s+1$s+1 开始阅读的话，那么必须阅读到 $t'≥t$t′≥t 页为止。由此这题也可以使用尺取法。

在某个区间 $[s,t]$[s,t] 已经覆盖了所有的知识点的情况下，下一个区间 $[s+1,t']\ (t'≥t)$[s+1,t′] (t′≥t) 要如何求出呢？

所有的知识点都被覆盖 $\Longleftrightarrow$⟺ 每个知识点出现的次数都不小于 $1$1

由以上的等价关系，我们可以用二叉树等数据结构来存储 $[s,t]$[s,t] 区间上每个知识点的出现次数，这
样把最开头的页 $s$s 去除后便可以判断 $[s+1,t]$[s+1,t] 是否满足条件。

从区间的最开头把 $s$s 取出之后，页 $s$s 上书写的知识点的出现次数就要减 $1$1，如果此时这个知识点的出现次数为 $0$0 了，在同一个知识点再次出现前，不停将区间末尾 $t$t 向后推进即可。每次在区间末尾追加页 $t$t 时将页 $t$t 上的知识点的出现次数加 $1$1，这样就完成了下一个区间上各个知识点出现次数的更新，通过重复这一操作可以以 $O(PlogP)$O(PlogP) 的复杂度求出最小的区间。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 1000010;
int P, a[maxn];

int main()
{
	scanf("%d", &P);
	for(int i = 0; i < P; ++i)
		scanf("%d", &a[i]);
	
	set<int> all;
	for(int i = 0; i < P; ++i)	//去重 
		all.insert(a[i]);
	int n = all.size();
	
	// 利用尺取法来求解
	int s = 0, t = 0, num = 0;
	map<int, int> count; 	//知识点到出现次数的映射
	int res = P;
	for( ; ; )
	{
		while(t < P && num < n)
		{
			if(count[a[t++]]++ == 0)	//出现新的知识点
				num++;
		}
		
		if(num<n)	break;
		
		res = min(res, t - s);
		
		if(--count[a[s++]] == 0)	//某个知识点的出现次数为0了
			num--;
	}
	printf("%d\n", res);
	return 0;
}