题解：P8530 [Ynoi2003] 博丽灵梦

dyc2022 · 2026-04-15 20:39:34 · 题解

更好的阅读体验

卡了 117 发卡过的，必须纪念一下。

我们先来研发一个数据结构，需要支持在一个 n \times 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} 的小块。注意需要保证每个大块必须由若干个完整的中块拼成，每个中块必须由若干个完整的小块拼成。

不难发现大块共有 O(n^{1/2}) 个，中块有 O(n^{3/4}) 个，小块有 O(n) 个。我们对每种块分别维护块内所有点的和。

对于修改，假设插入点 (x, y)，我们可以直接找到 (x, y) 所属的大块、两种中块、小块分别是哪一个，分别修改这些块的和，显然可以做到 O(1)。

对于删除，同样找到要删除的点所属的块，然后减去删除的点的点权即可，显然也可以做到 O(1)。

对于查询，我们稍微差分一下，变成询问一个左下角矩形内部的点权之和。

容易发现，一个左下角矩形应该包含

• 红色的整块（大块）：总共 O(\sqrt n) 个。
• 蓝色的整块（中块）：总共 O(n^{1/4} \cdot n^{1/4}) = O(\sqrt n) 个。
• 黄色的整块（中块）：同上，总共 O(\sqrt n) 个。
• 绿色的整块（小块）：总共 O(n^{1/4} \cdot n^{1/4}) = O(\sqrt n) 个。
• 灰色的散块。

对于前四个部分，可以直接枚举这些块并求和。然而对于散块，我们只能枚举散块内部的单点。

但是注意到由于所有点的 x 坐标和 y 坐标都互不相同，又因为灰色区域的宽度不会超过 O(n^{1/2})，因此这一部分的点数只有 O(n^{1/2}) 个。我们考虑存下每个 x 对应的 y，还有每个 y 对应的 x。然后我们枚举 x/y 坐标，看看当前 x/y 坐标对应的点是否在灰色部分，如果在就将这个点的点权加入答案。

这样，查询就做到了 O(\sqrt n)。

接下来看这个题：矩形带权数颜色。

我们考虑一维的数颜色怎么做。我们选取每个颜色第一次出现的位置为代表元进行统计。具体地，我们对每个位置 i 维护前驱（即前一个和 i 颜色相同的位置，不存在即为 0）pre_i，一个位置 i 是它的颜色在区间 [l, r] 第一次出现的颜色当且仅当它上一次出现的位置不在区间内，即 pre_i < l。那么我们把 (i, pre_i) 看作是平面上的点，那么询问 [l, r] 时对答案有贡献的点就是 i \isin [l, r] 且 pre_i \isin [0, l) 的点，可以看作是一次矩形查询。

那么对于二维的情形，我们对 i 这一维做莫队，维护出询问区间内所有 p 构成的集合，这个时候可以看作是一维的情况。

我们且称 p_i 的一维为纵轴，那么我们就在纵轴上维护每个数字 x 的前驱 pre_x，并同样可以看作是二维数点，也就是将 (p_i, pre_{p_i}) 看作是平面上的点，点权为 b_{a_i} 表示这个点颜色的权值。而对于一次查询 (l_1, r_1, l_2, r_2)，由于 i 一维要在 [l_1, r_1] 内这个限制我们已经用莫队处理掉了，因此我们只需要考虑 [l_2, r_2] 的限制，这部分和一维的情况是一模一样的，只需要在我们新生成的这个平面上查询 x \isin [l_2, r_2], y \isin [0, l_2) 这个矩形内部的权值之和即可。

现在问题就是如何支持加点，删点，动态维护 pre。

我们考虑对纵轴维护一个双向链表，也就是我们多维护一个 nxt 表示当前点的颜色下一次出现的位置（如果不存在则为 0）。容易发现在链表上删除一个点是简单的，然而插入一个点是困难的，因为无法快速找到插入的位置，而撤销一次删除操作也是简单的，只需要用一个栈维护上一次的修改。所以我们使用回滚莫队（无增莫队），这样只需要支持删除和撤销操作，非常优秀。

每一次莫队的删除或撤销都对应着 O(1) 次加点和删点操作。接下来我们只需要解决这个问题：我们要支持 O(n \sqrt n) 次加/删点，O(n) 次矩形查询。我们知道，如果一个点存在前驱，那它的前驱对应唯一的后继。所以我们每次加入的点 (x, y) 如果 y \not = 0，那么 x 互不相同，y 互不相同。这个和我们上面说的二维分块可以解决的形式很像了。

所以我们对于所有 y \not = 0 的点，我们扔进一个上述的 O(1) - O(\sqrt n) 二维分块中；对于 y = 0 的点，就退化成一维情况，用一个 O(1) - O(\sqrt n) 的一维分块维护它们就可以了。

那么这道题就做完了，复杂度 O(n \sqrt m + m \sqrt n)。卡常小技巧。

代码删除了快速读入的部分。

#include<bits/stdc++.h>
// #pragma GCC target("avx")
#define endl '\n'
#define N 100006
#define M 1000006
#define cl(t) memset((t),0,sizeof(t))
using namespace std;
struct IO {} io;
using u32=unsigned;
int n,q,tp,B,bel[N],p[N],a[N],nxt[N],pre[N],tmp[N],buc[N];
u32 b[N],ans[M];
struct Ask {
    int l,r,L,R,id;
} ask[M];
struct Stack_Node {
    int x,pre,nxt,col;
} stk[M];
namespace ds1 {
    constexpr int all=100489,B=317;
    u32 s1[all+10],s2[B+10];
    void clear() {cl(s1),cl(s2);}
    void del(int k) {s2[(k-1)/B+1]-=s1[k],s1[k]=0;}
    void add(int k,u32 val) {s1[k]+=val,s2[(k-1)/B+1]+=val;}
    u32 query(int k)
    {
        u32 ret=0; int bel=(k-1)/B+1;
        for(int i=1;i<bel;i++)ret+=s2[i];
        for(int i=(bel-1)*B+1;i<=k;i++)ret+=s1[i];
        return ret;
    }
}
namespace ds2 {
    constexpr int all=1e5,Big=7000,Small=350,Div=20;
    u32 s1[all/Big+5][all/Big+5]; //xbig * ybig
    u32 s2[all/Big+5][all/Small+5]; //xbig * ysmall
    u32 s3[all/Small+5][all/Big+5]; //xsmall * ybig
    u32 s4[all/Small+5][all/Small+5]; //xsmall * ysmall
    u32 sx[N],sy[N];
    int ix[N],iy[N];
    inline 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+10;i++)
            sx[i]=sy[i]=ix[i]=iy[i]=0;
    }
    inline void Del(int x,int y)
    {
        if(!ix[x])return;
        u32 val=sx[x];
        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;
        s1[x_b][y_b]-=val;
        s2[x_b][y_s]-=val;
        s3[x_s][y_b]-=val;
        s4[x_s][y_s]-=val;
        sx[x]=sy[y]=ix[x]=iy[y]=0;
    }
    inline void add(int x,int y,u32 val)
    {
        sx[x]=val,sy[y]=val,ix[x]=y,iy[y]=x;
        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;
        s1[x_b][y_b]+=val;
        s2[x_b][y_s]+=val;
        s3[x_s][y_b]+=val;
        s4[x_s][y_s]+=val;
    }
    inline u32 query(int x,int y)
    {
        u32 ret=0;
        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;
        int x_lb=(x_b-1)*Div+1,y_lb=(y_b-1)*Div+1;
        int x_ls=(x_s-1)*Small+1,y_ls=(y_s-1)*Small+1;
        for(int i=1;i<x_b;i++)
            for(int j=1;j<y_b;j++)ret+=s1[i][j];
        for(int i=1;i<x_b;i++)
            for(int j=y_lb;j<y_s;j++)ret+=s2[i][j];
        for(int i=x_lb;i<x_s;i++)
            for(int j=1;j<y_b;j++)ret+=s3[i][j];
        for(int i=x_lb;i<x_s;i++)
            for(int j=y_lb;j<y_s;j++)ret+=s4[i][j];
        for(int i=x;i>=x_ls;i--)if(ix[i]<=y)ret+=sx[i];
        for(int i=y;i>=y_ls;i--)if(iy[i]<x_ls)ret+=sy[i];
        return ret;
    }
}
namespace ds {
    inline void clear() {ds1::clear(),ds2::clear();}
    inline void del(int x,int y) {if(!y)ds1::del(x); else ds2::Del(x,y);}
    inline void add(int x,int y,u32 val) {if(!y)ds1::add(x,val); else ds2::add(x,y,val);}
    inline u32 query(int x,int y) {return ds1::query(x)+ds2::query(x,y);}
}
inline void del(int k)
{
    int x=p[k],col=a[k];
    ds::del(x,pre[x]),stk[++tp]={x,pre[x],nxt[x],col};
    if(nxt[x])ds::del(nxt[x],pre[nxt[x]]),pre[nxt[x]]=pre[x],ds::add(nxt[x],pre[nxt[x]],b[col]);
    if(pre[x])nxt[pre[x]]=nxt[x];
    pre[x]=nxt[x]=0;
}
inline void undo()
{
    int x=stk[tp].x;
    int pr=stk[tp].pre,nx=stk[tp].nxt,col=stk[tp].col; tp--;
    if(nx)ds::del(nx,pre[nx]),pre[nx]=x,ds::add(nx,pre[nx],b[col]);
    if(pr)nxt[pr]=x;
    pre[x]=pr,ds::add(x,pre[x],b[col]),nxt[x]=nx;
}
main()
{
    n=io.read();
    for(int i=1;i<=n;i++)p[i]=io.read();
    for(int i=1;i<=n;i++)a[i]=io.read();
    for(int i=1;i<=n;i++)b[i]=io.read<u32>();
    q=io.read(),B=n/pow(q,0.5);
    for(int i=1,l,r,x,y;i<=q;i++)
        l=io.read(),r=io.read(),x=io.read(),y=io.read(),ask[i]={l,r,x,y,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 bel[x.l]<bel[y.l];
        return x.r>y.r;
    });
    int l,r,now_l;
    for(int i=1;i<=q;i++)
    {
        if(bel[ask[i].l]!=bel[ask[i-1].l])
        {
            now_l=l=(bel[ask[i].l]-1)*B+1,r=n,tp=0;
            ds::clear(),cl(tmp),cl(pre),cl(nxt),cl(buc);
            for(int i=l;i<=r;i++)tmp[p[i]]=a[i];
            for(int i=1;i<=n;i++)
                if(tmp[i])pre[i]=buc[tmp[i]],buc[tmp[i]]=i,ds::add(i,pre[i],b[tmp[i]]);
            for(int i=1;i<=n;i++)if(pre[i])nxt[pre[i]]=i;
        }
        for(;r>ask[i].r;del(r--));
        for(;l<ask[i].l;del(l++));
        ans[ask[i].id]=ds::query(ask[i].R,ask[i].L-1)-
                       ds::query(ask[i].L-1,ask[i].L-1);
        for(;l>now_l;undo(),l--);
    }
    for(int i=1;i<=q;i++)io.writeln<u32>(ans[i]);
    return 0;
}