自动搬运

查看原文

来自洛谷，原作者为

	Umbrella_Leaf 曹刘生子，当如孙仲谋。

搬运于2025-08-24 22:38:52，当前版本为作者最后更新于2022-10-08 20:25:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

做的时候找了半天都没有找到详细的题解，只能自己写一个。

题意

给出排列 $a_1,a_2,\cdots,a_n$，你需要维护一个初始全 $0$ 的序列 $b$。$m$ 次操作：

1 l r：对于每对 $l\le i\le j\le r$ 且 $a_i\le a_j$，$b_j\gets b_j+1$。

2 x：查询 $b_x$。

$n,m\le 2\times 10^5$。

题解

对序列以 $\sqrt n$ 为块长分块。

对于一次修改的贡献，我们拆成 $5$ 个部分：

1. 左散块对左散块，右散块对右散块，或者 $l,r$ 在同一块；
2. 整块对整块（包括同一个整块内部）；
3. 整块对右散块；
4. 左散块对右散块；
5. 左散块对整块。

其中，“X 对 Y”表示 $i$ 在 X 中、$j$ 在 Y 中。

接下来分别考虑。

一、左散块对左散块/右散块对右散块/$l,r$ 在同一块

预处理 $pnum_{i,j,k}$ 表示第 $i$ 块的前 $k$ 个元素中小于等于第 $i$ 块第 $j$ 个元素的有多少个。修改时暴力在答案数组上加。

二、整块对整块

预处理 $num_{i,j}$ 表示第 $i$ 块中小于等于 $a_j$ 的有多少个。

对每个整块，我们记录前面每一块对它有多少次贡献。

修改：对一段区间内的每个块，左边一段区间内的块对它贡献 $+1$。

询问：扫描 $x$ 所在块左边的块，查询它们对 $x$ 所在的块贡献了多少次，乘上『这个块里小于等于 $a_x$ 的数量』后累加到答案。

维护贡献次数的差分数组即可。

注意同一块内部的贡献需要特殊处理。

三、整块对右散块

预处理 $prenum_{i,j}$ 表示前 $i$ 块中小于等于 $a_j$ 的有多少个。

修改时，对于右散块的每个元素暴力更新答案。

四、左散块对右散块

预处理 $id_{i,j}$ 表示第 $i$ 块第 $j$ 小的数在哪个位置。

使用双指针更新答案，具体不好描述，可浏览代码。

五、左散块对整块

最复杂的部分。

我们建立一个平面，$x$ 坐标是块编号，$y$ 坐标是 $a$ 值。假设 $pos_i$ 是下标 $i$ 所在的块。

• 修改 $(l,r)$：对于左散块每个点 $i$，在 $(pos_l+1,a_i)$ 上 $+1$，在 $(pos_r,a_i)$ 上 $-1$。

• 查询 $i$：查询 $x$ 坐标 $\le pos_i$，$y$ 坐标 $\le a_i$ 的点权值和。

转化成 $O(n\sqrt n)$ 次单点修改和 $O(n)$ 次二维数点。

先将 $x$ 坐标按照 $\sqrt[4]n$ 为块长分块。对于每个 $x$ 坐标上的整块和单点，我们需要支持：

• 修改：$O(n)$ 次连续在 $O(\sqrt n)$ 个位置单点修改。

• 查询：$O(n\sqrt[4]n)$ 次查询前缀和。

在 $y$ 坐标上继续以 $\sqrt n$ 为块长分块。把前缀和拆成整块和的前缀和和散块块内前缀和。

对于整块，我们维护前若干块内的和。修改时先差分出每个块内的和，然后暴力修改，最后再做前缀和。

而对于每个散块，我们要做的：

• 修改：$O(n\sqrt n)$ 次单点修改。

• 查询：$O(n\sqrt[4]n)$ 次查询前缀和。

貌似没区别？但是序列长度变成了 $O(\sqrt n)$。

所以再套一个以 $O(\sqrt[4]n)$ 为块长的分块，支持 $O(1)$ 单点修改和 $O(\sqrt[4]n)$ 前缀查询即可。

总复杂度 $O(n\sqrt n)$。

代码

比较丑陋，见谅。

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+(c^'0'),c=getchar();
	return x;
}
#define ll long long
int n,m;
const int B1=460,B2=23;
int a[200005];
int pos[200005],poss[465],L[465],R[465],L1[25],R1[25];
int num[465][200005],prenum[465][200005];
int pnum[465][465][465];
int id[465][465];
int times[465][465];
ll ans[200005];
int xbyb[25][465],xpyb[465][465],xbypyb[25][465][25],xbypyp[25][465][465],xpypyb[465][465][25],xpypyp[465][465][465];
//b 表示 block 块，p 表示 point 单点
bool cmp(int x,int y){return a[x]<a[y];}
int main(){
	n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        pos[i]=(i-1)/B1+1;
        if(!L[pos[i]])L[pos[i]]=i;
        R[pos[i]]=i;
    }
    for(int i=1;i<=B1;i++){
        poss[i]=(i-1)/B2+1;
        if(!L1[poss[i]])L1[poss[i]]=i;
        R1[poss[i]]=i;
    }
    for(int i=1;i<=pos[n];i++){//预处理
        for(int j=L[i];j<=R[i];j++)num[i][a[j]]++;
        for(int j=1;j<=n;j++)num[i][j]+=num[i][j-1],prenum[i][j]=num[i][j]+prenum[i-1][j];
        for(int j=L[i];j<=R[i];j++)id[i][j-L[i]+1]=j;
        sort(id[i]+1,id[i]+R[i]-L[i]+1+1,cmp);
        for(int j=1;j<=R[i]-L[i]+1;j++)
            for(int k=1;k<=R[i]-L[i]+1;k++)pnum[i][j][k]=pnum[i][j][k-1]+(a[k+L[i]-1]<=a[j+L[i]-1]);
    }
    while(m--){
        int opt=read();
        if(opt==1){
            int l=read(),r=read();
            if(pos[l]==pos[r]){
                // l,r 在同一个块
                for(int i=l;i<=r;i++)ans[i]+=pnum[pos[l]][i-L[pos[l]]+1][i-L[pos[l]]+1]-pnum[pos[l]][i-L[pos[l]]+1][l-L[pos[l]]];
            }else{
                // 第一部分 左散块对左散块/右散块对右散块
                for(int i=l;i<=R[pos[l]];i++)ans[i]+=pnum[pos[l]][i-L[pos[l]]+1][i-L[pos[l]]+1]-pnum[pos[l]][i-L[pos[l]]+1][l-L[pos[l]]];
                for(int i=L[pos[r]];i<=r;i++)ans[i]+=pnum[pos[r]][i-L[pos[r]]+1][i-L[pos[r]]+1];
                // 第二部分 整块对整块
                for(int i=pos[l]+1;i<pos[r];i++)times[pos[l]+1][i]++;
                // 第三部分 整块对右散块
                for(int i=L[pos[r]];i<=r;i++)ans[i]+=prenum[pos[r]-1][a[i]]-prenum[pos[l]][a[i]];
                // 第四部分 左散块对右散块
                for(int i=1,j=0,cnt=0;i<=R[pos[r]]-L[pos[r]]+1;i++){
                    while(i<=R[pos[r]]-L[pos[r]]+1&&id[pos[r]][i]>r)i++;
                    if(i>R[pos[r]]-L[pos[r]]+1)continue;
                    while(j<R[pos[l]]-L[pos[l]]+1&&a[id[pos[l]][j+1]]<=a[id[pos[r]][i]]){
                        j++;
                        if(id[pos[l]][j]>=l)cnt++;
                    }
                    ans[id[pos[r]][i]]+=cnt;
                }
                // 第五部分 左散块对整块
                int x=pos[l]+1;
                // y 整块的部分，差分->暴力修改->前缀和
                for(int i=pos[n];i>=1;i--)xbyb[poss[x]][i]-=xbyb[poss[x]][i-1],xpyb[x][i]-=xpyb[x][i-1];
                for(int i=l;i<=R[pos[l]];i++)xbyb[poss[x]][pos[a[i]]]++,xpyb[x][pos[a[i]]]++;
                for(int i=1;i<=pos[n];i++)xbyb[poss[x]][i]+=xbyb[poss[x]][i-1],xpyb[x][i]+=xpyb[x][i-1];
                // y 散块的部分，块内再分块
                for(int i=l;i<=R[pos[l]];i++){
                    int y=a[i];
                    // x 整块
                    xbypyb[poss[x]][pos[y]][poss[y-L[pos[y]]+1]]++,xbypyp[poss[x]][pos[y]][y-L[pos[y]]+1]++;
                    // x 散块
                    xpypyb[x][pos[y]][poss[y-L[pos[y]]+1]]++,xpypyp[x][pos[y]][y-L[pos[y]]+1]++;
                }
                // 和上面一样
                x=pos[r];
                for(int i=pos[n];i>=1;i--)xbyb[poss[x]][i]-=xbyb[poss[x]][i-1],xpyb[x][i]-=xpyb[x][i-1];
                for(int i=l;i<=R[pos[l]];i++)xbyb[poss[x]][pos[a[i]]]--,xpyb[x][pos[a[i]]]--;
                for(int i=1;i<=pos[n];i++)xbyb[poss[x]][i]+=xbyb[poss[x]][i-1],xpyb[x][i]+=xpyb[x][i-1];
                for(int i=l;i<=R[pos[l]];i++){
                    int y=a[i];
                    xbypyb[poss[x]][pos[y]][poss[y-L[pos[y]]+1]]--,xbypyp[poss[x]][pos[y]][y-L[pos[y]]+1]--;
                    xpypyb[x][pos[y]][poss[y-L[pos[y]]+1]]--,xpypyp[x][pos[y]][y-L[pos[y]]+1]--;
                }
            }
        }else{
            int x=read(),y=a[x];
            ll res=ans[x];// 第一、三、四部分 暴力记录答案
            // 第二部分 整块对整块
            for(int i=1,s=0;i<=pos[x];i++){
                s+=times[i][pos[x]];
                if(i<pos[x])res+=1ll*s*num[i][a[x]];
                else for(int j=L[i];j<=x;j++)if(a[j]<=a[x])res+=s;
            }
            // 第五部分 左散块对整块
            // x 整块
            for(int i=1;i<poss[pos[x]];i++){
                // y 整块
                res+=xbyb[i][pos[y]-1];
                // y 散块内整块
                for(int j=1;j<poss[y-L[pos[y]]+1];j++)res+=xbypyb[i][pos[y]][j];
                // y 散块内单点
                for(int j=L1[poss[y-L[pos[y]]+1]];j<=y-L[pos[y]]+1;j++)res+=xbypyp[i][pos[y]][j];
            }
            // x 散块（和上面一样）
            for(int i=L1[poss[pos[x]]];i<=pos[x];i++){
                res+=xpyb[i][pos[y]-1];
                for(int j=1;j<poss[y-L[pos[y]]+1];j++)res+=xpypyb[i][pos[y]][j];
                for(int j=L1[poss[y-L[pos[y]]+1]];j<=y-L[pos[y]]+1;j++)res+=xpypyp[i][pos[y]][j];
			}
            printf("%lld\n",res);
        }
    }
    return 0;
}