RT

虽然蒟蒻我是个大常数选手 但是这题真的好卡常啊 好像很多人都被卡常了（

今天都交了一板多了 卡常杀我也

求大佬帮忙卡常

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m;
int len;
int num;
int bel[100010];
int st[320],ed[320];
int a[100010];
int maxpos[320][100010];
int m1[320][320][320];
int m2[320][100010];
int m3[320][320];
int m4[320][320][320];
ll m5[320][320][320];
int m6[320][320][320];
struct node{
	int pos;
	int val;
};
vector<node> tmp;
bool operator <(node a,node b){
	return a.val<b.val;
}
void pre(){
	len=sqrt(n);
	for(int i=1;i<=n;i+=len){
		st[++num]=i,ed[num]=min(i+len-1,n);
		for(int j=i;j<=i+len-1&&j<=n;++j){
			bel[j]=num;
		}
	}
	for(int i=1;i<=num;++i){
		tmp.clear();
		for(int j=st[i];j<=ed[i];++j){
			tmp.push_back({j-st[i]+1,a[j]});
		}
		sort(tmp.begin(),tmp.end());
		int now=1;
		while(now<tmp[0].val&&now<=n){
			maxpos[i][now]=0;
			now++;
		}
		for(int j=0;j<tmp.size();++j){
			while((j==tmp.size()-1&&now<=n)||now<tmp[j+1].val){
				maxpos[i][now]=j+1;
				now++;
			}
			m1[i][tmp[j].pos][j+1]++;
			for(int k=0;k<j;++k){
				if(tmp[k].pos<tmp[j].pos){
					m3[i][j+1]++;
					m6[i][k+1][j+1]++;
				}
			}
		}
		for(int j=1;j<=ed[i]-st[i]+1;++j){
			for(int k=1;k<=ed[i]-st[i]+1;++k){
				m1[i][j][k]+=m1[i][j-1][k]+m1[i][j][k-1]-m1[i][j-1][k-1];
			}
		}
		for(int j=1;j<=n;++j){
			m2[i][j]=m1[i][ed[i]-st[i]+1][maxpos[i][j]];
			m2[i][j]+=m2[i-1][j];
		}
		for(int j=0;j<tmp.size();++j){
			m3[i][j+1]+=m3[i][j];
		}
		for(int j=1;j<i;++j){
			for(int k=0;k<tmp.size();++k){
				m4[i][j][k+1]+=m4[i][j-1][k+1]+(m2[j][tmp[k].val]-m2[j-1][tmp[k].val]);
				m5[i][j][k+1]+=0ll+m5[i][j][k]+m4[i][j][k+1];
			}
		}
		for(int j=0;j<tmp.size();++j){
			for(int k=0;k<tmp.size();++k){
				m6[i][j+1][k+1]+=m6[i][j][k+1]+m6[i][j+1][k]-m6[i][j][k];
			}
		}
	}
}
ll query(int l,int r,int d,int u){
	ll ret=0;
	if(bel[l]==bel[r]){
		int bl=bel[l];
		for(int i=l;i<=r;++i){
			if(a[i]<d||a[i]>u)continue;
			ret+=0ll
				+m1[bl][i-st[bl]+1][maxpos[bl][a[i]-1]]
				-m1[bl][l-st[bl]][maxpos[bl][a[i]-1]]
				-m1[bl][i-st[bl]+1][maxpos[bl][d-1]]
				+m1[bl][l-st[bl]][maxpos[bl][d-1]];
		}
		return ret;
	}
	int bl=bel[l]+1,br=bel[r]-1;
	int L=st[bl],R=ed[br];
	for(int i=l;i<L;++i){
		if(a[i]<d||a[i]>u)continue;
		ret+=0ll
			+m1[bl-1][i-st[bl-1]+1][maxpos[bl-1][a[i]-1]]
			-m1[bl-1][l-st[bl-1]][maxpos[bl-1][a[i]-1]]
			-m1[bl-1][i-st[bl-1]+1][maxpos[bl-1][d-1]]
			+m1[bl-1][l-st[bl-1]][maxpos[bl-1][d-1]];
		ret+=m2[br][u]-m2[bl-1][u]-m2[br][a[i]]+m2[bl-1][a[i]];
	}
	for(int i=R+1;i<=r;++i){
		if(a[i]<d||a[i]>u)continue;
		ret+=0ll
			+m1[br+1][i-R][maxpos[br+1][a[i]-1]]
			-m1[br+1][i-R][maxpos[br+1][d-1]];
		ret+=0ll
			+m1[bl-1][ed[bl-1]-st[bl-1]+1][maxpos[bl-1][a[i]]]
			-m1[bl-1][ed[bl-1]-st[bl-1]+1][maxpos[bl-1][d-1]]
			-m1[bl-1][l-st[bl-1]][maxpos[bl-1][a[i]]]
			+m1[bl-1][l-st[bl-1]][maxpos[bl-1][d-1]];
		ret+=0ll
			+m2[br][a[i]]-m2[bl-1][a[i]]-m2[br][d-1]+m2[bl-1][d-1];
	}
	for(int i=bl;i<=br;++i){
		ret+=0ll
			+m3[i][maxpos[i][u]]
			+m5[i][i-1][maxpos[i][u]]
			-m5[i][bl-1][maxpos[i][u]];
		ret-=0ll
			+m3[i][maxpos[i][d-1]]
			+m5[i][i-1][maxpos[i][d-1]]
			-m5[i][bl-1][maxpos[i][d-1]];
		ret-=1ll
			*(m2[i-1][d-1]-m2[bl-1][d-1])
			*(0ll+m1[i][ed[i]-st[i]+1][maxpos[i][u]]-m1[i][ed[i]-st[i]+1][maxpos[i][d-1]]);
		ret-=0ll
			+m6[i][maxpos[i][d-1]][maxpos[i][u]]-m6[i][maxpos[i][d-1]][maxpos[i][d-1]];
	}
	return ret;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	pre();
	for(int i=1;i<=m;++i){
		int l,r,d,u;
		l=read(),r=read(),d=read(),u=read();
		printf("%lld\n",query(l,r,d,u));
	}
}