题解 P7721【[Ynoi2007] rcn】

· · 题解

#Ynoi开始普及二维分块#

我们考虑一个广为人知的一维区间数颜色 trick：记录每个位置之前和它颜色相同的最后一个位置，查询 [l,r] 就相当于是查询 [l,r] 中前驱在 [0,l-1] 的位置个数，这是一个二维数点问题，容易解决。

然而这个做法难以直接推广到二维，因为你找不到到一个合适的序。。。因此考虑降维，在横坐标上莫队，同时维护纵坐标上的前驱。先假装我们已经有了快速找到前驱后继的方法，那么我们加入/删除一个点时只会影响到 O(1) 个位置的前驱值，于是这就是一个 O(n\sqrt m) 次单点修改，O(m) 次二维数点的问题。众所周知这是一个二维分块，具体可以看 P7448。

关于快速找前驱后继，实际上只需要用无增回滚就可以了。上一次被无增回滚杀还是在上一次。

于是复杂度就是 O(n\sqrt m+m\sqrt n) 的了。

头文件已删。

int n,m,B,b[N],rb[N],pos[N],p[N],a[N],L1,L2,C,D,bv2[N],bv[L],rbv2[L],rbv[25],pre[N],nxt[N],lst[N];
ui val[N],s1[25][25],s2[25][L],s3[L][25],s4[L][L],sb[L],sv[N],ans[N*10];bool vst[N],del[N];
struct qry{int l,r,d,u,id;};vector<qry> vq[N];
bool cmp(qry u,qry v){return u.r>v.r;}
void init(){
    for(int i=1;i<=D;i++)fill(s1[i],s1[i]+D+1,0),fill(s2[i],s2[i]+C+1,0);
    for(int i=1;i<=C;i++)fill(s3[i],s3[i]+D+1,0),fill(s4[i],s4[i]+C+1,0);
    fill(sb,sb+C+1,0),fill(sv,sv+n+1,0);
}
void update(int x,int y,ui v){
    if(y==0){sb[bv2[x]]+=v,sv[x]+=v;return;}
    int bx=bv[x=bv2[x]],by=bv[y=bv2[y]];
    s1[bx][by]+=v,s2[bx][y]+=v,s3[x][by]+=v,s4[x][y]+=v;
}
ui query(int x,int y){
    ui res=0;
    for(int i=1;i<bv2[x];i++)res+=sb[i];
    for(int i=rbv2[bv2[x]-1]+1;i<=x;i++)res+=sv[i];
    if(!y)return res;
    for(int i=rbv2[bv2[x]-1]+1;i<=x;i++)if(!del[i]&&pre[i]&&bv2[pre[i]]<bv2[y])res+=val[a[pos[i]]];
    for(int i=rbv2[bv2[y]-1]+1;i<=y;i++)if(!del[i]&&nxt[i]<=x)res+=val[a[pos[i]]];
    int bx=bv[x=bv2[x]],by=bv[y=bv2[y]];
    for(int i=1;i<bx;i++)for(int j=1;j<by;j++)res+=s1[i][j];
    for(int i=1;i<bx;i++)for(int j=rbv[by-1]+1;j<y;j++)res+=s2[i][j];
    for(int i=rbv[bx-1]+1;i<x;i++)for(int j=1;j<by;j++)res+=s3[i][j];
    for(int i=rbv[bx-1]+1;i<x;i++)for(int j=rbv[by-1]+1;j<y;j++)res+=s4[i][j];
    return res;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)p[i]=read(),pos[p[i]]=i;
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)val[i]=read();
    m=read(),B=n/sqrt(m);if(!B)B=1;
    for(int i=1;i<=n;i++)b[i]=(i-1)/B+1;
    for(int i=1;i<b[n];i++)rb[i]=i*B;rb[b[n]]=n;
    L2=sqrt(n);
    for(int i=1;i<=n;i++)bv2[i]=(i-1)/L2+1;
    for(int i=1;i<bv2[n];i++)rbv2[i]=i*L2;rbv2[C=bv2[n]]=n;
    L1=sqrt(C);
    for(int i=1;i<=C;i++)bv[i]=(i-1)/L1+1;
    for(int i=1;i<bv[C];i++)rbv[i]=i*L1;rbv[D=bv[C]]=C;
    for(int i=1,l,r,d,u;i<=m;i++){
        l=read(),r=read(),d=read(),u=read();
        if(b[l]==b[r]){
            for(int j=l;j<=r;j++)vst[a[j]]=0;
            for(int j=l;j<=r;j++)if(p[j]>=d&&p[j]<=u)vst[a[j]]=1;
            for(int j=l;j<=r;j++)if(vst[a[j]])ans[i]+=val[a[j]],vst[a[j]]=0;
        }
        else vq[b[l]].push_back((qry){l,r,d,u,i});
    }
    for(int k=1;k<=b[n];k++)if(vq[k].size()){
        sort(vq[k].begin(),vq[k].end(),cmp);
        fill(lst,lst+n+1,0),fill(nxt,nxt+n+1,n+1),fill(del,del+n+1,1);
        for(int i=1;i<=n;i++)if(pos[i]>rb[k-1])pre[i]=lst[a[pos[i]]],lst[a[pos[i]]]=i,del[i]=0;
        for(int i=1;i<=n;i++)if(pos[i]>rb[k-1]&&pre[i])nxt[pre[i]]=i;
        init();
        for(int i=1;i<=n;i++)if(pos[i]>rb[k-1])update(i,pre[i],val[a[pos[i]]]);
        int r=n;
        for(auto q:vq[k]){
            while(r>q.r){
                update(p[r],pre[p[r]],-val[a[r]]);
                if(nxt[p[r]]!=n+1)update(nxt[p[r]],p[r],-val[a[r]]),update(nxt[p[r]],pre[p[r]],val[a[r]]),pre[nxt[p[r]]]=pre[p[r]];
                if(pre[p[r]])nxt[pre[p[r]]]=nxt[p[r]];
                del[p[r]]=1,r--;
            }
            for(int l=rb[k-1]+1;l<q.l;l++){
                update(p[l],pre[p[l]],-val[a[l]]);
                if(nxt[p[l]]!=n+1)update(nxt[p[l]],p[l],-val[a[l]]),update(nxt[p[l]],pre[p[l]],val[a[l]]),pre[nxt[p[l]]]=pre[p[l]];
                if(pre[p[l]])nxt[pre[p[l]]]=nxt[p[l]];
                del[p[l]]=1;
            }
            ans[q.id]=query(q.u,q.d-1)-query(q.d-1,q.d-1);
            for(int l=q.l-1;l>rb[k-1];l--){
                update(p[l],pre[p[l]],val[a[l]]);
                if(nxt[p[l]]!=n+1)update(nxt[p[l]],pre[p[l]],-val[a[l]]),update(nxt[p[l]],p[l],val[a[l]]),pre[nxt[p[l]]]=p[l];
                if(pre[p[l]])nxt[pre[p[l]]]=p[l];
                del[p[l]]=0;
            }
        }
    }
    for(int i=1;i<=m;i++)printf("%u\n",ans[i]);
    return 0;
}