题解:P7448 [Ynoi2007] rdiq

· · 题解

更好的阅读体验

\text {rdiq = range different invertion queries}

十分具有技巧性,个人认为最终的做法还是非常令人惊叹的。书接上回。

我们先来研发一个数据结构,需要支持在一个 n \times n 的二维平面上,

保证插入的点 x, y 坐标分别互不相同。

只能做到半在线,即所有询问涉及的矩形,会在所有加/删点操作之前给出。本质不同的询问矩形只有 \boldsymbol {O(n)} 种。

为了解决这个问题,我们考虑将这个 n \times n 的平面分块。我们分成四种块:n^{3/4} \times n^{3/4} 的大块,n^{3/4} \times n^{1/2} 的中块,n^{1/2} \times n^{3/4} 的中块,n^{1/2} \times n^{1/2} 的小块。注意需要保证每个大块必须由若干个完整的中块拼成,每个中块必须由若干个完整的小块拼成。

我们同样需要将答案拆成若干个左下角矩形求和。

那么我们对于所有红块维护二维前缀和;对于每个 n \times n^{0.75} 的矩形内部,我们对蓝块维护二维前缀和;对于每个 n^{0.75} \times n 的矩形内部,我们对黄块维护二维前缀和;对于每个 n^{0.75} \times n^{0.75} 的矩形内部,我们对绿块维护二维前缀和。

容易发现,当加入一个点时,

因此一次修改操作可以在 O(\sqrt n) 的时间内实现。

维护出二维前缀和后,对于一个询问(如上图中五角星所表示的),我们可以在 O(1) 的时间内得到上图中红、蓝、黄、绿的部分的点权之和了。

然而灰色的散块部分的点权和不好求。在博丽灵梦使用的二维分块中,我们通过枚举散块内部的点来使复杂度正确,然而在这个数据结构中不行。

考虑到允许半在线,我们可以在加入一个点的时候更新所有满足,这个点在该矩形的散块内部,的矩形的答案。

具体怎么更新呢?我们可以先用 vector 之类的东西把每个询问矩形挂到 x/y 轴上;加入一个点的时候,直接枚举这些矩形,暴力修改即可。

这个为什么是对的?注意到由于插入的点 x, y 坐标互不相同,因此我们所有矩形散块中的点数之和是 O(n \sqrt n)。而考虑把贡献算在点身上,那就是对于所有点,满足这个点在该矩形的散块内部,的矩形的数量之和,是 O(n \sqrt n)。

至此,查询可以在 O(1) 的时间内解决;修改的复杂度不变。

接下来看这个题:区间本质不同逆序对计数。由于不弱于区间逆序对,且分块维护“本质不同”的限制较为困难,因此考虑莫队。

莫队的指针移动有四种情况,接下来我们讨论其中的两种。

第一种:\boldsymbol {[l, r-1] \to [l, r]}。

这是右端点扩展的情况;右端点收缩的情况与之是相对称的。则 [l, r-1] \to [l, r] 所增加答案数量,就是 r 和 [l, r) 中,与之前有过的逆序对都不同的,逆序对的数量。

那么如何处理逆序对和先前都不同这个条件呢?我们假设 r' 是 a_r 的前驱,即在 r 前面的最后一个 x 使得 a_x = a_r。我们假定这个 r' 存在。

那么假设我们现在有一个有序二元组 (i, r),我们应该如何判断它是否符合条件呢?

为了方便处理,我们将条件 1 的左端点的等号取上,并将条件 2 的右端点的等号取上。最后只需要特判 (r, a_r) 这个点是否在平面上,如果在平面上就把这个点带来的贡献扣掉即可。

我们考虑以 i 为横坐标,a_i 为纵坐标,维护平面上的一些点。一个点 (i, a_i) 出现在平面上,当且仅当它的前驱不在平面上,这样就满足了上述第三个条件。那么我们要对满足 1,2 条件的点计数。容易发现满足条件的点位于横坐标区间是 [r'+1, r],纵坐标区间是 [a_r, n],也就是左下角和右上角分别是 (r'+1, a_r), (r, n) 的一个矩形里。因此一次扩展就是一次加点,一次矩形数点。

由于莫队的端点会扩展 O(n \sqrt n) 次,而加点次数和查询次数同阶,所以需要二次离线。但是由于这道题目矩形查询比较特殊,无法拆开贡献;而注意到虽然询问矩形的左下角和右上角的坐标中均同时包含 r, r',但是左上角和右下角的坐标中分别只含有 r, r'。因此我们考虑一个手法:翻转坐标轴。

具体地,我们将每个点的 y 坐标反转,即 (i, a_i) \to (i, n-a_i + 1)。那么新平面上的左下角和右上角就变成了原平面上的左上角和右下角。

因此变成了左下角 (r'+1, 1),右上角 (r, a_r) 的矩形查询。由于 a_{r'} = a_r,因此可以拆成 (r, n-a_r + 1) 的左下角矩形,减去 (r', n-a_{r'} + 1) 的左下角矩形的点数。而由于进行了二次离线,只有 n 次加点;而由于每个询问矩形仅和 r 有关,因此询问矩形只有 O(n) 中,O(n \sqrt n) 次。使用上述 O(\sqrt n) - O(1) 二维分块可以解决这一部分。

第二种:\boldsymbol{[l+1, r] \to [l, r]}。

假设 l 的后继是 l'。同理,我们考虑一个有序二元组 (l, i) 什么时候可以计入答案。

同样的,我们把条件 1,2 的开区间都取闭,最后再特判即可。我们照样对区间中所有是当前颜色出现最后一次的 i,维护平面上的点 (i, a_i)。那么可以看作是一个左下角坐标是 (l, 1),右上角坐标是 (l', a_l) 的矩形查询。

发现左下角和右上角的坐标中同时包含 l, l',这不好。但是左上角和右下角中只包含 l, l' 中的一个。这里我们考虑翻转 x 轴,如图。

新矩形已在图中标出,这里不在赘述。这个矩形内部的点数可以差分成 (n-l+1, a_l) 的左下角矩形,减去 (n - l' +1, a_{l'}) 的左下角矩形,这样子保证了本质不同的矩形只有 O(n) 个。同样进行莫队二次离线,这样只有 O(n) 次加点,O(n \sqrt n) 次矩形查询,同样可以使用上述的二维分块做到总体 O(n \sqrt n) 的复杂度。

假设 n, q 同阶,那么问题在 O(n \sqrt n) 的时间内得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 100006
#define M 500006
using namespace std;
using i64=long long;
int n,q,B,a[N],bel[N],cnt[N],pre[N],nxt[N],buc[N];
i64 ans[M],o[M];
struct Ask {int l,r,id;} ask[M];
struct Node {int l,r,v,id;};
vector<Node> vl[N],vr[N];
namespace ds {
    constexpr int all=104976,Big=5832,Small=324,Div=18;
    i64 s1[all/Big+5][all/Big+5];
    i64 s2[all/Big+5][all/Small+5];
    i64 s3[all/Small+5][all/Big+5];
    i64 s4[all/Small+5][all/Small+5];
    i64 s[all+5]; int tot,rx[all+5],ry[all+5],ix[all+5],iy[all+5];
    void clear()
    {
        for(int i=0;i<all/Big+5;i++)
            for(int j=0;j<all/Big+5;j++)s1[i][j]=0;
        for(int i=0;i<all/Big+5;i++)
            for(int j=0;j<all/Small+5;j++)s2[i][j]=0;
        for(int i=0;i<all/Small+5;i++)
            for(int j=0;j<all/Big+5;j++)s3[i][j]=0;
        for(int i=0;i<all/Small+5;i++)
            for(int j=0;j<all/Small+5;j++)s4[i][j]=0;
        for(int i=0;i<all+5;i++)
            s[i]=rx[i]=ry[i]=ix[i]=iy[i]=0;
        tot=0;
    }
    void add_rec(int x,int y) {ix[x]=iy[y]=++tot,rx[tot]=x,ry[tot]=y;}
    void insert(int x,int y,i64 val)
    {
        int x_b=(x-1)/Big+1,y_b=(y-1)/Big+1;
        int x_s=(x-1)/Small+1,y_s=(y-1)/Small+1;
        for(int i=x_b;i<=all/Big;i++)
            for(int j=y_b;j<=all/Big;j++)s1[i][j]+=val;
        for(int i=x_b;i<=all/Big;i++)
            for(int j=y_s;j<=y_b*Div;j++)s2[i][j]+=val;
        for(int i=x_s;i<=x_b*Div;i++)
            for(int j=y_b;j<=all/Big;j++)s3[i][j]+=val;
        for(int i=x_s;i<=x_b*Div;i++)
            for(int j=y_s;j<=y_b*Div;j++)s4[i][j]+=val;
        for(int i=x;i<=x_s*Small;i++)
            if(ix[i]&&ry[ix[i]]>=y)s[ix[i]]+=val;
        for(int i=y;i<=y_s*Small;i++)
            if(iy[i]&&rx[iy[i]]>x_s*Small)s[iy[i]]+=val;
    }
    i64 query(int id)
    {
        int x=rx[id],y=ry[id];
        int x_b=(x-1)/Big+1,y_b=(y-1)/Big+1;
        int x_s=(x-1)/Small+1,y_s=(y-1)/Small+1;
        i64 ret=s1[x_b-1][y_b-1];
        if((y_s-1)%Div)ret+=s2[x_b-1][y_s-1];
        if((x_s-1)%Div)ret+=s3[x_s-1][y_b-1];
        if(((y_s-1)%Div)&&((x_s-1)%Div))ret+=s4[x_s-1][y_s-1];
        return ret+s[id];
    }
}
inline int rev(int x) {return n-x+1;}
main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)pre[i]=buc[a[i]],buc[a[i]]=i;
    for(int i=1;i<=n;i++)buc[i]=0;
    for(int i=n;i;i--)nxt[i]=buc[a[i]],buc[a[i]]=i;
    scanf("%d",&q),B=max<int>(1,n/pow(q,0.5));
    for(int i=1;i<=q;i++)
        scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].id=i;
    for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1;
    sort(ask+1,ask+1+q,[](Ask x,Ask y) {
        if(bel[x.l]!=bel[y.l])return x.l<y.l;
        return bel[x.l]&1?x.r<y.r:x.r>y.r;
    });
    for(int i=1,l=1,r=0;i<=q;i++)
    {
        if(ask[i].l<l)vl[r].push_back({ask[i].l,l-1,1,i}),l=ask[i].l;
        if(ask[i].r>r)vr[l].push_back({r+1,ask[i].r,1,i}),r=ask[i].r;
        if(ask[i].l>l)vl[r].push_back({l,ask[i].l-1,-1,i}),l=ask[i].l;
        if(ask[i].r<r)vr[l].push_back({ask[i].r+1,r,-1,i}),r=ask[i].r;
    }
    for(int i=1;i<=n;i++)cnt[a[i]]++;
    for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++)a[i]=cnt[a[i]]--;
    for(int i=1;i<=n;i++)ds::add_rec(i,rev(a[i]));
    for(int i=n;i;i--)
    {
        if(nxt[i])ds::insert(nxt[i],rev(a[nxt[i]]),-1);
        ds::insert(i,rev(a[i]),1);
        for(auto j:vr[i])
        {
            int l=j.l,r=j.r,v=j.v,id=j.id; i64 s=0;
            for(int k=r;k>=l;k--)
                s+=ds::query(k)-(pre[k]?ds::query(pre[k]):0ll)-(pre[k]<i);
            ans[id]+=s*v;
        }
    }
    ds::clear();
    for(int i=1;i<=n;i++)ds::add_rec(rev(i),a[i]);
    for(int i=1;i<=n;i++)
    {
        if(pre[i])ds::insert(rev(pre[i]),a[pre[i]],-1);
        ds::insert(rev(i),a[i],1);
        for(auto j:vl[i])
        {
            int l=j.l,r=j.r,v=j.v,id=j.id; i64 s=0;
            for(int k=l;k<=r;k++)
                s+=ds::query(k)-(nxt[k]?ds::query(nxt[k]):0ll)-(nxt[k]>i||!nxt[k]);
            ans[id]+=s*v;
        }
    }
    for(int i=1;i<=q;i++)
        ans[i]+=ans[i-1],o[ask[i].id]=ans[i];
    for(int i=1;i<=q;i++)printf("%lld\n",o[i]);
    return 0;
}