Description
Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。
Input
第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。
第二行包括n个整数s1...sn(1<=si<=n)。
接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。
Output
对每个询问，单独输出一行，表示sl...sr中权值∈[a,b]的权值的种类数。
Sample Input
10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
Sample Output
2
0
0
2
1
1
1
0
1
2
0
0
2
1
1
1
0
1
2
HINT
样例的部分解释：
5 9 1 2
子序列为4 1 5 1 2
在[1,2]里的权值有1,1,2，有2种，因此答案为2。
3 4 7 9
子序列为5 1
在[7,9]里的权值有5，有1种，因此答案为1。
4 4 2 5
子序列为1
没有权值在[2,5]中的，因此答案为0。
2 3 4 7
子序列为4 5
权值在[4,7]中的有4,5，因此答案为2。
建议使用输入/输出优化。
同AHOI2013作业。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
int n,m,A[maxn],blo[maxn],st[maxn],en[maxn];
struct Query {
int l,r,a,b,id;
bool operator < (const Query& ths) const {
if(blo[l]==blo[ths.l]) return r<ths.r;
return l<ths.l;
}
}Q[maxm];
int ans[maxm],cnt[maxn],bloans[maxn];
void add(int x) {
if(!cnt[x]) bloans[blo[x]]++;
cnt[x]++;
}
void del(int x) {
cnt[x]--;
if(!cnt[x]) bloans[blo[x]]--;
}
int query(int l,int r) {
int res=;
rep(i,blo[l]+,blo[r]-) res+=bloans[i];
if(blo[l]==blo[r]) rep(i,l,r) res+=(cnt[i]>);
else {
rep(i,l,en[blo[l]]) res+=(cnt[i]>);
rep(i,st[blo[r]],r) res+=(cnt[i]>);
}
return res;
}
int main() {
n=read();m=read();int SIZE=(int)sqrt(m/);
rep(i,,n) {
A[i]=read();blo[i]=(i-)/SIZE+;
if(!st[blo[i]]) st[blo[i]]=i;
en[blo[i]]=i;
}
rep(i,,m) Q[i].l=read(),Q[i].r=read(),Q[i].a=read(),Q[i].b=read(),Q[i].id=i;
sort(Q+,Q+m+);
int l=,r=;
rep(i,,m) {
while(l>Q[i].l) add(A[--l]);
while(r<Q[i].r) add(A[++r]);
while(l<Q[i].l) del(A[l++]);
while(r>Q[i].r) del(A[r--]);
ans[Q[i].id]=query(Q[i].a,Q[i].b);
}
rep(i,,m) printf("%d\n",ans[i]);
return ;
}