JOI2012 春合宿 3日目

#include<stdio.h>
#include<algorithm>
using namespace std;
int X[200050];
int Y[200050];
int x[200050];
int y[200050];
int d[100050];
int e[100050];
int f[100050];
int g[100050];
pair<int,pair<int,int> > event[200050];
long long par[450];
long long chi[202500];
long long sum[450];
int SQ=450;
long long val[450];
void init(){
	for(int i=0;i<200050;i++)X[i]=Y[i]=x[i]=y[i]=0;
	for(int i=0;i<100050;i++)d[i]=e[i]=f[i]=g[i]=0;
	for(int i=0;i<200050;i++)event[i]=make_pair(0,make_pair(0,0));
	for(int i=0;i<450;i++)par[i]=sum[i]=val[i]=0LL;
	for(int i=0;i<202500;i++)chi[i]=0LL;
}
void ADD(int a,int b){//[a,b)
	int L=(a+SQ-1)/SQ;
	int R=b/SQ;
	if(L>=R){
		for(int i=a;i<b;i++){
			if(chi[i]){
				sum[i/SQ]-=chi[i];
				chi[i]=0LL;
			}else{
				chi[i]=y[i+1]-y[i];
				sum[i/SQ]+=chi[i];
			}
		}
		return;
	}
	for(int i=a;i<L*SQ;i++){
		if(chi[i]){
			sum[i/SQ]-=chi[i];
			chi[i]=0LL;
		}else{
			chi[i]=y[i+1]-y[i];
			sum[i/SQ]+=chi[i];
		}
	}
	for(int i=R*SQ;i<b;i++){
		if(chi[i]){
			sum[i/SQ]-=chi[i];
			chi[i]=0LL;
		}else{
			chi[i]=y[i+1]-y[i];
			sum[i/SQ]+=chi[i];
		}
	}
	for(int i=L;i<R;i++){
		if(par[i])par[i]=0LL;
		else par[i]=val[i];
	}
}
long long SUM(){
	long long ret=0LL;
	for(int i=0;i<SQ;i++){
		if(par[i])ret+=par[i]-sum[i];
		else ret+=sum[i];
	}
	return ret;
}
int main(){
	int a,b,c;
	//scanf("%d%d%d",&a,&b,&c);
	while(~scanf("%d%d%d",&a,&b,&c)){
	init();
	for(int i=0;i<c;i++){
		scanf("%d%d%d%d",d+i,e+i,f+i,g+i);
		e[i]++;
		g[i]++;
		X[i*2]=d[i];
		X[i*2+1]=e[i];
		Y[i*2]=f[i];
		Y[i*2+1]=g[i];
	}

	std::sort(X,X+c*2);
	std::sort(Y,Y+c*2);
	int sx=0;
	int sy=0;
	x[sx++]=X[0];
	y[sy++]=Y[0];
	for(int i=1;i<c*2;i++){
		if(X[i]!=X[i-1])x[sx++]=X[i];
	}
	for(int i=1;i<c*2;i++){
		if(Y[i]!=Y[i-1])y[sy++]=Y[i];
	}
	for(int i=0;i<c;i++){
		int atT=lower_bound(x,x+sx,d[i])-x;
		int atB=lower_bound(x,x+sx,e[i])-x;
		int atL=lower_bound(y,y+sy,f[i])-y;
		int atR=lower_bound(y,y+sy,g[i])-y;
		event[i*2]=make_pair(atT,make_pair(atL,atR));
		event[i*2+1]=make_pair(atB,make_pair(atL,atR));
	}
	std::sort(event,event+c*2);
	for(int i=0;i<sy-1;i++){
		val[i/SQ]+=y[i+1]-y[i];
	}
	long long ret=0LL;
	int use=0;
	for(int i=0;i<c*2-1;i++){
		ADD(event[i].second.first,event[i].second.second);
		ret+=SUM()*(x[event[i+1].first]-x[event[i].first]);
		use+=(x[event[i+1].first]-x[event[i].first]);
	}

	printf("%lld\n",(long long)a*b-ret);
		}
}