自动搬运

查看原文

来自洛谷，原作者为

	louhao088 这个家伙不懒，但还是什么都没留下

搬运于2025-08-24 22:23:50，当前版本为作者最后更新于2021-07-27 15:55:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一直在看却不敢写的题，终于写掉了。果然是毒瘤分块题，题解区里很少有代码，只能自己动手写了。

简化题意

求一段区间内值域在 $[x,y]$ 间的顺序对个数，具体来说就是 P5046 Ynoi2019 模拟赛Yuno loves sqrt technology I 的加强版。或许大佬用矩阵做的，但小蒟蒻认为这样最容易理解。

本题最大特点就是分块 + 容斥。

我们采用了在线做法，先预处理出一些东西。

处理内容

我们令 $rk[i][j]$ 表示第 $i$ 块排名为 $j$ 的数，$p[i][j]$ 表示第 $i$ 个数与其所在块左边这一段小于此块排名为 $j$ 的数的个数，$pre[i][j]$ 表示前 $i$ 个块小于等于 $j$ 的数的个数。$lsh[i][j]$ 表示第 $i$ 块小于等于 $j$ 最大排名，$c[i][j][k]$ 第 $i$ 块与前 $j$ 块排名前 $k$ 个数产生顺序对的个数 ，$sum[i][j][k]$ 表示第 $i$ 块从排名 $j$ 至排名 $k$ 之间顺序对数 ，$L[i],R[i]$ 分别表示一个块的左右区间， $id[i]$ 表示一个数所属的块 ， $pos[i]$ 表示一个块里第 $i$ 名的位置 。

处理方法

1. $rk$ 数组：这很好处理，因为是一个排列，故我们只要把每个块从小到大排个序，记录一下就好了。

2. $p$ 数组：可以与$rk$ 数组同时处理，对每个数，在 $p[位置][排名]$ 处标上 1 ，做一遍二维前缀和就好了。注意不能在 $j=L[id[j]]$ 时加前缀和，这会使答案加上前一个块。

3. $pre$ 数组：对于 $pre$ 数组也是同样的处理方式，对每个数，在 $pre[块的标号][值]$ 标上 1，然后在每个块中做一次二维前缀和即可。

4. $lsh$ 数组：这也很好处理 , 然而蒟蒻最开始处理错了 ，就是在每两个值之间，给它标上前一个块内值的排名。

5. $c$ 数组：我们发现可以用 $pre$ 数组代求。具体的 $c[i][j][k]=pre[j][rk[i][k]]+c[i][j][k-1]$ ，就是这个值产生的顺序对，加上之前值产生的顺序对。

6. $sum$ 数组： 可以用 $p$ 数组代求。具体的 $sum[i][j][k]=sum[i][j][k-1]+p[pos[k]][k-1]-p[pos[k]][j-1]$ 。就是之前的顺序对数加上第 $k$ 名产生的顺序对数。

预处理总复杂度 $O (n \sqrt n)$，虽然常数可能有点大。

预处理完了，我们需要在 $O (\sqrt n)$ 内求出答案。

根据 P5046 Ynoi2019 模拟赛Yuno loves sqrt technology 的经验，我们可以得出，答案应该是 散块内部 + 整块内部 + 散块对整块 / 整块对散块 + 整块对整块 + 散块对散块。

具体过程如下

1. 散块内部：我们要求出 $l \to r$ 值域在 $[x,y]$ 之间的顺序对数，只需求出 $l \to r$ 值域在 $[1,x-1]$ 之间的顺序对数和 $l \to r$ 值域在 $[1,y]$ 之间的顺序对数，再减去 $[1,x-1]$ 与 $[x,y]$ 顺序对数即可。
2. 整块内部：我们之前已经预处理好了 $sum[i][j][k]$ ，对每个块加一加即可。
3. 散块对整块 / 整块对散块：可以用 $pre$ 数组代求，求对 $1 \to x$ 块贡献容斥一下即可。
4. 整块对整块：也是容斥用 $c$ 数组处理第 $i$ 块 $1 \to i-1$ 和 $1 \to id[l]$ 间 $[1,x-1]$ 和 $[1,y-1]$ 之间的贡献。再减去 $[1,x-1]$ 与 $[x,y]$ 产生的顺序对数，具体的减去每次比 $x$ 小的数的顺序对个数，再乘以这块中在 $[x,y]$ 间数的顺序对个数。
5. 散块对散块：用一次归并排序即可，注意这次求的是顺序对，不是逆序对。

代码如下

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define re register
const int maxn=1e5+5,B=345;
inline int read()
{
	char ch=getchar();bool f=0;int x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
void print(long long x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
struct node{int x,id;}a[maxn],b[maxn];
int n,m,l,r,x,y,t,g,L[B],R[B],lx[maxn],ly[maxn],id[maxn];
int rk[B][B];//第i块排名为j的数 
int p[maxn][B];//第i个数与其所在块左边这一段小于此块排名为j的数的个数 
int pre[B][maxn]; //前i块中 小于等于j的数的个数 
int lsh[B][maxn];//第i块小于等于j最大排名 
long long c[B][B][B];//第i块与前j块排名前k个数产生顺序对的个数 
int sum[B][B][B];//第i块从排名j至排名k之间顺序对数 
int msort(int l,int r)
{
	int tot=0,res=0;
	int i=1,j=1;
	for(;i<=l&&j<=r;)
		if(lx[i]<ly[j])i++,res+=r-j+1;
		else j++;
	return res;
}
bool cmp(node a,node b){return a.x<b.x;}
inline int query1(int l,int r,int x,int y)
{
	int res=0,h=id[l];int g=lsh[h][x-1];
	for(int i=l;i<=r;i++)
		if(a[i].x<=y&&a[i].x>=x)
		{
			res+=p[i][lsh[h][a[i].x-1]]-p[i][g];
			if(l!=L[h])res=res-p[l-1][lsh[h][a[i].x-1]]+p[l-1][g];
		}
			
	return res;
}
inline long long query2(int l,int r,int x,int y)
{
	long long res=0;res=query1(l,R[id[l]],x,y)+query1(L[id[r]],r,x,y); 
	int s1=0,s2=0;
	for(re int i=L[id[l]];i<=R[id[l]];i++)
		if(b[i].id>=l&&b[i].x<=y&&b[i].x>=x)lx[++s1]=b[i].x,
		res+=pre[id[r]-1][y]-pre[id[r]-1][b[i].x]-pre[id[l]][y]+pre[id[l]][b[i].x];
	for(re int i=L[id[r]];i<=R[id[r]];i++)
		if(b[i].id<=r&&b[i].x<=y&&b[i].x>=x)ly[++s2]=b[i].x,
		res+=pre[id[r]-1][b[i].x]-pre[id[r]-1][x-1]-pre[id[l]][b[i].x]+pre[id[l]][x-1];
	
	res+=msort(s1,s2);int num=0;
	for(int i=id[l]+1;i<=id[r]-1;i++)
	{
		res+=sum[i][lsh[i][x-1]+1][lsh[i][y]];
		res+=c[i][i-1][lsh[i][y]]-c[i][id[l]][lsh[i][y]]-c[i][i-1][lsh[i][x-1]]+c[i][id[l]][lsh[i][x-1]]
		-num*(lsh[i][y]-lsh[i][x-1]);
		num+=lsh[i][x-1];
	}
	return res;
}
signed main()
{
	//freopen("t.in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();m=read();t=sqrt(n);g=(n-1)/t+1;
	for(re int i=1;i<=n;i++)a[i].x=read(),a[i].id=i,b[i]=a[i],id[i]=(i-1)/t+1;
	for(re int i=1;i<=g;i++)
	{
		L[i]=R[i-1]+1,R[i]=min(i*t,n);
		int l=L[i],r=R[i];
		sort(b+l,b+r+1,cmp);int h=1;
		for(int j=1;j<b[l].x;j++)lsh[i][j]=0;h=b[l].x;
		for(re int j=l;j<=r;j++)
		{
			rk[i][j-l+1]=b[j].x,p[b[j].id][j-l+1]=1,pre[i][a[j].x]=1;
			int u=b[j+1].x;if(j==r)u=n+1;
			for(int k=h;k<u;k++)lsh[i][k]=j-l+1;h=b[j+1].x;
		}
		for(re int j=l;j<=r;j++)
			for(re int k=1;k<=r-l+1;k++)
			{
				if(j!=l)
					p[j][k]=p[j][k]+p[j-1][k]+p[j][k-1]-p[j-1][k-1];
				else p[j][k]=p[j][k]+p[j][k-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];
		for(re int j=1;j<i;j++)
			for(re int k=1;k<=r-l+1;k++)
				c[i][j][k]=pre[j][rk[i][k]]+c[i][j][k-1];
		for(re int j=1;j<=r-l+1;j++)
			for(re int k=j+1;k<=r-l+1;k++)
				 sum[i][j][k]=sum[i][j][k-1]+p[b[k+l-1].id][k-1]-p[b[k+l-1].id][j-1];
	}
	for(int i=1;i<=m;i++)
	{
		l=read(),r=read(),x=read(),y=read();
		if(id[l]==id[r])
			print(query1(l,r,x,y)),puts("");
		else print(query2(l,r,x,y)),puts("");
	}
 	return 0;
}