这个空间还能卡吗
查看原帖
这个空间还能卡吗
999274
CNS_5t0_0r2楼主2025/1/19 14:38
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const short SqrtN = 409,SIZE = 1 << 14;
inline char gc(){
    static char buf[SIZE],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,SIZE,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
int n,m;
struct node{
    int num,id;
} a[N],tmp[N];
bool cmp(const node x,const node y){
	return x.num < y.num;
}
short block_cnt,block_len;
struct block{
	int l,r;
} b[SqrtN];
short belong[N];
short p[N][SqrtN];//p[i][j]:[b[bel[i]].l,i]这一段小于等于此块排名为j的数的个数 
int pre[SqrtN][N];//pre[i][j]:前i块中小于等于j的数的个数
int ans1[SqrtN][SqrtN][SqrtN];//ans1[i][j][k]:第i块排名前k的数与前j块的数产生的顺序对个数 
int ans2[SqrtN][SqrtN][SqrtN];//ans2[i][j][k]:第i块内从排名j至排名k的顺序对数 
int query1(const int l,const int r,const int x,const int y){//块内查询 
	const short 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][pre[pos][a[i].num - 1] - pre[pos - 1][a[i].num - 1]] - p[i][pre[pos][x - 1] - pre[pos - 1][x - 1]];
			if(l != b[pos].l)
				ret -= p[l - 1][pre[pos][a[i].num - 1] - pre[pos - 1][a[i].num - 1]] - p[l - 1][pre[pos][x - 1] - pre[pos - 1][x - 1]];
		}
	return ret;
}
int tmp1[N];short top1;
int tmp2[N];short top2;
long long query2(const int l,const int r,const int x,const int y){//跨块查询 
	const short pos_l = belong[l],pos_r = belong[r];
	const int l_l = b[pos_l].l,l_r = b[pos_l].r;
	const int r_l = b[pos_r].l,r_r = b[pos_r].r;
	long long ret = 0;

	//散块内部
	//左散块内部 
	for(int i = l;i <= l_r;i++)
		if(a[i].num >= x && a[i].num <= y){
			ret += p[i][pre[pos_l][a[i].num - 1] - pre[pos_l - 1][a[i].num - 1]] - p[i][pre[pos_l][x - 1] - pre[pos_l - 1][x - 1]];
			if(l != l_l)
				ret -= p[l - 1][pre[pos_l][a[i].num - 1] - pre[pos_l - 1][a[i].num - 1]] - p[l - 1][pre[pos_l][x - 1] - pre[pos_l - 1][x - 1]];
		}
	//右散块内部
	for(int i = r_l;i <= r;i++)
		if(a[i].num >= x && a[i].num <= y)
			ret += p[i][pre[pos_r][a[i].num - 1] - pre[pos_r - 1][a[i].num - 1]] - p[i][pre[pos_r][x - 1] - pre[pos_r - 1][x - 1]];

	//散块对散块
	top1 = top2 = 0;
	for(int i = l_l;i <= l_r;i++)
		if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
			tmp1[++top1] = tmp[i].num;
	for(int i = r_l;i <= r_r;i++)
		if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
			tmp2[++top2] = tmp[i].num;
	short i = 1,j = 1;
	while(i <= top1 && j <= top2){
		if(tmp1[i] < tmp2[j]){
			i++;
			ret += top2 - j + 1;
		}
		else
			j++;
	}

	//整块对散块
	//左散块对整块 
	for(int i = l_l;i <= 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 = r_l;i <= 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(short i = pos_l + 1;i <= pos_r - 1;i++)
		ret += ans2[i][pre[i][x - 1] - pre[i - 1][x - 1] + 1][pre[i][y] - pre[i - 1][y]];

	//整块对整块
	for(short i = pos_l + 1;i <= pos_r - 1;i++)
		ret += (ans1[i][i - 1][pre[i][y] - pre[i - 1][y]] - ans1[i][i - 1][pre[i][x - 1] - pre[i - 1][x - 1]]) - (ans1[i][pos_l][pre[i][y] - pre[i - 1][y]] - ans1[i][pos_l][pre[i][x - 1] - pre[i - 1][x - 1]]);
	//最后要减去[1,x - 1](前半段值域)对[x,y](后半段值域) 的贡献
	int temp = 0;
	for(short i = pos_l + 1;i <= pos_r - 1;i++){
		ret -= 1ll * temp * ((pre[i][y] - pre[i - 1][y]) - (pre[i][x - 1] - pre[i - 1][x - 1]));
		temp += pre[i][x - 1] - pre[i - 1][x - 1];
	}
	return ret;
}
signed main(){ 
	ios::sync_with_stdio(false);
	cout.tie(0);
	n = read();m = read();
	for(int i = 1;i <= n;i++)
		tmp[i] = a[i] = (node){read(),i};


	//建分块 
    block_len = 317;
    block_cnt = (n + block_len - 1) / block_len;
    for(short 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(short i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;


	//预处理 


	//块内排序 
	for(short i = 1;i <= block_cnt;i++){
		const int l = b[i].l,r = b[i].r;
		sort(tmp + l,tmp + r + 1,cmp);
	}

	//预处理p 
	for(short i = 1;i <= block_cnt;i++){
		const int l = b[i].l,r = b[i].r;
		const short len = r - l + 1;
		for(int j = l;j <= r;j++)
			p[tmp[j].id][j - l + 1] = 1;
		for(int j = l;j <= r;j++){
			for(short k = 1;k <= len;k++){
				if(j > 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(short 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];
	}

	//预处理ans1
	for(short i = 1;i <= block_cnt;i++){
		const short len = b[i].r - b[i].l + 1;
		for(short j = 1;j < i;j++)
			for(short k = 1;k <= len;k++)
				ans1[i][j][k] = ans1[i][j][k - 1] + pre[j][tmp[k + b[i].l - 1].num];
	}

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



	while(m--){
		const int x1 = read(),x2 = read(),y1 = read(),y2 = read();
		if(belong[x1] == belong[x2])
			cout << query1(x1,x2,y1,y2) << '\n';
		else
			cout << query2(x1,x2,y1,y2) << '\n';
	}
	return 0; 
}
2025/1/19 14:38
加载中...