[NOI2020] 时代的眼泪-526互联

分块。设分出来左散块 \(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;
}