分块。设分出来左散块 \(A_1\)，中间块 \(B_1,\cdots,B_k\)，右散块 \(A_2\)。那么贡献有 \(A_1\leftarrow A_1\) 即散块对自己，\(A_1\leftarrow A_2\) 即散块对散块，\(A_i\leftarrow B_j\) 即散块对整块，\(B_i\leftarrow B_j(i\neq j)\) 即整块对整块，\(B_i\leftarrow B_i\) 即整块自己。当然还有同块的情况。
首先带散块的都好做：我们总能拆成 \(O(\sqrt{n})\) 次查询区间 \([l,r]\) 内有多少 \([x,y]\) 中的数这样的询问（下面记这样的查询为查询 \(c(l,r,x,y)\)），离线下来值域分块平衡复杂度即可。
这部分的时间复杂度为 \(O(qB+n\sqrt{n})\)。
如果想要空间线性，发现 \(A_1\leftarrow B,A_1\leftarrow A_2\) 这样的都可以直接在端点处挂一个区间。
但 \(A_1\leftarrow A_1\) 怎么算呢，我们可以把他当作同块，用同块的方法计算。这个我们最后说。
对于整块的情况，首先考虑 \(B_i\leftarrow B_i\)，发现由于一块内只有 \(O(B)\) 个数，我们预处理 \(\text{ans}(x,y)\) 表示如果询问的 \(u,d\) 在块内排名分别是 \(x,y\) 的答案即可。这部分复杂度为 \(O(nB+\frac{qn}{B})\)。为了找排名还需要处理 \(\text{rank}(i,j)\) 表示 \(i\) 这个数在 \(j\) 块中的排名，这部分也是 \(O(nB)\)。
然后再考虑 \(B_i\leftarrow B_j\)。考虑差分成值域 \([1,d]-[1,u-1]-[1,u-1]\times [u,d]\)，发现最后一种是好算的：只需要查询 \([l,r]\) 这些块中值在 \([x,y]\) 中的元素个数 \((1\le l,r\le \frac{n}{B})\)。
考虑 \([1,u-1]\times [u,d]\) 怎么算，写一下式子，设 \(L,R\) 为这些整块的左右边界，\(g(l,r,x,y)\) 表示 \(l\cdots r\) 这些块中值在 \([x,y]\) 中的元素个数，那么这部分就是
\[\begin{aligned} &\sum_{i=L}^Rg(L,i-1,1,u-1)\times g(i,i,u,d)\\ =&\sum_{i=L}^Rg(1,i-1,1,u-1)\times g(i,i,u,d)-g(1,L-1,1,u-1)\times g(i,i,u,d)\\ =&-g(1,L-1,1,u-1)\times (g(1,R,u,d)-g(1,L-1,u,d))\\+&\sum_{i=L}^Rg(1,i-1,1,u-1)\times g(i,i,u,d) \end{aligned} \]那这样就很容易做到线性空间了。
如果想要空间线性，只需要对每块单独做。
那还需要查询一些块的 \([1,d]\) 的贡献。考虑从小到大加入每个数，并维护 \(s_{i,j}\) 表示 \([i,j-1]\) 中的块对第 \(j\) 块的答案贡献，那么如果在 \(x\) 这个块内插入了一个数，只会把 \(s_{i,x}\leftarrow s_{i,x}+\text{cnt}(i,x-1)\)，其中 \(\text{cnt}(l,r)\) 表示当前 \([l,r]\) 这些块内已经插入了多少个数。\(\text{cnt}\) 可以用前缀和维护。
\([l,r]\) 块的答案就是 \(\sum_{i=l}^rs_{l,i}\)。那这部分复杂度是 \(O(\frac{n^2}{B})\)，且空间复杂度天然是线性。
对于同块的情况，朴素的想法是直接拆成 \(O(\sqrt{n})\) 次查询 \(c(l,r,x,y)\)，但是空间不好卡。考虑再分一次块，把这个散块分成长度为 \(S\) 的块，每块内直接暴力 \(O(S^2)\) 算，块之间就直接加询问，那么这部分的时间复杂度是 \(O(\frac{qB}{S}+qBS)\)。注意由于暴力的那些块长加起来是 \(B\)，因此暴力的复杂度是 \(O(BS)\) 而非 \(O(BS^2)\)。
如果只看时间，我们应当取 \(S=1\)；但空间复杂度其实是 \(O(\frac{qB}{S})\)，我们可以偷偷调整 \(B\) 和 \(S\) 的值（不是）并假装他是线性。
取 \(B=O(\sqrt{n})\)，那么总的复杂度是 \(O((n+q)\sqrt{n})\)，空间是（迫真）线性的，可以通过 P6579。
//-DYUNQIAN -std=c++14 -O2 -Wall
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void Assert(bool c,int L=0){if(!c){cout<<"Assertion Failed at "<<L<<endl;exit(0);}}
const int N=1e5+5;
const int M=2e5+5;
const int B=500;
const int NB=500;
int n,m;
namespace ds{// O(sqrtn) add O(1) sum
int sumb[B+5],sum[N],st[NB+5],ed[NB+5],bl[N];
void build(int siz){
memset(st,63,sizeof(st));
for(int i=1;i<=n;i++)bl[i]=(i-1)/siz+1,ed[bl[i]]=i,st[bl[i]]=min(st[bl[i]],i);
}
void add(int x){
for(int i=x;i<=ed[bl[x]];i++)sum[i]++;
for(int i=bl[x];i<=bl[n];i++)sumb[i]++;
}
int qsum(int l,int r){
if(l>r)return 0;
int ql=bl[l],qr=bl[r];
if(ql==qr)return sum[r]-(l==st[ql]?0:sum[l-1]);
int ans=sumb[qr-1]-sumb[ql];
ans+=sum[r],ans+=sum[ed[ql]]-(l==st[ql]?0:sum[l-1]);
return ans;
}
};
int st[NB+5],ed[NB+5],bl[N],S,Sq,a[N];
struct Q{
int l,r,vl,vr,f,id,typ;// type = 1 : [a[i],n] & [vl,vr] | type = 2 : [1,a[i]] & [vl,vr]
Q(int L=0,int R=0,int VL=0,int VR=0,int F=0,int ID=0,int Ty=0):l(L),r(R),vl(VL),vr(VR),f(F),id(ID),typ(Ty){}
};
vector<Q>qs[N];
ll ans[M];
void addq(int l,int r,int u,int d,int ql,int qr,int id,int typ){
if(l>r||ql>qr)return ;
// type = 1 : sum{i = l...r}sum{j = ql...qr} u <= a[i] < a[j] <= d ( l<=r<=ql<=qr )
// type = 2 : sum{i = l...r}sum{j = ql...qr} u <= a[j] < a[i] <= d ( ql<=qr<=l<=r )
if(typ==1)Assert(l<=r&&r<=ql&&ql<=qr);
if(typ==2)Assert(ql<=qr&&qr<=l&&l<=r);
qs[qr].emplace_back(Q(l,r,u,d,1,id,typ));
qs[ql-1].emplace_back(Q(l,r,u,d,-1,id,typ));
}
void solveA(int l,int r,int u,int d,int id){
if(l>r)return ;
int qr=min(l+Sq-1,r);
for(int i=l;i<=qr;i++)if(u<=a[i]&&a[i]<=d)for(int j=i+1;j<=qr;j++)if(a[i]<=a[j]&&a[j]<=d)ans[id]++;
addq(l,qr,u,d,qr+1,r,id,1),solveA(qr+1,r,u,d,id);
}
int pr[N],sf[N],res[B+5][B+5];
struct qry{int l,r,u,d;}ques[M];
vector<int>lsh;
int b[N],cur[N],num[N],mul[M];
void solveB(int l,int r){
lsh.clear();int V=r-l+1;lsh.resize(V+2);int c=bl[l];
for(int i=l;i<=r;i++)lsh[i-l]=a[i];lsh[V]=0,lsh[V+1]=n+1;
sort(lsh.begin(),lsh.end());
for(int i=1;i<=V+1;i++){
for(int j=lsh[i-1]+1;j<=lsh[i];j++)sf[j]=i;
for(int j=lsh[i-1];j<lsh[i];j++)pr[j]=i-1;
}
for(int i=l;i<=r;i++)b[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin();
for(int i=l;i<=r;i++){
for(int j=i+1;j<=r;j++)if(b[i]<b[j])res[b[i]][b[j]]++;
}
for(int i=V;i>=1;i--)for(int j=i;j<=V;j++)res[i][j]+=res[i+1][j]+res[i][j-1]-res[i+1][j-1];
for(int i=l;i<=r;i++)cur[a[i]]++;
for(int i=1;i<=n;i++)cur[i]+=cur[i-1];
for(int i=1;i<=m;i++){
auto t=ques[i];int ql=bl[t.l],qr=bl[t.r];
if(ql==qr)continue;
if(ql<c&&c<qr)ans[i]+=res[sf[t.u]][pr[t.d]];
if(ql<c&&c<qr)ans[i]-=1ll*(cur[t.d]-cur[t.u-1])*num[t.u-1];
if(c==ql+1&&ql<qr-1)mul[i]=num[t.u-1],ans[i]-=1ll*(num[t.d]-num[t.u-1])*num[t.u-1];
if(c==qr&&ql<qr-1)ans[i]+=1ll*(num[t.d]-num[t.u-1])*mul[i];
}
for(int i=1;i<=n;i++)num[i]+=cur[i],cur[i]=0;
for(int i=1;i<=V;i++)for(int j=1;j<=V;j++)res[i][j]=0;
}
int con[NB+5][NB+5],cnt[NB+5],pos[N];
struct Qs{
int l,r,f,id;
Qs(int L=0,int R=0,int F=0,int ID=0):l(L),r(R),f(F),id(ID){}
};
vector<Qs>vec[N];
void solve(int l,int r,int u,int d,int id){
int ql=bl[l],qr=bl[r];
if(ql==qr){solveA(l,r,u,d,id);return ;}
solveA(l,ed[ql],u,d,id),solveA(st[qr],r,u,d,id);
vec[d].emplace_back(Qs(ql+1,qr-1,1,id));
vec[u-1].emplace_back(Qs(ql+1,qr-1,-1,id));
addq(l,ed[ql],u,d,ed[ql]+1,r,id,1),addq(st[qr],r,u,d,ed[ql]+1,st[qr]-1,id,2);
}
signed main(void){
#ifdef YUNQIAN
freopen("tears.in","r",stdin);
freopen("tears.out","w",stdout);
#endif
n=read(),m=read();
S=200,Sq=35;
for(int i=1;i<=n;i++)a[i]=read();memset(st,63,sizeof(st));
for(int i=1;i<=n;i++)bl[i]=(i-1)/S+1,st[bl[i]]=min(st[bl[i]],i),ed[bl[i]]=i;
for(int i=1;i<=m;i++){
int l=read(),r=read(),u=read(),d=read();
ques[i].l=l,ques[i].r=r,ques[i].u=u,ques[i].d=d;
solve(l,r,u,d,i);
}
for(int i=1;i<=n;i+=S)solveB(i,min(i+S-1,n));
ds::build(300);
for(int i=1;i<=n;i++){
ds::add(a[i]);
for(auto t:qs[i]){
for(int j=t.l;j<=t.r;j++){
int ql=t.vl,qr=t.vr;
if(a[j]<ql||a[j]>qr)continue;
if(t.typ==1)ql=max(ql,a[j]);
if(t.typ==2)qr=min(qr,a[j]);
if(t.f==1)ans[t.id]+=ds::qsum(ql,qr);
else ans[t.id]-=ds::qsum(ql,qr);
}
}
}
for(int i=1;i<=n;i++)pos[a[i]]=i;
for(int i=1;i<=n;i++){
int p=pos[i],bp=bl[p];
for(int j=1;j<bp;j++)con[j][bp]+=cnt[bp-1]-cnt[j-1];
for(int j=bp;j<=bl[n];j++)cnt[j]++;
for(auto t:vec[i]){
for(int j=t.l+1;j<=t.r;j++){
if(t.f==1)ans[t.id]+=con[t.l][j];
else ans[t.id]-=con[t.l][j];
}
}
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}