题解 P5046 【[Ynoi2019 模拟赛] Yuno loves sqrt technology I】

whiteqwq · 2021-02-18 16:17:31 · 题解

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;
}