记录编号	488987	评测结果	AAAAAAATTT
题目名称	[HEOI 2012]采花	最终得分	70
用户昵称	Rye_Catcher	是否通过	未通过
代码语言	C++	运行时间	20.437 s
提交时间	2018-02-26 11:07:16	内存使用	67.07 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#define ri register int 
#define ll long long 
using namespace std;
const int maxn=2000005;
int n,m,cc,a[maxn];
int num[maxn];
int block,belong[maxn];
int anss[maxn],ans=0;
struct Ask{
    int l,r,id;
}ask[maxn];
void print(int x)
{
    if(x<0){
      putchar('-');
      x=-x;
    }
    if(x>9)  print(x/10);
    putchar(x-x/10*10+'0');
}
inline bool cmp (const Ask & a,const Ask & b)
{
    return belong[a.l]^belong[b.l]?belong[a.l]<belong[b.l]:belong[a.l]&1?a.r<b.r:a.r>b.r;
}
inline int read(){
    int x,ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    return ne?-x:x;
}
inline void add(int c){
    num[c]++;
    if(num[c]==2)ans++;
    return ;
}
inline void rem(int c){
    num[c]--;
    if(num[c]==1)ans--;
    return ;
}
inline void solve(){
    int l=1,r=0;
    for(ri i=1;i<=m;i++){
        int L=ask[i].l,R=ask[i].r;
        while(r<R)add(a[++r]);
        while(r>R)rem(a[r--]);
        while(l<L)rem(a[l++]);
        while(l>L)add(a[--l]);
        anss[ask[i].id]=ans;
    }
    for(ri i=1;i<=m;i++){
        print(anss[i]);
        putchar('\n');//printf("%d\n",anss[i]);
    }
    return ;
}
int main() 
{
    freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    n=read(),cc=read(),m=read();
    block=n/sqrt(m*2/3);
    for(ri i=1;i<=n;i++){
        a[i]=read();
        belong[i]=(i-1)/block+1;
    }
    for(ri i=1;i<=m;i++){
        ask[i].l=read();
        ask[i].r=read();
        ask[i].id=i;
    }
    sort(ask+1,ask+1+m,cmp);
    solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}