之前的记录

现在的记录

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9,SqrtN = 359;
int n,m,ans;
struct node{
    int num,id;
} a[N],tmp[N];
bool cmp(node x,node y){
	return x.num < y.num;
}
int block_cnt,block_len;
struct block{
	int l,r;
} b[SqrtN];
int belong[N];
void build_block(){
    block_len = 280;
    block_cnt = (n + block_len - 1) / block_len;
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
int rk[SqrtN][SqrtN];//rk[i][j]：第i块排名为j的数 
int p[N][SqrtN];//p[i][j]：[b[bel[i]].l,i]这一段小于等于此块排名为j的数的个数 
int pre[SqrtN][N];//pre[i][j]：前i块中小于等于j的数的个数 
int rk2[SqrtN][N];//rk2[i][j]：第i块中小于等于j的数的个数（小于等于j的数的最大排名） 
long long ans1[SqrtN][SqrtN][SqrtN];//ans1[i][j][k]：第i块排名前k的数与前j块的数产生的顺序对个数 
int ans2[SqrtN][SqrtN][SqrtN];//ans2[i][j][k]：第i块内从排名j至排名k的顺序对数 
void init(){
	for(int i = 1;i <= block_cnt;i++){
		int l = b[i].l,r = b[i].r;
		sort(tmp + l,tmp + r + 1,cmp);
	}

	//预处理rk 
	for(int i = 1;i <= block_cnt;i++)
		for(int j = b[i].l;j <= b[i].r;j++)
			rk[i][j - b[i].l + 1] = tmp[j].num;

	//预处理p 
	for(int i = 1;i <= block_cnt;i++){
		for(int j = b[i].l;j <= b[i].r;j++)
			p[tmp[j].id][j - b[i].l + 1] = 1;
		for(int j = b[i].l;j <= b[i].r;j++){
			for(int k = 1;k <= b[i].r - b[i].l + 1;k++){
				if(j > b[i].l){
					p[j][k] += p[j][k - 1] + p[j - 1][k] - p[j - 1][k - 1];
				}
				else{
					p[j][k] += p[j][k - 1];
				}
			}
		}
	}

	//预处理pre
	for(int i = 1;i <= block_cnt;i++){
		for(int j = b[i].l;j <= b[i].r;j++)
			pre[i][a[j].num] = 1;
		for(int j = 1;j <= n;j++)
			pre[i][j] = pre[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
	}

	//预处理rk2
	for(int i = 1;i <= block_cnt;i++)
		for(int j = 1;j <= n;j++)
			rk2[i][j] = pre[i][j] - pre[i - 1][j];

	//预处理ans1
	for(int i = 1;i <= block_cnt;i++)
		for(int j = 1;j < i;j++)
			for(int k = 1;k <= b[i].r - b[i].l + 1;k++)
				ans1[i][j][k] = ans1[i][j][k - 1] + pre[j][rk[i][k]];

	//预处理ans2
	for(int i = 1;i <= block_cnt;i++)
		for(int j = 1;j < b[i].r - b[i].l + 1;j++)
			for(int k = j + 1;k <= b[i].r - b[i].l + 1;k++)
				ans2[i][j][k] = ans2[i][j][k - 1] + p[tmp[b[i].l + k - 1].id][k - 1] - p[tmp[b[i].l + k - 1].id][j - 1];
}
int query1(int l,int r,int x,int y){//块内查询 
	int pos = belong[l];
	int ret = 0;
	for(int i = l;i <= r;i++)
		if(a[i].num >= x && a[i].num <= y){
			ret += p[i][rk2[pos][a[i].num - 1]] - p[i][rk2[pos][x - 1]];
			if(l != b[pos].l)
				ret -= p[l - 1][rk2[pos][a[i].num - 1]] - p[l - 1][rk2[pos][x - 1]];
		}
	return ret;
}
int tmp1[N],top1;
int tmp2[N],top2;
int merge(){
	int ret = 0;
	int i = 1,j = 1;
	while(i <= top1 && j <= top2){
		if(tmp1[i] < tmp2[j]){
			i++;
			ret += top2 - j + 1;
		}
		else
			j++;
	}
	return ret;
}
long long query2(int l,int r,int x,int y){//跨块查询 
	int pos_l = belong[l],pos_r = belong[r];
	long long ret = query1(l,b[pos_l].r,x,y) + query1(b[pos_r].l,r,x,y);//散块内部

	//散块对散块
	top1 = top2 = 0;
	for(int i = b[pos_l].l;i <= b[pos_l].r;i++)
		if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
			tmp1[++top1] = tmp[i].num;
	for(int i = b[pos_r].l;i <= b[pos_r].r;i++)
		if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
			tmp2[++top2] = tmp[i].num;
	ret += merge();

	//整块对散块
	//左散块对整块 
	for(int i = b[pos_l].l;i <= b[pos_l].r;i++)
		if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
			ret += (pre[pos_r - 1][y] - pre[pos_r - 1][tmp[i].num]) - (pre[pos_l][y] - pre[pos_l][tmp[i].num]);
	//右散块对整块 
	for(int i = b[pos_r].l;i <= b[pos_r].r;i++)
		if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
			ret += (pre[pos_r - 1][tmp[i].num] - pre[pos_r - 1][x - 1]) - (pre[pos_l][tmp[i].num] - pre[pos_l][x - 1]);

	//整块内部 
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		ret += ans2[i][rk2[i][x - 1] + 1][rk2[i][y]];

	//整块对整块
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		ret += (ans1[i][i - 1][rk2[i][y]] - ans1[i][i - 1][rk2[i][x - 1]]) - (ans1[i][pos_l][rk2[i][y]] - ans1[i][pos_l][rk2[i][x - 1]]);
	//最后要减去[1,x - 1]（前半段值域）对[x,y]（后半段值域） 的贡献
	int temp = 0;
	for(int i = pos_l + 1;i <= pos_r - 1;i++){
		ret -= 1ll * temp * (rk2[i][y] - rk2[i][x - 1]);
		temp += rk2[i][x - 1];
	}
	return ret;
}
signed main(){ 
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++){ 
		cin >> a[i].num;
		a[i].id = i;
		tmp[i] = a[i];
	} 
	build_block();
	init();
	while(m--){
		int x1,x2,y1,y2;
		cin >> x1 >> x2 >> y1 >> y2;
		if(belong[x1] == belong[x2])
			cout << query1(x1,x2,y1,y2) << '\n';
		else
			cout << query2(x1,x2,y1,y2) << '\n';
	}
	return 0; 
}