记录编号	151721	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.983 s
提交时间	2015-03-09 20:55:51	内存使用	7.57 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
const int MAXN=50050;
int col[MAXN],Block[MAXN];
struct Querys{
   int s,e,No;
   bool operator <(const Querys &rhs) const{
      return Block[s]==Block[rhs.s]?e<rhs.e:Block[s]<Block[rhs.s];
   }
};
///==============var declaration=================
int n,q;
int color[1000100],cnt=0;
int ans[200500];
Querys Query[200500];
///==============function declaration============

///==============main code=======================
int main()
{

   freopen("diff.in","r",stdin);
   freopen("diff.out","w",stdout);

   scanf("%d",&n);
   for(int i=1;i<=n;i++){
      scanf("%d",col+i);
      Block[i]=sqrt(i*1.0);
   }
   scanf("%d",&q);
   for(int i=1;i<=q;i++){
      scanf("%d%d",&Query[i].s,&Query[i].e);
      Query[i].No=i;
   }
   sort(Query+1,Query+1+q);
   int l=1,r=1;color[col[1]]++;cnt=1;
   for(int i=1;i<=q;i++){
      while (r<Query[i].e){
         r++;
         if (++color[col[r]]==1) cnt++;
      }
      while (r>Query[i].e){
         if (--color[col[r]]==0) cnt--;
         r--;
      }
      while (l<Query[i].s){
         if (--color[col[l]]==0) cnt--;
         l++;
      }
      while (l>Query[i].s){
          l--;
         if (++color[col[l]]==1) cnt++;
      }
      ans[Query[i].No]=cnt;
   }
   for(int i=1;i<=q;i++)
      printf("%d\n",ans[i]);
}