题目
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
Sample Output
2
0
0
2
1
1
1
0
1
2
题解
莫队+值域分块
因为数组开小了调了两节课…… 
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
int n,m,k,N;
int a[MAX],pos[MAX],bl[MAX],br[MAX],num[MAX],cnt[MAX],ans[MAX*10];
struct p{
int l,r,a,b,id;
bool operator< (const p &a)
const{
if(pos[l]!=pos[a.l]) return pos[l]<pos[a.l];
return r<a.r;
}
}qu[MAX*10];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int ask(int l,int r)
{
int ans=0;
if(pos[l]==pos[r])
{
if(l==bl[pos[l]]&&r==br[pos[r]]) return cnt[pos[l]];
for(int i=l;i<=r;++i)
if(num[i]) ++ans;
return ans;
}
int L=pos[l],R=pos[r];
if(l!=bl[pos[l]]) ++L;
if(r!=br[pos[r]]) --R;
for(int i=L;i<=R;++i)
ans+=cnt[i];
if(L!=pos[l]) for(int i=l;i<=br[pos[l]];++i)
if(num[i]) ++ans;
if(R!=pos[r]) for(int i=bl[pos[r]];i<=r;++i)
if(num[i]) ++ans;
return ans;
}
void add(int x) {if(++num[a[x]]==1) ++cnt[pos[a[x]]];}
void del(int x) {if(!--num[a[x]]) --cnt[pos[a[x]]];}
int main()
{
k=sqrt(n=read()),m=read();
if(n%k) ++k;
for(int i=1,x;i<=n;++i)
{
a[i]=read(),x=pos[i]=(i-1)/k+1,br[x]=i;
if(!bl[x]) bl[x]=i;
}
for(int i=1;i<=m;++i)
qu[i].l=read(),qu[i].r=read(),qu[i].a=read(),qu[i].b=read(),qu[i].id=i;
sort(qu+1,qu+1+m);
for(int i=1,l=1,r=0;i<=m;++i)
{
while(l<qu[i].l) del(l++);
while(l>qu[i].l) add(--l);
while(r<qu[i].r) add(++r);
while(r>qu[i].r) del(r--);
ans[qu[i].id]=ask(qu[i].a,qu[i].b);
}
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
