P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I解题报告

解题报告

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I解题报告：

更好的阅读体验

我们已经有了低于$n^{1.5}$的在线算法。——nzhtl1477

题意

题意：给定一个长度为$n$的排列，$q$次询问，每次询问区间的逆序对数，强制在线。（$1\leqslant n,m\leqslant 10^5$）

分析

BF口中序列分块基础题，我并不会/fad。

首先对原序列进行分块（大小为$S$），第$k$个块的位置为$[l_k,r_k]$，然后进行下列预处理：

对于第$k$个块，我们将它进行排序（并且将每个块排序后的数组保存到$b$数组里），然后可以把原序列与这个块归并一下（因为原序列是排列，因此我们记$pos_i$为$i$的位置），计算出对于位置$i$，第$k$个块内有多少个数小于它，我们记为$atb'_{k,i}$（$\text{all to block}$）。

然后设$ib_i$表示$i$在当前块中单独贡献的逆序对数量，$ibpre_i$与$ibsuf_i$分别表示当前块内$i$表示的前缀/后缀贡献的逆序对数量，很容易预处理出来。

设$ibsum_{i,j}$表示$i$这个位置往后一直到块内第$j$个位置这个区间$i$贡献的的逆序对数量，我们不难发现可以差分一下，它就等于$ib_i$减去$j+1$到块末比$a_i$小的值数量。

最后，我们还预处理两个前缀和：$atb_{k,i}$表示前$k$个块，有多少个数小于$a_i$（也就是对上面的$atb'$求一个前缀和），$btb_{k,i}$表示前$k$个块有多少个数大于第$i$个块内所有的数（$\text{block to block}$），不难发现

不难发现上述预处理的时间复杂度是$O(n+B^2)$。

void build(int k){
    int tmps=0;
    for(int i=l[k];i<=r[k];i++)
        tmp[++tmps]=a[i];
    sort(tmp+1,tmp+1+tmps);
    for(int i=l[k];i<=r[k];i++)
        b[i]=tmp[i-l[k]+1];
    for(int i=1,j=0;i<=n;i++){
        for(;j<tmps&&tmp[j+1]<i;j++);
        atb[k][pos[i]]=j;
    }
    for(int i=r[k];i>=l[k];i--){
        ib[i]=qry(a[i]);
        ibsuf[i]=(i==r[k]? 0:ibsuf[i+1])+ib[i];
        upd(a[i],1);
    }
    for(int i=r[k];i>=l[k];i--)
        upd(a[i],-1);
    for(int i=l[k];i<=r[k];i++){
        ibpre[i]=(i==l[k]? 0:ibpre[i-1])+((i-l[k])-qry(a[i]));
        upd(a[i],1);
    }
    for(int i=l[k];i<=r[k];i++)
        upd(a[i],-1);
    for(int i=r[k];i>=l[k];i--){
        for(int j=l[k];j<=i;j++)
            ibsum[j][i-l[k]+1]=ib[j]-qry(a[j]);
        upd(a[i],1);
    }
    for(int i=r[k];i>=l[k];i--)
        upd(a[i],-1);
    for(int i=1;i<=n;i++)
        atb[k][i]+=atb[k-1][i],btb[k][bel[i]]+=atb[k][i];
}

然后，我们考虑查询$[x,y]$，我们设$x$在块$p$中，$y$在块$q$中。

如果$p=q$，我们可以想到之前预处理的$ibsum_{i,j}$（表示$i$这个位置往后一直到块内第$j$个位置这个区间$i$贡献的的逆序对数量，不难发现我们对于$i=[x,y]$的$ibsum_{i,y-l_p+1}$求和就好了），复杂度是$O(\sqrt n)$。

如果$p\ne q$，那么一个个部分分析：

• 散对散：两端的散块之间的贡献可以通过这两个散块的归并实现（还记得排完序的数组保存在$b$吗），复杂度$O(B)$。
• 整对散：考虑前面预处理的$atb_{i,j}$（表示前$i$个块，有多少个数小于$a_j$），我们枚举散块中每一个数加上就好了，复杂度$O(B)$。
• 散块内部：考虑前面预处理的$ibpre_i$和$ibsuf_i$（当前块内$i$表示的前缀/后缀贡献的逆序对数量），然后直接加上就好了，复杂度$O(1)$。
• 整块内部：考虑前面预处理的$btb_{i,j}$（表示前$i$个块有多少个数大于第$j$个块内所有的数），然后枚举每一个整块，加上就好了（记得减去自己），复杂度$O(\frac{n}{B})$。

因此，一次查询的时间复杂度为$O(B+\frac{n}{B})$。

long long query(int x,int y){
    if(x<1||y<1||x>n||y>n||x>y)//貌似不判也行
        return 0;
    int p=bel[x],q=bel[y];
    long long res=0;
    if(p==q){
        for(int i=x;i<=y;i++)
            res+=ibsum[i][y-l[p]+1];
        return res;
    }
    int tmps=0,pmts=0;
    for(int i=l[p];i<=r[p];i++)
        if(pos[b[i]]>=x)
            tmp[++tmps]=b[i];
    for(int i=l[q];i<=r[q];i++)
        if(pos[b[i]]<=y)
            pmt[++pmts]=b[i];
    for(int i=1,j=0;i<=tmps;i++){
        for(;j<pmts&&pmt[j+1]<tmp[i];j++);
        res+=j;
    }
    for(int i=x;i<=r[p];i++)
        res+=atb[q-1][i]-atb[p][i];
    for(int i=p+1;i<=q-1;i++)
        res+=btb[q-1][i]-btb[i][i]+ibpre[r[i]];
    for(int i=l[q];i<=y;i++)
        res+=(l[q]-r[p]-1)-(atb[q-1][i]-atb[p][i]);
    return ibsuf[x]+res+ibpre[y];
}

时间复杂度：$O(\frac{n}{B}(n+B^2)+m(B+\frac{n}{B}))$，因为$n,m$同阶，因此设$B=\sqrt n$，总时间复杂度为$O(n\sqrt n)$。

多开了一个数组，结果卡了半天常数。。。

实际上如果实现精细一点，甚至不需要卡什么常（加一个快读就够了，连块长都不需要调）

代码

记得开$\text{long long}$。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=100005,maxt=345;
int n,m,t,S;
int a[maxn],b[maxn],l[maxn],r[maxn],bel[maxn],Asum[maxt],Bsum[maxn],pos[maxn],tmp[maxn],pmt[maxn];//b[l,r]=sort(a[l],a[r])
int ib[maxn]/*in block*/,atb[maxt][maxn]/*all to block*/,ibsum[maxn][maxt],ibpre[maxn],ibsuf[maxn];
long long lastans;
long long btb[maxt][maxt]/*block to block*/;
void upd(int x,int v){
    for(int i=bel[x]+1;i<=t;i++)
        Asum[i]+=v;
    for(int i=x;i<=r[bel[x]];i++)
        Bsum[i]+=v;
}
int qry(int x){
    return Asum[bel[x]]+Bsum[x];
}
void build(int k){
    int tmps=0;
    for(int i=l[k];i<=r[k];i++)
        tmp[++tmps]=a[i];
    sort(tmp+1,tmp+1+tmps);
    for(int i=l[k];i<=r[k];i++)
        b[i]=tmp[i-l[k]+1];
    for(int i=1,j=0;i<=n;i++){
        for(;j<tmps&&tmp[j+1]<i;j++);
        atb[k][pos[i]]=j;
    }
    for(int i=l[k];i<=r[k];i++){
        ibpre[i]=(i==l[k]? 0:ibpre[i-1])+((i-l[k])-qry(a[i]));
        upd(a[i],1);
    }
    for(int i=l[k];i<=r[k];i++)
        upd(a[i],-1);
    for(int i=r[k];i>=l[k];i--){
        ib[i]=qry(a[i]);
        ibsuf[i]=(i==r[k]? 0:ibsuf[i+1])+ib[i];
        upd(a[i],1);
    }
    for(int i=r[k];i>=l[k];i--)
        upd(a[i],-1);
    for(int i=r[k];i>=l[k];i--){
        for(int j=l[k];j<=i;j++)
            ibsum[j][i-l[k]+1]=ib[j]-qry(a[j]);
        upd(a[i],1);
    }
    for(int i=r[k];i>=l[k];i--)
        upd(a[i],-1);
    for(int i=1;i<=n;i++)
        atb[k][i]+=atb[k-1][i],btb[k][bel[i]]+=atb[k][i];
}
void init(){
    S=sqrt(n),t=n/S;
    for(int i=1;i<=t;i++)
        l[i]=r[i-1]+1,r[i]=i*S;
    if(r[t]<n)
        t++,l[t]=r[t-1]+1,r[t]=n;
    for(int i=1;i<=t;i++)
        for(int j=l[i];j<=r[i];j++)
            bel[j]=i;
    for(int i=1;i<=t;i++)
        build(i);
}
long long query(int x,int y){
    if(x<1||y<1||x>n||y>n||x>y)
        return 0;
    int p=bel[x],q=bel[y];
    long long res=0;
    if(p==q){
        for(int i=x;i<=y;i++)
            res+=ibsum[i][y-l[p]+1];
        return res;
    }
    int tmps=0,pmts=0;
    for(int i=l[p];i<=r[p];i++)
        if(pos[b[i]]>=x)
            tmp[++tmps]=b[i];
    for(int i=l[q];i<=r[q];i++)
        if(pos[b[i]]<=y)
            pmt[++pmts]=b[i];
    for(int i=1,j=0;i<=tmps;i++){
        for(;j<pmts&&pmt[j+1]<tmp[i];j++);
        res+=j;
    }
    for(int i=x;i<=r[p];i++)
        res+=atb[q-1][i]-atb[p][i];
    for(int i=p+1;i<=q-1;i++)
        res+=btb[q-1][i]-btb[i][i]+ibpre[r[i]];
    for(int i=l[q];i<=y;i++)
        res+=(l[q]-r[p]-1)-(atb[q-1][i]-atb[p][i]);
    return ibsuf[x]+res+ibpre[y];
}
inline void read(int &x){
    char c=getchar();
    x=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-48;
}
int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++)
        read(a[i]),pos[a[i]]=i;
    init();
    for(int i=1;i<=m;i++){
        long long x,y;
        int l,r;
        read(l),read(r);
        x=l,y=r;
        x^=lastans,y^=lastans;
        printf("%lld\n",lastans=query((int)x,(int)y));
    }
    return 0;
}