说实话，做优化这个专题实在是磕磕绊绊的，交了很多TLE和WA，每道题一上手第一感觉是会做，然后按照往常的思路暴力求解。信心满满的交上去之后得到的只是超时的回复，于是我就开始找自己程序的问题，刚开始的时候，越改越乱，改到后面再提交就得到了WA的回复，然后就觉得特纳闷。于是第一道题就看了题解，当时看了之后是恍然大悟的感觉，然后自己也写了一份类似的代码匆匆忙忙提交后AC也就没管了，今天再看同样的这道题，竟然还是毫无头绪。说实话，心里还是挺失落的，不过加油总结，以后碰到类似的题目要会。废话少说，现在就上那几道题吧。
这是第一道题的题目描述：
给定一个数组a和q个查询，查询第i个数字及以后共有几个互不相同的数字。
Input
第一行是两个整数n和q（1<=n,q<=10^5），分别表示数组的长度和询问的次数。第二行是n个整数 a1, a2, ..., an (1≤ai≤105) 表示数组内容。
接下来的q行表示q个询问，每询问是一个整数i(1<=i<=n)。
Output
对于每个询问，输出答案。
SampleInput
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10
SampleOutput
6
6
6
6
6
5
4
3
2
1
这道题的题目很短，就短短的一句话：
给定一个数组a和q个查询，查询第i个数字及以后共有几个互不相同的数字。
一开始拿到这道题目的时候，我是按照常规暴力遍历的思路，每输入一个查询，然后用“桶的思想”便开始遍历从该数及以后共有多少个互不相同的数字，殊不知这样做其实重复了很多次的遍历，比如说第一次查询的数字是3，第二次是4.那么4后面的数字都是重复遍历。
而查询的次数高达10^5次方量级的，因此第一次的提交，因为太多的重复遍历操作，所以得到了一个TLE。下面是一种解题思路：
我们注意到题目是查询第i个数字及以后有多少个互不相同的数字，那么突破点来了。
既然是求“以后”，如果我们从头往后遍历的话，那么难免两个查询的数区间的交叉部分是要重复遍历的。所以呢，我们就可以想到一种办法，就是将数组a从后往前遍历，并且声明一个相应大小的查询数组，每往前遍历一个数，便更新查询数组中相应的值。举个例子：
如果数组中有五个数，那么当从a[4]→a[3]的时候，这时候更新查询数组中ans[3]的值，并保存。那么这时候就还剩下一个问题尚待解决，题目要查询的是共有几个互不相同的数字。
这个问题其实很好解决，我们可以使用“标记法”，即另外再声明一个10^5量级的bool类型的数组。在输入数据的时候，每输入一个数据便将该bool类型的数组中的相应元素赋值为true.举个例子，就是说如果输入的是33，那么该bool类型的数组中的tmp[33]则赋值为true。表示输入的数据中含有33这个元素，所以呢在后面我们遍历的时候，已经遍历到的数字，便将该数对应的bool类型数组中相应元素赋值为false。这样的话便可以用一个if判断语句，判断当前遍历到的数字是否已经出现过，出现过便不再重复计数，这样的话就可以起到查询共有几个互不相同的数字的作用，而每当往前遍历的时候，便更新对应的查询数组的值。
下面附上完整的代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005],ans[100005]; //全局变量初始值为0
bool tmp[100005]; //用来标记a[i]
int main()
{
int n,q;
while(scanf("%d %d",&n,&q) == 2 && n && q)
{
int sum = 0,ask; //用来记录每次询问的结果，实时更新
for(int i = 0;i < n;i++)
{
scanf("%d",&a[i]);
tmp[a[i]] = true;
}
for(int i = n - 1;i >= 0;i--)
{
if(tmp[a[i]])
{
sum++;
tmp[a[i]] = false; //表示该数已经出现过,往后不再对该数计数
}
ans[i] = sum; //从后往前减少遍历次数
}
while(q--)
{
scanf("%d",&ask);
printf("%d\n",ans[ask-1]);
}
}
return 0;
}
