自动搬运

查看原文

来自洛谷，原作者为

	Undead2008 。

搬运于2025-08-24 23:03:50，当前版本为作者最后更新于2024-09-12 22:17:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这个生成方式不好刻画，考虑打表观察答案网格的性质。

打表可以发现对于大部分的 $(i,j)$，$(i,j)$ 和 $(i-1,j-1)$ 的颜色相同。事实上对于所有 $i,j\ge 4$，该性质成立。

证明一下。考虑对一个 $4\times 4$ 的网格标号，如上图。我们想要证明 $\tt 1$ 格子和 $\tt 2$ 格子的颜色总是相等，不妨先考虑不等的情况：

• $\tt 1$ 格子为黑色，$\tt 2$ 格子为白色：得出 $\tt 3$ 格子和 $\tt 4$ 格子均为白色，$\tt 2$ 格子理应为黑色，推出矛盾；
• $\tt 1$ 格子为白色，$\tt 2$ 格子为黑色：得出 $\tt 3$ 格子和 $\tt 4$ 格子均为白色，$\tt A$ 格子均为黑色，$\tt B$ 格子均为白色，$\tt 1$ 格子理应为黑色，推出矛盾。

所以 $\tt 1$ 格子和 $\tt 2$ 格子颜色总是相等，证明了上述结论。

所以我们暴力做前三行和前三列，之后的格子颜色都可以推出，查询时是一个等差序列求和，分讨一下即可。

#include"bits/stdc++.h"
using namespace std;
#define L long long
const int maxN = 200010;
const int B = 3;
int n,q,a[B+2][maxN],b[maxN][B+2];
int Mex[2][2];
inline int Geta(int Xl,int Yl,int Xr,int Yr){
	return a[Xr][Yr]-a[Xl-1][Yr]-a[Xr][Yl-1]+a[Xl-1][Yl-1];
}
inline int Getb(int Xl,int Yl,int Xr,int Yr){
	return b[Xr][Yr]-b[Xl-1][Yr]-b[Xr][Yl-1]+b[Xl-1][Yl-1];
}
int Id[maxN<<1],Idx;
L Su[maxN<<1],Sl[maxN<<1],Sr[maxN<<1];
inline L Cl(int l,int r){
	return (Sl[r]-Sl[l-1])-(Su[r]-Su[l-1])*(l-1);
}
inline L Cr(int l,int r){
	return (Sr[r]-Sr[l-1])-(Su[r]-Su[l-1])*(Idx-r);
}
inline int Origin(int X,int Y){
	int Dl=min(X-B,Y-B);
	X-=Dl,Y-=Dl;
	if(Y==B)return n-X+1;
	return n-B+1+Y-B;
}
inline L Solve(int Xl,int Yl,int Xr,int Yr){
	int Lb=Origin(Xr,Yl),Rb=Origin(Xl,Yr),Ln=min(Xr-Xl+1,Yr-Yl+1);
	return Cl(Lb,Lb+Ln-1)+(Su[Rb-Ln+1]-Su[Lb+Ln-1])*Ln+Cr(Rb-Ln+2,Rb);
}
vector<L> mosaic(vector<int> Xo,vector<int> Yo,vector<int> To,vector<int> Bo,vector<int> Lo,vector<int> Ro){
	n=Xo.size(),q=To.size();
	Mex[0][0]=1;
	vector<L>Ans;
	for(int i=1;i<=n;i++)a[1][i]=Xo[i-1];
	for(int j=1;j<=min(B,n);j++)a[j][1]=Yo[j-1];
	for(int j=B+1;j<=n;j++)b[j][1]=Yo[j-1];
	for(int i=2;i<=B;i++)
		for(int j=2;j<=n;j++)
			a[i][j]=Mex[a[i][j-1]][a[i-1][j]];
	for(int i=B+1;i<=n;i++)
		for(int j=2;j<=B;j++)
			b[i][j]=Mex[b[i][j-1]][(i==B+1?a[i-1][j]:b[i-1][j])];
	for(int j=n;j>B;j--)Su[++Idx]=b[j][B];
	for(int j=B;j<=n;j++)Su[++Idx]=a[B][j];
	for(int i=1;i<=Idx;i++)Sl[i]=Sl[i-1]+i*Su[i];
	for(int i=1;i<=Idx;i++)Sr[i]=Sr[i-1]+(Idx-i+1)*Su[i];
	for(int i=1;i<=Idx;i++)Su[i]=Su[i-1]+Su[i];
	for(int i=1;i<=B;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	for(int i=B+1;i<=n;i++)
		for(int j=1;j<=B;j++)
			b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
	for(int i=1,Xl,Yl,Xr,Yr;i<=q;i++){
		Xl=To[i-1]+1,Yl=Lo[i-1]+1,Xr=Bo[i-1]+1,Yr=Ro[i-1]+1;
		if(Xr<=B)Ans.push_back(Geta(Xl,Yl,Xr,Yr));
		else if(Xl>B&&Yr<=B)Ans.push_back(Getb(Xl,Yl,Xr,Yr));
		else if(Yr<=B)Ans.push_back(Getb(B+1,Yl,Xr,Yr)+Geta(Xl,Yl,B,Yr));
		else{
			int A=0;
			if(Xl<=B)A+=Geta(Xl,Yl,B,Yr),Xl=B+1;
			if(Yl<=B)A+=Getb(Xl,Yl,Xr,B),Yl=B+1;
			Ans.push_back(A+Solve(Xl,Yl,Xr,Yr));
		}
	}
	return Ans;
}

主函数部分是直接从题目附件里贺的：

#ifndef ONLINE_JUDGE
int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> Xo(N), Yo(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &Xo[i]));
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &Yo[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> To(Q), Bo(Q), Lo(Q), Ro(Q);
  for (int k = 0; k < Q; k++)
    assert(4 == scanf("%d%d%d%d", &To[k], &Bo[k], &Lo[k], &Ro[k]));
  fclose(stdin);

  std::vector<long long> Co = mosaic(Xo, Yo, To, Bo, Lo, Ro);

  int S = (int)Co.size();
  for (int k = 0; k < S; k++)
    printf("%lld\n", Co[k]);
  fclose(stdout);

  return 0;
}
#endif