P8530 题解

· · 题解

阻挡我一遍过的竟然是同块的暴力......

6.5 update：经@FutaRimeWoawaSete的提醒修改了“普及”的部分。

2023.1.28 update:修改了代码里的一些瑕疵。

前置知识

分块，区间数颜色的 trick，回滚莫队，如果做过rdiq那你就畅通无阻了。

先普及二维分块（会的跳过）

我们理解一下一维分块，它相当于一个 n^{0.5} 叉树，但是照搬下来在二维的背景下会平方，所以我们牺牲树的高度（常数）来优化，即 n^{0.25} 叉树，第一层是 n^{0.75}\times n^{0.75}（省去了第 -1 层的 n\times n 和第 0 层的 n\times n^{0.75} 和 n^{0.75}\times n），第二层是 n^{0.75}\times n^{0.5} 和 n^{0.5}\times n^{0.75}，然后就是 n^{0.5}\times n^{0.5} 的块，因为这题有个性质：x,y 坐标不重复，所以散块直接枚举横纵坐标就行了。

考虑没有性质的情况：我们在分一个 n^{0.25}\times n^{1/0.75/0.5/0.25} 的块和 1\times n^{1/0.75/0.5/0.25} 的块，剩的暴力即可，只是这样的空间很疯狂......

本题实现思路

这是一个静态区间数颜色的题目（Range Count Numbers），二维版本。

首先这种大规模数颜色肯定要用链表的 trick，最后查询 lst<l_2 的和即可，但是用回滚莫队滚滚掉一维后还有一个 p_i 和 lst_i 两维，所以考虑二维分块，因为 p_i 不重复，lst_i 除了 0 的情况肯定都不重复，而 0 的情况都会计入答案，所以二维分块记录不为 0 的部分，再打一个一维分块记录 0 的部分，都是 O(1)-O(\sqrt n) 的分块。

还有几点值得注意：

  2. 原序列的那一维已经被滚掉了，所以链表是在 p_i 那一维操作的。

Code:

#include <bits/stdc++.h>
#define ll unsigned int
#define wr(x,ch) write(x),putchar(ch)
using namespace std;
namespace IO{
}
using IO::read;
using IO::write;
const ll N=100005,M=1000005,s=107,s1=6405,s2=305;
ll sum1[N/s1+5][N/s1+5],sum2[N/s1+5][N/s2+5],sum3[N/s2+5][N/s1+5],sum4[N/s2+5][N/s2+5],sum5[N],sum6[N],pos[N],a[N],b[N],
P[N],idx[N],L[N],n,m,bls,R[N],vis[N],ans[M],lst[N],nxt[N],Q[N],aa[N],del[N];
ll L1[N],L2[N],R1[N],R2[N],idx1[N],idx2[N],bls1,bls2;
struct node {
    ll l,r,id,s,t;
    bool operator<(const node &p) const {
        return idx[l]==idx[p.l]?r>p.r:l<p.l;
    }
}p[M];
inline void add(ll x,ll y,const ll delta) {
    if(!y) {
        sum5[x]+=delta,sum6[idx[x]]+=delta;
        return ;
    }
    sum1[idx1[x]][idx1[y]]+=delta;
    sum2[idx1[x]][idx2[y]]+=delta;
    sum3[idx2[x]][idx1[y]]+=delta;
    sum4[idx2[x]][idx2[y]]+=delta;
}
ll ask(ll x,ll y) {
    ll tot=0;
    for(ll i=1;i<idx[x];i++) tot+=sum6[i];
    for(ll i=L[idx[x]];i<=x;i++) tot+=sum5[i];
    for(ll i=1;i<idx1[x];i++) 
        for(ll j=1;j<idx1[y];j++) 
            tot+=sum1[i][j];
    for(ll i=1;i<idx1[x];i++) 
        for(ll j=idx2[L1[idx1[y]]],k=idx2[y];j<k;j++) 
            tot+=sum2[i][j];
    for(ll i=idx2[L1[idx1[x]]],j=idx2[x];i<j;i++) 
        for(ll k=1;k<idx1[y];k++) 
            tot+=sum3[i][k];
    for(ll i=idx2[L1[idx1[x]]],j=idx2[x];i<j;i++) 
        for(ll k=idx2[L1[idx1[y]]],l=idx2[y];k<l;k++) 
            tot+=sum4[i][k];
    for(ll i=L2[idx2[x]];i<=x;i++) (!del[i]&&lst[i]&&lst[i]<=y)&&(tot+=b[aa[i]]);
    for(ll i=L2[idx2[y]],cyy=L2[idx2[x]];i<=y;i++) (!del[i]&&nxt[i]&&nxt[i]<cyy)&&(tot+=b[aa[i]]);
    return tot;
}
void init() {
    bls=(n+s-1)/s;
    for(int i=1;i<=bls;i++) {
        L[i]=R[i-1]+1,R[i]=min(n,s*i);
        for(int j=L[i];j<=R[i];j++) idx[j]=i;
    }
    bls1=(n+s1-1)/s1;
    for(int i=1;i<=bls1;i++) {
        L1[i]=R1[i-1]+1,R1[i]=min(n,s1*i);
        for(int j=L1[i];j<=R1[i];j++) idx1[j]=i;
    }
    bls2=(n+s2-1)/s2;
    for(int i=1;i<=bls2;i++) {
        L2[i]=R2[i-1]+1,R2[i]=min(n,s2*i);
        for(int j=L2[i];j<=R2[i];j++) idx2[j]=i;
    }
}
int main() {
    n=read();
    for(ll i=1;i<=n;i++) P[i]=read(),Q[P[i]]=i;
    for(ll i=1;i<=n;i++) a[i]=read(),aa[P[i]]=a[i];
    for(ll i=1;i<=n;i++) b[i]=read();
    m=read();
    init();
    for(ll i=1;i<=m;i++) p[i].l=read(),p[i].r=read(),p[i].s=read(),p[i].t=read(),p[i].id=i;
    sort(p+1,p+m+1);
    for(ll i=1,now=0,tot=0,l,r;i<=m;i++) {
        if(idx[p[i].l]!=now) {
            now=idx[p[i].l],l=L[now],r=n;
            memset(pos,0,sizeof(pos));
            memset(sum1,0,sizeof(sum1));
            memset(sum2,0,sizeof(sum2));
            memset(sum3,0,sizeof(sum3));
            memset(sum4,0,sizeof(sum4));
            memset(sum5,0,sizeof(sum5));
            memset(sum6,0,sizeof(sum6));
            memset(lst,0,sizeof(lst));
            memset(nxt,0,sizeof(nxt));
            memset(del,0,sizeof(del));
            for(ll j=1;j<=n;j++) if(Q[j]>=l) lst[j]=pos[aa[j]],pos[aa[j]]=j,add(j,lst[j],b[aa[j]]);
            memset(pos,0,sizeof(pos));
            for(ll j=n;j>=1;j--) if(Q[j]>=l) nxt[j]=pos[aa[j]],pos[aa[j]]=j;
        }
        while(r>p[i].r) {
            add(P[r],lst[P[r]],-b[a[r]]),del[P[r]]=1;
            if(nxt[P[r]]) add(nxt[P[r]],P[r],-b[a[r]]),lst[nxt[P[r]]]=lst[P[r]],add(nxt[P[r]],lst[nxt[P[r]]],b[a[r]]);
            if(lst[P[r]]) nxt[lst[P[r]]]=nxt[P[r]];
            r--;
        }
        while(l<p[i].l) {
            add(P[l],lst[P[l]],-b[a[l]]),del[P[l]]=1;
            if(nxt[P[l]]) add(nxt[P[l]],P[l],-b[a[l]]),lst[nxt[P[l]]]=lst[P[l]],add(nxt[P[l]],lst[nxt[P[l]]],b[a[l]]);
            if(lst[P[l]]) nxt[lst[P[l]]]=nxt[P[l]];
            l++;
        }
        ans[p[i].id]=ask(p[i].t,p[i].s-1)-ask(p[i].s-1,p[i].s-1);
        while(l>L[now]) {
            l--,del[P[l]]=0;
            if(nxt[P[l]]) add(nxt[P[l]],lst[nxt[P[l]]],-b[a[l]]),lst[nxt[P[l]]]=P[l],add(nxt[P[l]],P[l],b[a[l]]);
            if(lst[P[l]]) nxt[lst[P[l]]]=P[l];add(P[l],lst[P[l]],b[a[l]]);
        }
    }
    for(ll i=1;i<=m;i++) wr(ans[i],'\n');
    return 0;
}