学步园

传送门：【COGS】451 布匠问题

题目分析：这题一看就是二维线段树区间修改区间查询啊，可是。。。写了一下午还是写不出来。。。后来索性暴力1000棵线段树，然后T了三组数据。。。感觉没治了。。。

后来突然想到是不是可以写四分树（四个儿子的线段树），每一个儿子都是一个矩阵，叶子节点就是1X1的矩阵，然后就这么YY了个写法写了下，然后让我十分无语的是：我竟然AC了。。。。。竟然AC了！

迫不及待的想去仰慕大神们的写法（AC了一题以后可以看其他人AC这题的代码），然后更让我无语的是！他们全部是暴力的！！！各种暴力无节操啊有木有！！

我的眼泪忍不住就哗哗哗的流啊T U T。。。

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define s1 o * 4 + 1
#define s2 o * 4 + 2
#define s3 o * 4 + 3
#define s4 o * 4 + 4
#define son1 s1 , lx , mx , ly , my
#define son2 s2 , lx , mx , my + 1 , ry
#define son3 s3 , mx + 1 , rx , ly , my
#define son4 s4 , mx + 1 , rx , my + 1 , ry
#define root  0 , 1 , n , 1 , m
#define rt o , lx , rx , ly , ry
#define xxyy x1 , x2 , y1 , y2

const int MAXN = 5000005 ;

int sum[MAXN] ;
int set[MAXN] ;

void pushdown ( int o , int lx , int rx , int ly , int ry ) {
	if ( ~set[o] ) {
		int mx = ( lx + rx ) >> 1 , my = ( ly + ry ) >> 1 ;
		set[s1] = set[o] , sum[s1] = set[o] ? ( mx - lx + 1 ) * ( my - ly + 1 ) : 0 ;
		set[s2] = set[o] , sum[s2] = set[o] ? ( mx - lx + 1 ) * ( ry - my ) : 0 ;
		set[s3] = set[o] , sum[s3] = set[o] ? ( rx - mx ) * ( my - ly + 1 ) : 0 ;
		set[s4] = set[o] , sum[s4] = set[o] ? ( rx - mx ) * ( ry - my ) : 0 ;
		set[o] = -1 ;
	}
}

void update ( int v , int x1 , int x2 , int y1 , int y2 , int o , int lx , int rx , int ly , int ry ) {
	if ( x1 <= lx && rx <= x2 && y1 <= ly && ry <= y2 ) {
		set[o] = v ;
		sum[o] = v ? ( rx - lx + 1 ) * ( ry - ly + 1 ) : 0 ;
		return ;
	}
	pushdown ( rt ) ;
	int mx = ( lx + rx ) >> 1 , my = ( ly + ry ) >> 1 ;
	if ( x1 <= mx && y1 <= my ) update ( v , xxyy , son1 ) ;
	if ( x1 <= mx && my <  y2 ) update ( v , xxyy , son2 ) ;
	if ( mx <  x2 && y1 <= my ) update ( v , xxyy , son3 ) ;
	if ( mx <  x2 && my <  y2 ) update ( v , xxyy , son4 ) ;
	sum[o] = sum[s1] + sum[s2] + sum[s3] + sum[s4] ;
}

int query ( int x1 , int x2 , int y1 , int y2 , int o , int lx , int rx , int ly , int ry ) {
	if ( x1 <= lx && rx <= x2 && y1 <= ly && ry <= y2 ) return sum[o] ;
	pushdown ( rt ) ;
	int mx = ( lx + rx ) >> 1 , my = ( ly + ry ) >> 1 , ans = 0 ;
	if ( x1 <= mx && y1 <= my ) ans += query ( xxyy , son1 ) ;
	if ( x1 <= mx && my <  y2 ) ans += query ( xxyy , son2 ) ;
	if ( mx <  x2 && y1 <= my ) ans += query ( xxyy , son3 ) ;
	if ( mx <  x2 && my <  y2 ) ans += query ( xxyy , son4 ) ;
	return ans ;
}

void scanf ( int& x , char c = 0 ) {
	while ( ( c = getchar () ) < '0' || c > '9' ) ;
	x = c - '0' ;
	while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}

void solve () {
	int n , m , q ;
	int op , x1 , x2 , y1 , y2 ;
	scanf ( "%d%d%d" , &n , &m , &q ) ;
	CLR ( sum , 0 ) ;
	CLR ( set , -1 ) ;
	while ( q -- ) {
		scanf ( op ) , scanf ( x1 ) , scanf ( y1 ) , scanf ( x2 ) , scanf ( y2 ) ;
		//printf ( "ok\n" ) ;
		if ( op == 0 ) {
			printf ( "%d\n" , query ( xxyy , root ) ) ;
		} else update ( 2 - op , xxyy , root ) ;
		//printf ( "ok\n" ) ;
	}
}

int main () {
	freopen ( "fabric.in" , "r" , stdin ) ;
	freopen ( "fabric.out" , "w" , stdout ) ;
	solve () ;
	return 0 ;
}