【洛谷3776】[APIO2017] 斑斓之地（平面圖歐拉公式）

給定一張$A\times B$的網格圖，把其中一條長度為$n$的路徑标為黑色（可能自交），其餘點為白色。$q$次詢問，每次求一個子矩陣中白色連通塊的數量。

點此看題面

• 給定一張\(A\times B\)的網格圖，把其中一條長度為\(n\)的路徑标為黑色（可能自交），其餘點為白色。
• \(q\)次詢問，每次求一個子矩陣中白色連通塊的數量。
• \(n\le10^5,A,B\le2\times10^5\)

平面圖歐拉公式

公式如下：

\[V-E+F=2

\]

其中\(V\)為點數，\(E\)為邊數，\(F\)為面數。

由于\(F\)中的面數是包含外面的，是以我們可以設\(F'\)表示圖形内部的面數，得到\(V-E+F'=1\)。

對于樹的問題我們常常利用\(V-E=1\)得出點數-邊數=連通塊數，其實就是\(F'=0\)的特殊情況。

對于這道題，在相鄰的網格之間連邊顯然得到的是一張平面圖，受樹情況的啟發就有結論：連通塊數=點數-邊數+面數。

貢獻讨論+二維數點

由于白點數量很大，而黑點數量很少，這也就意味着不合法情況數很少，是以無論點數、邊數、面數，我們都考慮用總情況數減去不合法情況數。

對于點數，非常簡單，就是用\((x_2-x_1+1)\times(y_2-y_1+1)\)減去子矩形\((x_1,y_1)-(x_2,y_2)\)中的黑點數。

代碼：\(O(nlogn)\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define M 200000
#define pb push_back
using namespace std;
int A,B,n,Rt[M+5][4];vector<int> p[M+5][4];
class ChairmanTree
{
	private:
		#define PT CI l=0,CI r=B
		#define LT l,mid
		#define RT mid+1,r
		int Nt;struct node {int V,S[2];}O[N*72];
	public:
		I void U(int& rt,CI x,PT)//單點修改
		{
			if(++(O[++Nt]=O[rt]).V,rt=Nt,l==r) return;RI mid=l+r>>1;
			x<=mid?U(O[rt].S[0],x,LT):U(O[rt].S[1],x,RT);
		}
		I int Q(CI rt,CI L,CI R,PT)//區間求和
		{
			if(!rt||L<=l&&r<=R) return O[rt].V;RI mid=l+r>>1;
			return (L<=mid?Q(O[rt].S[0],L,R,LT):0)+(R>mid?Q(O[rt].S[1],L,R,RT):0);
		}
}C[4];
int main()
{
	#define Mark(x,y) (xl=min(xl,x),xr=max(xr,x),yl=min(yl,y),yr=max(yr,y),\
		p[x][0].pb(y),p[x-1][1].pb(y),p[x][1].pb(y),p[x][2].pb(y-1),p[x][2].pb(y),\
		p[x-1][3].pb(y-1),p[x-1][3].pb(y),p[x][3].pb(y-1),p[x][3].pb(y))
	RI Qt,x,y,xl=1e9,xr=0,yl=1e9,yr=0;scanf("%d%d%d%d%d%d",&A,&B,&n,&Qt,&x,&y),Mark(x,y);
	RI i;char op;for(i=1;i<=n;++i) cin>>op,op=='N'?--x:(op=='S'?++x:(op=='W'?--y:++y)),Mark(x,y);
	RI j,k,sz;for(i=1;i<=A;++i) for(j=0;j^4;++j)
	{
		sort(p[i][j].begin(),p[i][j].end()),sz=unique(p[i][j].begin(),p[i][j].end())-p[i][j].begin();//去重
		for(Rt[i][j]=Rt[i-1][j],k=0;k^sz;++k) C[j].U(Rt[i][j],p[i][j][k]);//主席樹上修改
	}
	#define Qry(op,x1,y1,x2,y2) (C[op].Q(Rt[x2][op],y1,y2)-C[op].Q(Rt[x1-1][op],y1,y2))//詢問子矩形貢獻和
	long long t;W(Qt--) scanf("%d%d%d%d",&i,&j,&x,&y),t=1LL*(x-i+1)*(y-j+1)-Qry(0,i,j,x,y),//點數
		i^x&&(t-=1LL*(x-i)*(y-j+1)-Qry(1,i,j,x-1,y)),j^y&&(t-=1LL*(x-i+1)*(y-j)-Qry(2,i,j,x,y-1)),//邊數
		i^x&&j^y&&(t+=1LL*(x-i)*(y-j)-Qry(3,i,j,x-1,y-1)),i<xl&&xr<x&&j<yl&&yr<y&&++t,printf("%lld\n",t);//面數
	return 0;
}
           

敗得義無反顧，弱得一無是處