自动搬运

查看原文

来自洛谷，原作者为

	FunnyCreatress AFOed.

搬运于2025-08-24 22:39:54，当前版本为作者最后更新于2022-03-16 08:48:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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