lxl的分治都场切了这道题的类分治居然没想到
考虑反着做这个东西。
反着做有一个好处就是可以\(O(1)\)用并查集处理一个点在一列中最近的两个坏点。
我们发现每次答案增大就是增大包含正在添加点的矩形。
这个东西很好做，我们将正在处理的点的这一行每个点的上下界都查出来，然后枚举左部点，右部用双指针指出分界点，分类讨论一下位置关系然后维护前缀和即可。
时间复杂度\(O(nm^2)\)，代码大常数，要开O2才能过。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 500
#define M 250000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,m,x[M+5],y[M+5],l[N+5][N+5],r[N+5][N+5],A[N+5],B[N+5],now,ar,br;ll ans[M+5],QA[N+5],QB[N+5],QAB[N+5];
I int GetL(int x,int y){return l[x][y]==x?x:l[x][y]=GetL(l[x][y],y);}
I int GetR(int x,int y){return r[x][y]==x?x:r[x][y]=GetR(r[x][y],y);}
int main(){
	freopen("flip.in","r",stdin);freopen("flip.out","w",stdout);
	re int i,j,k;scanf("%d%d",&n,&m);for(i=1;i<=n*m;i++)scanf("%d%d",&x[i],&y[i]);
	for(i=1;i<=n+1;i++) for(j=1;j<=m;j++) l[i][j]=r[i][j]=i;
	for(k=n*m;k;k--){
		l[x[k]][y[k]]=x[k]-1;r[x[k]][y[k]]=x[k]+1;ans[k]=ans[k+1];for(i=1;i<=m;i++) A[i]=GetL(x[k],i),B[i]=GetR(x[k],i);
		for(i=y[k]-1;i;i--) A[i]=max(A[i],A[i+1]),B[i]=min(B[i],B[i+1]);QA[y[k]-1]=QB[y[k]-1]=QAB[y[k]-1]=0;
		for(i=y[k]+1;i<=m;i++) A[i]=max(A[i-1],A[i]),B[i]=min(B[i-1],B[i]);for(i=y[k];i<=m;i++)QA[i]=QA[i-1]+x[k]-A[i],QB[i]=QB[i-1]+B[i]-x[k],QAB[i]=QAB[i-1]+(x[k]-A[i])*(B[i]-x[k]);
		for(ar=br=i=y[k];i;i--){
			while(ar<=m&&A[ar]<A[i]) ar++;while(br<=m&&B[br]>B[i]) br++;
			if(ar<=br)ans[k]+=(x[k]-A[i])*(B[i]-x[k])*(ar-y[k])+(B[i]-x[k])*(QA[br-1]-QA[ar-1])+QAB[m]-QAB[br-1];
			else ans[k]+=(x[k]-A[i])*(B[i]-x[k])*(br-y[k])+(x[k]-A[i])*(QB[ar-1]-QB[br-1])+QAB[m]-QAB[ar-1];//printf("%lld\n",ans[k]);
		}
	}
	for(i=2;i<=n*m+1;i++) printf("%lld\n",ans[i]);
}