Problem Link

题目大意

给定 $n\times n$ 的 01 矩阵 $A$ 的第一行和第一列，定义 $A_{i,j}=1-A_{i-1,j}\times A_{i,j-1}$，$q$ 次询问 $A$ 的某个子矩阵的元素和。

数据范围：$n,q\le 2\times 10^5$。

思路分析

观察这个矩阵，发现如果 $A_{i,j}=1$ 那么 $A_{i+1,j},A_{i,j+1}=0$，从而 $A_{i+1,j+1}=1$，因此所有的 $1$ 构成若干向右下方的射线。

并且我们发现如果 $A_{i,j}=1,A_{i-1,j-1}=0$，那么可以推出 $A_{i,j}$ 左上角的矩形一定形如 $\begin{bmatrix}x&y&1\\z&0&0\\1&0&1\end{bmatrix}$。

此时 $y,z$ 中至少有一个 $1$，又因为连续的两个 $1$ 显然不能出现在第一行或第一列以外的地方。

因此这种情况只能出现在 $\min(i,j)\le 3$ 的位置，也就是前三行或前三列，那么暴力求出第三行和第三列，其中的每个 $1$ 都对应一条向右下方的射线，且不存在其他的 $1$。

对子矩形询问差分成一个以 $(1,1)$ 为左上角的询问 $(x,y)$，对于一条射线的起点 $(i,j)$，其对询问的贡献就是 $\max(0,\min(x-i,y-j))$。

先求出 $\sum \min(x-i,y-j)$，$\min(x-i,y-j)<0$ 的点一定是 $A_{3,j+1\sim n}$ 和 $A_{i+1\sim n,3}$ 范围内的点，后缀和即可。

时间复杂度 $\mathcal O((n+q)\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef vector<int> vi;
const int MAXN=2e5+5;
int n,q,a[4][MAXN],b[MAXN][4],cl[MAXN],cr[MAXN];
ll dl[MAXN],dr[MAXN];
bool cmp(array<int,2> i,array<int,2> j) { return i[0]-i[1]<j[0]-j[1]; }
vector<ll> mosaic(vi X,vi Y,vi T,vi B,vi L,vi R) {
	n=X.size(),q=T.size();
	if(n<=3) {
		vector <vi> M(n,vi(n));
		M[0]=X;
		for(int i=1;i<n;++i) {
			M[i][0]=Y[i];
			for(int j=1;j<n;++j) M[i][j]=(M[i-1][j]|M[i][j-1])^1;
		}
		for(int i=0;i<n;++i) for(int j=1;j<n;++j) M[i][j]+=M[i][j-1];
		for(int i=1;i<n;++i) for(int j=0;j<n;++j) M[i][j]+=M[i-1][j];
		vector <ll> ans(q);
		for(int i=0;i<q;++i) {
			ans[i]=M[B[i]][R[i]];
			if(T[i]) ans[i]-=M[T[i]-1][R[i]];
			if(L[i]) ans[i]-=M[B[i]][L[i]-1];
			if(T[i]&&L[i]) ans[i]+=M[T[i]-1][L[i]-1];
		}
		return ans;
	}
	for(int i=1;i<=n;++i) a[1][i]=X[i-1],b[i][1]=Y[i-1];
	a[2][1]=Y[1],a[3][1]=Y[2],b[1][2]=X[1],b[1][3]=X[2];
	for(int o:{2,3}) for(int i=2;i<=n;++i) {
		a[o][i]=(a[o-1][i]|a[o][i-1])^1;
		b[i][o]=(b[i][o-1]|b[i-1][o])^1;
	}
	vector <array<int,2>> Z;
	for(int i=3;i<=n;++i) if(a[3][i]) Z.push_back({3,i}),++cl[i],dl[i]+=i;
	for(int i=4;i<=n;++i) if(b[i][3]) Z.push_back({i,3}),++cr[i],dr[i]+=i;
	for(int i=n;i>=1;--i) cl[i]+=cl[i+1],dl[i]+=dl[i+1],cr[i]+=cr[i+1],dr[i]+=dr[i+1];
	sort(Z.begin(),Z.end(),cmp);
	int k=Z.size();
	vector <ll> sl(k),sr(k);
	if(k) {
		sl[0]=Z[0][1];
		for(int i=1;i<k;++i) sl[i]=sl[i-1]+Z[i][1];
		sr[k-1]=Z[k-1][0];
		for(int i=k-2;~i;--i) sr[i]=sr[i+1]+Z[i][0];
	}
	for(int i=1;i<=3;++i) for(int j=1;j<=n;++j) a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
	for(int i=1;i<=n;++i) for(int j=1;j<=3;++j) b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];
	auto qry=[&](int x,int y) -> ll {
		if(x<=3) return a[x][y];
		if(y<=3) return b[x][y];
		ll s=a[3][y]+b[x][3]-a[3][3];
		int i=upper_bound(Z.begin(),Z.end(),array<int,2>{x,y},cmp)-Z.begin();
		if(i>0) s+=1ll*i*y-sl[i-1];
		if(i<k) s+=1ll*(k-i)*x-sr[i];
		s+=dl[y]-1ll*y*cl[y];
		s+=dr[x]-1ll*x*cr[x];
		return s;
	};
	vector <ll> ans(q);
	for(int i=0;i<q;++i) ans[i]=qry(B[i]+1,R[i]+1)-qry(T[i],R[i]+1)-qry(B[i]+1,L[i])+qry(T[i],L[i]);
	return ans;
}