分块做法，块长调小了会 WA，求高人指点

#include<bits/stdc++.h>
#define pb push_back
#define tbc '\n'

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

//fast IO
#define _r return *this
#define _o &operator
namespace IO { const int _S = 1 << 20; char b[_S], *p1 = b, *p2 = b, pb[_S], *pp = pb;
    void fl() { fwrite(pb, 1, pp - pb, stdout), pp = pb; }
    struct fr { char gc() { if (p1 == p2) p2 = (p1 = b) + fread(b, 1, _S, stdin); return p1 == p2 ? ' ' : *p1++; }
        fr _o>>(char &c) { do c = gc(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t'); _r; }
        template <class T> fr _o>>(T &x) { char c = gc(); T f = 1; for (x = 0; !isdigit(c);) (c == '-' ? f = -1 : 1),
            c = gc(); while (isdigit(c)) x = (x * 10) + (c ^ 48), c = gc(); x *= f; _r; } fr() {} } in;
    struct fw { void pt(char c) { *pp++ = c; if (pp - pb == _S) fl(); } fw _o<<(char c) { pt(c); _r; }
        template <class T> fw _o<<(T x) { if (!x) { pt(48); _r; } if(x < 0) pt('-'), x = -x;
            static int s[64], t; t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) pt(s[t--] + 48); _r; }
        fw _o<<(const char *s) { int c = 0; while (s[c]) pt(s[c++]); _r; }  fw() {} } out;
struct fe { ~fe() { fl(); } } fls; } using IO::in; using IO::out;
//end fast IO

const int N=1e5+233,M=2e5+233;
const int K=512,B=N/K+5;
int n,m,a[N],pos[N];
struct querys
{
	int l,r,a,b;
}q[M];
ll ans[M];
struct Qry
{
	int l,r,a,b,v,id;
};
vector<Qry> v[N],w[B],o[N];
int L[B],R[B],bel[N],lxl;
int c[N],b[B];
inline void udt(int x,int k)
{
	for (int i=x;bel[i]==bel[x];i++) c[i]+=k;
	for (int i=bel[x]+1;i<=lxl;i++) b[i]+=k;
}
inline int qry(int l,int r)
{
	return c[r]+b[bel[r]]-c[l-1]-b[bel[l-1]];
}
int f[K+5][K+5],lsh[N],inv[N],cnt[M];

int main()
{
	in>>n>>m;
	for (int i=1;i<=n;i++) in>>a[i],pos[a[i]]=i;
	lxl=(n-1)/K+1;
	for (int i=1;i<=lxl;i++)
	{
		L[i]=R[i-1]+1,R[i]=min(n,i*K);
		for (int j=L[i];j<=R[i];j++) bel[j]=i;
	}
	for (int i=1;i<=m;i++)
	{
		int l,r,u,d;
		in>>l>>r>>u>>d;
		int bl=(l-1)/K+1,br=(r-1)/K+1;
		if (bl==br) w[bl].pb({l,r,u,d,1,i});
		else
		{
			w[bl].pb({l,R[bl],u,d,1,i}),w[br].pb({L[br],r,u,d,1,i});
			v[R[br-1]].pb({L[br],r,u,d,1,i}),v[l-1].pb({L[br],r,u,d,-1,i});
			if (bl+2<=br)
			{
				v[R[br-1]].pb({l,R[bl],u,d,1,i}),v[R[bl]].pb({l,R[bl],u,d,-1,i});
				o[d].pb({bl+1,br-1,u,d,1,i}),o[u-1].pb({bl+1,br-1,u,d,-1,i});
			}
		}
		q[i].l=l,q[i].r=r,q[i].a=u,q[i].b=d;
	}
	for (int i=1;i<=n;i++)
	{
		udt(a[i],1);
		for (auto j:v[i])
		{
			for (int k=j.l;k<=j.r;k++)
			{
				int u=j.a,d=j.b;
				if (i<k) d=min(d,a[k]-1);
				else u=max(u,a[k]+1);
				if (u<=d&&j.a<=a[k]&&a[k]<=j.b) ans[j.id]+=j.v*qry(u,d);
			}
		}
	}
	for (int i=1;i<=lxl;i++)
	{
		memset(c,0,sizeof c),memset(b,0,sizeof b);
		for (int j=L[i];j<=R[i];j++)
		{
			for (auto k:w[i])
			{
				if (k.l<=j&&j<=k.r&&k.a<=a[j]&&a[j]<=k.b) ans[k.id]+=qry(k.a,a[j]);
				if (k.l==j) 
					for (int l=k.l;l<=k.r;l++)
						if (k.a<=a[l]&&a[l]<=k.b) ans[k.id]-=qry(k.a,a[l]);
			}
			udt(a[j],1);
		}
		int len=R[i]-L[i]+1;
		for (int j=1;j<=n;j++)
		{
			if (L[i]<=pos[j]&&pos[j]<=R[i]) lsh[j]=lsh[j-1]+1,inv[lsh[j]]=j;
			else lsh[j]=lsh[j-1];
		}
		for (int l=2;l<=len;l++)
			for (int j=1,k=l;k<=len;j++,k++)
				f[j][k]=f[j+1][k]+f[j][k-1]-f[j+1][k-1]+(pos[inv[j]]<pos[inv[k]]);
		for (int j=1;j<=m;j++)
			if (bel[q[j].l]<i&&i<bel[q[j].r])
				ans[j]+=f[lsh[q[j].a]+(lsh[q[j].a]==lsh[q[j].a-1])][lsh[q[j].b]]-cnt[j]*(lsh[q[j].b]-lsh[q[j].a-1]),cnt[j]+=lsh[q[j].a-1];
	}
	memset(b,0,sizeof b),memset(f,0,sizeof f);
	for (int i=1;i<=n;i++)
	{
		int bi=bel[pos[i]];
		b[bi]++;
		for (int j=bi-1,s=0;j;j--)
			s+=b[j],f[j][bi]+=s;
		for (auto j:o[i])
			for (int k=j.l;k<=j.r;k++)	
				ans[j.id]+=j.v*f[j.l][k];
	}
	for (int i=1;i<=m;i++)
		out<<ans[i]<<tbc;

	return 0;
}