P6774 [NOI2020] 时代的眼泪题解
一直在看却不敢写的题，终于写掉了。果然是毒瘤分块题，题解区里很少有代码，只能自己动手写了。
简化题意
求一段区间内值域在
本题最大特点就是分块 + 容斥。
我们采用了在线做法，先预处理出一些东西。
处理内容
我们令
处理方法
-
-
-
-
-
-
预处理总复杂度 $O (n \sqrt n)$，虽然常数可能有点大。
预处理完了，我们需要在
根据 P5046 Ynoi2019 模拟赛Yuno loves sqrt technology 的经验，我们可以得出，答案应该是 散块内部 + 整块内部 + 散块对整块 / 整块对散块 + 整块对整块 + 散块对散块。
具体过程如下
- 散块内部：我们要求出
l \to r 值域在[x,y] 之间的顺序对数，只需求出l \to r 值域在[1,x-1] 之间的顺序对数和l \to r 值域在[1,y] 之间的顺序对数，再减去[1,x-1] 与[x,y] 顺序对数即可。 - 整块内部：我们之前已经预处理好了
sum[i][j][k] ，对每个块加一加即可。 - 散块对整块 / 整块对散块：可以用
pre 数组代求，求对1 \to x 块贡献容斥一下即可。 - 整块对整块：也是容斥用
c 数组处理第i 块1 \to i-1 和1 \to id[l] 间[1,x-1] 和[1,y-1] 之间的贡献。再减去[1,x-1] 与[x,y] 产生的顺序对数，具体的减去每次比x 小的数的顺序对个数，再乘以这块中在[x,y] 间数的顺序对个数。 - 散块对散块：用一次归并排序即可，注意这次求的是顺序对，不是逆序对。
代码如下
#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;
}