学步园

题目大意：给出一个数列，问[x,y]中间有多少种不同的数字在[a,b]之间。

思路：又是傻逼莫队……

如果没有[a,b]的限制，那么就是傻逼莫队了

这个限制就比较坑爹了，当然常规一点的想法还是树套树，很明显这个空间限制是卡树套树的。

所以就只能莫队了。然而暴力的求[a,b]之间有多少个数的话时间就到了O(n^2)，但是利用一下分块，时间复杂度就是O(n*sqrt(n))了。

CODE：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define SIZE 350
#define MAX 100010
using namespace std;
 
namespace IStream{
    const int L=1<<15;
    char buffer[L],*S,*T;
    inline char Get_Char()
    {
        if(S==T)
        {
            T=(S=buffer)+fread(buffer,1,L,stdin);
            if(S==T) return EOF;
        }
        return *S++;
    }
    inline int GetInt()
    {
        char c;
        int re=0;
        for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
        while(c>='0'&&c<='9')
            re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
        return re;
    }
}
 
int size;
int cnt,asks;
 
int src[MAX],belong[MAX];
int begin[SIZE];
 
struct Ask{
    int x,y,a,b;
    int id;
     
    bool operator <(const Ask &a)const {
        if(belong[x] == belong[a.x])    return y < a.y;
        return x < a.x;
    }
    void Read(int p) {
        x = IStream::GetInt();
        y = IStream::GetInt();
        a = IStream::GetInt();
        b = IStream::GetInt();
        id = p;
    }
}ask[1000010];
int colors[MAX],num[SIZE];
 
int ans[1000010];
 
inline void Add(int col)
{
    if(!colors[col])
        ++num[belong[col]];
    ++colors[col];
}
 
inline void Del(int col)
{
    if(colors[col] == 1)
        --num[belong[col]];
    --colors[col];
}
 
inline int Query(int a,int b)
{
    int re = 0;
    if(belong[a] == belong[b]) {
        for(int i = a; i <= b; ++i)
            re += colors[i] ? 1:0;
        return re;
    }
    int l = belong[a] + 1,r = belong[b] - 1;
    for(int i = l; i <= r; ++i)  re += num[i];
    for(int i = a; belong[i] == belong[a]; ++i)
        re += colors[i] ? 1:0;
    for(int i = begin[belong[b]]; i <= b; ++i)
        re += colors[i] ? 1:0;
    return re;
}
 
int main()
{
    cin >> cnt >> asks;
    size = sqrt(cnt);
    for(int i = 1; i <= cnt; ++i) {
        belong[i] = i / size;
        if(!begin[belong[i]])
            begin[belong[i]] = i;
    }
    for(int i = 1; i <= cnt; ++i)
        src[i] = IStream::GetInt();
    for(int i = 1; i <= asks; ++i)
        ask[i].Read(i);
    sort(ask + 1,ask + asks + 1);
    int l = 1,r = 0;
    for(int i = 1; i <= asks; ++i) {
        while(r < ask[i].y)  Add(src[++r]);
        while(l > ask[i].x)  Add(src[--l]);
        while(r > ask[i].y)  Del(src[r--]);
        while(l < ask[i].x)  Del(src[l++]);
        ans[ask[i].id] = Query(ask[i].a,ask[i].b);
    }
    for(int i = 1; i <= asks; ++i)   
        printf("%d\n",ans[i]);
    return 0;
}