ZOJ4117 BaoBao Loves Reading（思维+树状数组）

题目描述

BaoBao is a good student who loves reading, but compared with his huge bookshelf containing lots and lots of books, his reading desk, which can only hold at most books, is surprisingly small.
Today BaoBao decides to read some books for minutes by the desk. According to his reading plan, during the -th minute, he is scheduled to read book . The reading desk is initially empty and all the books are initially on the shelf. If the book BaoBao decides to read is not on the desk, BaoBao will have to fetch it from the shelf. Also, if the desk is full and BaoBao has to fetch another book from the shelf, he will have to put one book back from the desk to the shelf before fetching the new book.
Tired of deciding which book to put back, BaoBao searches the Internet and discovers an algorithm called the Least Recently Used (LRU) algorithm. According to the algorithm, when BaoBao has to put a book back from the desk to the shelf, he should put back the least recently read book.
For example, let’s consider the reading plan {4, 3, 4, 2, 3, 1, 4} and assume that the capacity of the desk is 3. The following table explains what BaoBao should do according to the LRU algorithm. Note that in the following table, we use a pair of integer to represent a book, where is the index of the book, and is the last time when this book is read.

Minute Books on the Desk	Minute Books on the Desk	Before This Minute BaoBao’s Action
1	{}	Fetch book 4 from the shelf
2	{(4, 1)}	Fetch book 3 from the shelf
3	{(4, 1), (3, 2)}	Do nothing as book 4 is already on the desk
4	{(4, 3), (3, 2)}	Fetch book 2 from the shelf
5	{(4, 3), (3, 2), (2, 4)}	Do nothing as book 3 is already on the desk
6	{(4, 3), (3, 5), (2, 4)}	Put book 4 back to the shelf as its the least recently read book,and fetch book 1 from the shelf
7	{(3, 5), (2, 4), (1, 6)}	Put book 2 back to the shelf as its the least recently read book,and fetch book 4 from the shelf

Given the reading plan, what’s the number of times BaoBao fetches a book from the shelf if the value of (the capacity of the desk) ranges from 1 to (both inclusive)?

Input

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains an integer (), indicating the length of the reading plan.
The second line contains integers (), indicating the indices of the books to read.
It’s guaranteed that the sum of of all test cases will not exceed .

Output

For each test case output one line containing integers separated by a space, where indicates the number of times BaoBao fetches a book from the shelf when the capacity of the desk is .
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Sample Input
1
7
4 3 4 2 3 1 4
Sample Output
7 6 5 4 4 4 4

题目大意

按照顺序依次从书架上取书到桌上，桌上的容量为k(1<=k<=n)，当桌上书本个数小于k时，直接取书，若>=k，则需要把桌上最早阅读的书放回再取，问对于不同的容量k 需要取书的次数是多少。

题目分析

设num[i] //表示相等的两个数之间距离为i的数的个数（即相等的两个数之间有多少个不同的数）
num[] 数组我们可以用树状数组求出。

对于每个num[i]来说，都代表：如果容量k大于等于num[i]，那么在读到对应的书时，我们就不需要再去书架上拿书了，书桌上此时还有这本书。
反之，如果k小于num[i]，在读到对应的书时，这本书已经放回书架上了，因此我们要重新再取出这本书。
即：对于每个num[i]，我们都要给区间ans[1一(num[i]-1)]+1。

对于给区间中每个数加一个数的操作，我们可以维护一个差分数组。即把ans[i]变为差分数组，最后再用前缀和还原。

代码如下

#include <iostream>
#include <cmath>
#include <cstdio>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <bitset>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PDD pair<double,double>
#define x first
#define y second
using namespace std;
const int N=1e5+5;
int n,tr[N];			//tr[]为树状数组
int pre[N],ans[N];		//pre[x]表示x数上次出现的位置，ans[]为答案数组
int lowbit(int x)		//树状数组模板函数
{
	return x&-x;
}
void add(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tr[i]+=c;
}
int sum(int x)
{
	int res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=tr[i];
	return res;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<=n;i++) ans[i]=tr[i]=pre[i]=0;		//清空数组
		ans[1]=n;		//因为n次区间操作都是从1开始的，因此我们可以在这提前给ans[1]加上n
		for(int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			add(i,1);					//在i处做一个记录
			if(pre[x])					//如果x在前面存在
			{
				add(pre[x],-1);			//删除x原位置上的标记
				int num=sum(i)-sum(pre[x]-1);	//求出num
				ans[num]--;				//给ans[1-(num-1)]区间加上1（差分）
			}
			pre[x]=i;					//更新pre[x]
		}
		for(int i=1;i<n;i++)			//前缀和还原数组，并输出答案
		{
			ans[i]+=ans[i-1];
			printf("%d ",ans[i]);
		}
		printf("%d\n",ans[n]+ans[n-1]);
	}
	return 0;
}