emmm......我把莫队扔到了杂题里，因为感觉局限挺大的=。=

这题是莫队维护信息+分块查询答案，都是两者的基本操作，复杂度$O(m$ $sqrt(n)+n$ $sqrt(m))$

所以为啥要写这水题的题解来着

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int N=100005,Sq=320; 7 struct a 8 { 9     long long ans,num;10     int l,r,xx,yy,v,id; 11 }mo[N];12 int b[N],blo[N],cnt[N],exi[Sq],bkt[Sq],pts[Sq][2];13 int n,m,t1,t2,t3,t4,lp,rp,sqr,srt,xnt,maxx;14 bool cmp(a x,a y)15 {16     return x.v==y.v?x.r
          
           
            0);53 for(int i=pts[blo[y]][0];i<=y;i++) ret+=(cnt[i]>0);54 for(int i=blo[x]+1;i<=blo[y]-1;i++) ret+=exi[i];55 }56 else for(int i=x;i<=y;i++) ret+=(cnt[i]>0);57 return ret;58 }59 int main ()60 {61 scanf("%d%d",&n,&m),sqr=sqrt(n);62 for(int i=1;i<=n;i++) 63 scanf("%d",&b[i]),maxx=max(maxx,b[i]);64 for(int i=1;i<=m;i++)65 {66 scanf("%d%d%d%d",&t1,&t2,&t3,&t4);67 mo[i].v=(t1-1)/sqr+1,mo[i].id=i,maxx=max(maxx,t4);68 mo[i].l=t1,mo[i].r=t2,mo[i].xx=t3,mo[i].yy=t4; 69 }70 pts[xnt=1][0]=1,srt=sqrt(maxx);71 for(int i=1;i<=n;i++)72 {73 blo[i]=(i-1)/srt+1;74 if(i%srt==0)75 {76 pts[xnt++][1]=i;77 pts[xnt][0]=i+1;78 }79 }80 pts[xnt][1]=maxx,lp=1;81 sort(mo+1,mo+1+m,cmp);82 for(int i=1;i<=m;i++)83 {84 while(lp
            
             mo[i].l) change(b[--lp],1);86 while(rp
             
              mo[i].r) change(b[rp--],0);88 mo[i].ans=query1(mo[i].xx,mo[i].yy);89 mo[i].num=query2(mo[i].xx,mo[i].yy);90 }91 sort(mo+1,mo+1+m,com);92 for(int i=1;i<=m;i++)93 printf("%lld %lld\n",mo[i].ans,mo[i].num);94 return 0;95 }