同上题，BZOJ3236，简化了，只要求求数值的个数。

同样的做法，似乎我没加读入优化rank倒一……现在我做莫队题一块都是$O(\sqrt{\frac{n}{2}})$。

# include <stdio.h>
# include <math.h> 
# include <algorithm>
using namespace std;
int n,m,t,left=1,right;
int a[100010],cnt[100010],w[100010];
int g[10010];
int a2[1000010];
 
 
struct quest {
    int l,r,a,b,id;
    bool operator <(const quest &A) const{
        if (w[l]==w[A.l]) return r<A.r;
        else return l<A.l;
    }
}q[1000010];
 
inline void xy(int l,int r,int id) {
    if(w[l]==w[r]) {
        for (int i=l;i<=r;++i) if(cnt[i]) a2[id]++;
    } else {
        for (int i=w[l]*t-1;i>=l;--i) if(cnt[i]) a2[id]++;
        for (int i=w[r]*t-t;i<=r;++i) if(cnt[i]) a2[id]++; 
        for (int i=w[l]+1;i<w[r];++i) a2[id]+=g[i];
    }
}
 
inline void u(int x) {
    ++cnt[x];
    if(cnt[x]==1) g[w[x]]++;
}
 
inline void v(int x) {
    --cnt[x];
    if(cnt[x]==0) g[w[x]]--;
}
 
int main() {
    scanf("%d%d",&n,&m);
    t=sqrt(n/2);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]),w[i]=i/t+1;
    for (int i=1;i<=m;++i) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i;
    sort(q+1,q+m+1);
    for (int i=1;i<=m;++i) {
        while(right<q[i].r) u(a[++right]);
        while(left<q[i].l) v(a[left++]);
        while(right>q[i].r) v(a[right--]);
        while(left>q[i].l) u(a[--left]);     
        xy(q[i].a,q[i].b,q[i].id); 
    }
    for (int i=1;i<=m;++i) printf("%d\n",a2[i]);
}