思路：
莫队+树状数组维护；
代码：
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxn 100005 struct QueryType { int l,r,a,b,id; }; struct QueryType qu[maxn*10]; int n,sum[maxn],sum_[maxn],ti[maxn],ans[maxn*10][2]; int ai[maxn],size,bel[maxn],m; inline void in(int &now) { char Cget=getchar();now=0; while(Cget>'9'||Cget<'0') Cget=getchar(); while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } } inline int lowbit(int x) { return x&(-x); } inline void sadd(int x,int k) { while(x<=n) sum[x]+=k,x+=lowbit(x); } inline int ssum(int p,int x) { int res=0;p--; while(x) res+=sum[x],x-=lowbit(x); while(p) res-=sum[p],p-=lowbit(p); return res; } inline void tadd(int x,int k) { while(x<=n) sum_[x]+=k,x+=lowbit(x); } inline int tsum(int p,int x) { int res=0;p--; while(x) res+=sum_[x],x-=lowbit(x); while(p) res-=sum_[p],p-=lowbit(p); return res; } inline bool cmp(QueryType aaa,QueryType bbb) { if(bel[aaa.l]==bel[bbb.l]) { if(bel[aaa.r]==bel[bbb.r]) { if(aaa.l==bbb.l) return aaa.r<bbb.r; else return aaa.l<bbb.l; } return bel[aaa.r]<bel[bbb.r]; } else return bel[aaa.l]<bel[bbb.l]; } inline void updata(int now,int x) { int pre=ti[now]; ti[now]+=x,sadd(now,x); if(pre==0&&ti[now]==1) tadd(now,1); if(pre==1&&ti[now]==0) tadd(now,-1); } int main() { in(n),in(m),size=sqrt(n);for(int i=1;i<=n;i++) in(ai[i]),bel[i]=(i-1)/size; for(int i=1;i<=m;i++) in(qu[i].l),in(qu[i].r),in(qu[i].a),in(qu[i].b),qu[i].id=i; sort(qu+1,qu+m+1,cmp);int l=1,r=0,pos; for(int no=1;no<=m;no++) { if(l<qu[no].l) for(int i=l;i<qu[no].l;i++) updata(ai[i],-1); else for(int i=l-1;i>=qu[no].l;i--) updata(ai[i],1); if(r>qu[no].r) for(int i=r;i>qu[no].r;i--) updata(ai[i],-1); else for(int i=r+1;i<=qu[no].r;i++) updata(ai[i],1); l=qu[no].l,r=qu[no].r,ans[qu[no].id][1]=ssum(qu[no].a,qu[no].b),ans[qu[no].id][2]=tsum(qu[no].a,qu[no].b); } for(int i=1;i<=m;i++) printf("%d %d ",ans[i][1],ans[i][2]); return 0; }