rt，菜鸡被卡空间卡死了，理论空间 $O(nsqrtn)$，实际上死都过不去最后一个点 各种方法都试过了，块长也试过不少，就是卡最后一个点。

#include <stack>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <random>
#include <assert.h>
#include <ctime>

using namespace std;
//reader and writer
#define int long long
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
//file io
void setIO(string name) {
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
//read int
inline int read(){
    register int a=0,f=1;register char c;
    while((c=getchar())<'0')if(c=='-')f=-1;
    while(c>='0')a=a*10+(c^48),c=getchar();
    return a*f;
}
//write int
inline void write(int s) {
  if (s<0) s =-s,putchar('-');
  if (s>9) write(s/10),putchar(s%10+'0');
  else putchar(s+'0');
}
//write int with space
inline void Write(int s){
  write(s);
  printf(" ");
}
//write int with endl
inline void writeln(int s){
  write(s);
  puts("");
}
//get char
inline char get(){
  char re = getchar();
  while(re=='\r' || re=='\n') re = getchar();
  return re;
}
//get string
inline string Get(){
  string s=""; char re;
  while(isalpha(re=getchar())) s+=re;
  return s;
}
struct read{
	static const int BUFSIZE=1<<23;
	char buf[BUFSIZE],*p1,*p2,c,f;
	read():p1(buf),p2(buf){}
	char gc(void){
		if(p1==p2)p2=buf+fread(p1=buf,1,BUFSIZE,stdin);
		if(p1==p2)return EOF;
		else return *p1++;
	}
	read& operator >>(int& x){
		c=gc(),f=1,x=0;
		for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(;c>='0'&&c<='9';c=gc())x=x*10+c-'0';
		x*=f;
		return *this;
	}
	read& operator >>(char &c){
		c=gc();
		while(c!='A'&&c!='C') c=gc();
		return *this;
	}
}fin;

mt19937 rnd(time(NULL));
int rad(int x,int y){
	return rnd()%(y-x+1)+x;
}
//template stuff
typedef vector<int> vi;
typedef long long ll;
#define ft front()
#define bk back()
#define pq priority_queue
#define sz(x) (int)(x).size()
#define mp make_pair
#define endl '\n'
#define pp pair<int,int>
#define f first
#define s second
#define pb push_back
#define mem(s,v) memset(s,v,sizeof(s))
#define For(i,a,b) for (int i=a;i<=b;i++)
#define FOR(i,a,b) for (int i=a;i>=b;i--)
#define Trav(a,b) for(auto a : b)
#define trav(i,u) for(int i=head[u];i;i=edge[i].nxt)
int Mod(int a, int p=(int)(1e9+7)){return a<p ? a : a%p;}
int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);}
int chkmax(int a, int b){return a>b?a:b;}
int chkmin(int a, int b){return a<b?a:b;}
int qpow(int base, int times, int p=0){int ans=1;if (p)base%=p;while(times){if(times&1) {ans=ans*base; if(p) ans%=p;}times>>=1;base=base*base;if (p) base%=p;}return ans;}
int MaxVal(int a, int b, int *val){int re = 0;For(i,a,b) re = chkmax(re,val[i]);return re;}
int MinVal(int a, int b, int *val){int re = 1e9;For(i,a,b) re = chkmin(re,val[i]);return re;}


//namespace

const int MAXN = 1e5+5;
const int MAXM = 2e6+5;
const int mod = 1e9+7;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
int n,m,t,l,k,a,b,c,d,pos[MAXN],ans,len,pre[MAXN],cor[MAXN],L,R=1,head[MAXN],block[MAXN];
vi num[MAXN],ub[MAXN];
namespace BIT{
  #define lowbits(x) (x&-x)
  int bit[320][MAXN],bit2[320][MAXN];
  inline void update(int u, int val, int* bit) {
    for (int i=u;i<=n;i+=lowbits(i)) bit[i]+=val;
  }
  inline int query(int u, int* bit){
    int re = 0;
    for (int i=u;i;i-=lowbits(i)) re+= bit[i];
    return re;
  }
  #undef lowbits
}
using namespace BIT;
struct Query{
  int l,r,a,b,id,ans,ans2;
  bool operator < (const Query &oth) const{
    return r<oth.r;
  }
}q[MAXN];
inline int bsl(int id, int val){
  if (num[id].size()==0) return -1;
  int l = 0, r = num[id].size()-1;
  while(l!=r){
    int mid = (l+r)/2;
    if (num[id][mid]<val) l = mid+1;
    else r = mid;
  }
  return num[id][l]>=val ? l : -1;
}
inline int bsr(int id, int val){
  // if (num[id].size()==0) return -1;
  assert(num[id].size());
  int l = 0, r = num[id].size()-1;
  while(l!=r){
    int mid = (l+r+1)/2;
    if (num[id][mid]>val) r = mid-1;
    else l = mid;
  }
  return num[id][l]<=val ? l : -1;
}
inline bool cmp(Query a, Query b){
  return a.id<b.id;
}
inline void solve(int i){
  while(R<=q[i].r){
    if (pre[R]) update(pre[R],-1,bit[block[pos[pre[R]]]]);
    update(R,1,bit[block[pos[R]]]);
    update(R,1,bit2[block[pos[R]]]);
    R++;
  }
  // For(j,1,len){
  //   For(k,1,len) cout << query(k,bit[j]) << " ";
  //   puts("");
  // }
  ans = 0;
  For(v,block[q[i].a],block[q[i].b]){
    //Case 1: part of the block
    int lb = chkmax(1,(v-1)*len),rb = v*len-1;
    if (q[i].a>=lb || q[i].b<=rb){
      For(j,chkmax(lb,q[i].a),chkmin(rb,q[i].b)) {
        int left = bsl(j,q[i].l);
        if (left==-1) continue;
        if(num[j][left]<=q[i].r) {
          // cout << q[i].l << " " << q[i].r << "  " << q[i].a << "  " << q[i].b;
          // puts("");
          q[i].ans++;
          int right = bsr(j,q[i].r);
          q[i].ans2+= right-left+1;
        }
      }
      //Case 2: whole block included
    }else{
      assert(q[i].a<=lb && q[i].b>=rb);
      // cout << q[i].l << " " << q[i].r << " " << q[i].a << " " << q[i].b << endl;
      // cout << query(q[i].r,bit[v])-query(q[i].l-1,bit[v]) << "   " << query(q[i].r,bit2[v])-query(q[i].l-1,bit2[v]) << endl;
      q[i].ans+= query(q[i].r,bit[v])-query(q[i].l-1,bit[v]);
      q[i].ans2+= query(q[i].r,bit2[v])-query(q[i].l-1,bit2[v]);
    }
  }
}

signed main(){
  n = read(); m = read();len = sqrt(n)+1;
  For(i,1,n) {pos[i] = read();num[pos[i]].pb(i);}
  For(i,1,n){
    if (!head[pos[i]]) head[pos[i]] = i;
    else{
      pre[i] = head[pos[i]];
      head[pos[i]] = i;
    }
  }
  For(i,1,n) block[i] = i/len+1;
  // For(i,1,n) cout << block[i] << " ";
  // puts("");
  For(i,1,m){
    a = read(),b = read(), c = read(), d = read();
    q[i] = (Query){a,b,c,d,i};
  }
  sort(q+1,q+1+m);
  For(i,1,m){
    solve(i);
  }
  sort(q+1,q+1+m,cmp);
  For(i,1,m) cout << q[i].ans2 << " " << q[i].ans << endl;

}
/*
10 5
6 3 4 8 2 3 4 6 2 4
1 10 3 8
5 7 2 7
3 6 2 6
4 8 3 7
2 9 4 8

*/