树套树做矩形加矩形求和。

题目大意：
有一个 \(n\times n\) 的矩阵，每个位置上初始值都为 \(0\)，\(q\) 次操作，分为两种：
1.把横坐标在 \([x_1,x_2]\) 范围内，纵坐标在 \([y_1,y_2]\) 范围内的所有数加上一个 \(val\)；
2.求横坐标在 \([x_1,x_2]\) 范围内，纵坐标在 \([y_1,y_2]\) 范围内的所有数的值的和。
数据范围：
\(n,q\le 200000\)。

解法：

维护两棵线段树套线段树,记为A和B。

每次矩形加的时候,在A的外层上找到对应区间,对内层进行区间加,维护区间和。

在B的外层上在找到对应区间之前遍历到的所有节点,对那些节点的内层线段树区间加,维护区间和。

然后查询一个矩形和的时候,就是在B的外层对应位置上找到对应区间，区间求和。

在A的外层上在找到对应区间之前遍历到的所有节点,计算与询问区间的交的面积作为系数,区间求和。

Talk is cheap,and this is my Code.

#include <iostream>
using namespace std ;

#define int long long
const int N = 400005 , L = 20 ;
int n , q , dt , rt[N] , ls[N*L*L] , rs[N*L*L] ;

int read ( ) {
	char ch = getchar ( ) ;
	int x = 0 ;
	while ( ch < '0' || ch > '9' )
		ch = getchar ( ) ;
	while ( ch >= '0' && ch <= '9' )
		x = x * 10 + ch - 48 , ch = getchar ( ) ;
	return x ;
}

struct Sgt {

int t[N*L*L] , g[N*L*L] ;

void pushdown ( int k , int l , int r ) {
	if ( ! g [ k ] ) return ;
	if ( ! ls [ k ] ) ls [ k ] = ++ dt ;
	if ( ! rs [ k ] ) rs [ k ] = ++ dt ;
	int mid = ( l + r ) >> 1 ;
	t [ ls [ k ] ] += ( mid - l + 1 ) * g [ k ] ;
	t [ rs [ k ] ] += ( r - mid ) * g [ k ] ;
	g [ ls [ k ] ] += g [ k ] ;
	g [ rs [ k ] ] += g [ k ] ;
	g [ k ] = 0 ;
}

void modify ( int &k , int l , int r , int x , int y , int z ) {
	if ( ! k ) k = ++ dt ;
	if ( x <= l && r <= y ) {
		t [ k ] += z * ( r - l + 1 ) ;
		g [ k ] += z ;
		return ;
	}
	pushdown ( k , l , r ) ;
	int mid = ( l + r ) >> 1 ;
	if ( x <= mid ) modify ( ls [ k ] , l , mid , x , y , z ) ;
	if ( y > mid ) modify ( rs [ k ] , mid + 1 , r , x , y , z ) ;
	t [ k ] = t [ ls [ k ] ] + t [ rs [ k ] ] ;
}

int query ( int k , int l , int r , int x , int y ) {
	if ( x <= l && r <= y )
		return t [ k ] ;
	pushdown ( k , l , r ) ;
	int mid = ( l + r ) >> 1 ;
	if ( y <= mid ) return query ( ls [ k ] , l , mid , x , y ) ;
	if ( x > mid ) return query ( rs [ k ] , mid + 1 , r , x , y ) ;
	return query ( ls [ k ] , l , mid , x , y ) + query ( rs [ k ] , mid + 1 , r , x , y ) ;
}

} A , B ;

void change ( int k , int l , int r , int x , int y , int L , int R , int z ) {
	if ( x <= l && r <= y ) {
		A .modify ( rt [ k ] , 1 , n , L , R , z ) ;
		return ;
	}
	B .modify ( rt [ k ] , 1 , n , L , R , z * ( min ( r , y ) - max ( l , x ) + 1 ) ) ;
	int mid = ( l + r ) >> 1 ;
	if ( x <= mid ) change ( k << 1 , l , mid , x , y , L , R , z ) ;
	if ( y > mid ) change ( k << 1 | 1 , mid + 1 , r , x , y , L , R , z ) ;
}

int query ( int k , int l , int r , int x , int y , int L , int R ) {
	if ( x <= l && r <= y )
		return B .query ( rt [ k ] , 1 , n , L , R ) + A .query ( rt [ k ] , 1 , n , L , R ) * ( r - l + 1 ) ;
	int mid = ( l + r ) >> 1 , res = A .query ( rt [ k ] , 1 , n , L , R ) * ( min ( r , y ) - max ( x , l ) + 1 ) ;
	if ( x <= mid ) res += query ( k << 1 , l , mid , x , y , L , R ) ;
	if ( y > mid ) res += query ( k << 1 | 1 , mid + 1 , r , x , y , L , R ) ;
	return res ;
}

signed main ( ) {
	cin >> n >> q ;
	while ( q -- ) {
		int op = read ( ) , xa = read ( ) , ya = read ( ) , xb = read ( ) , yb = read ( ) ;
		if ( xa > xb ) swap ( xa , xb ) ;
		if ( ya > yb ) swap ( ya , yb ) ;
		if ( op == 1 ) {
			int val = read ( ) ;
			change ( 1 , 1 , n , xa , xb , ya , yb , val ) ;
		}
		else {
			cout << query ( 1 , 1 , n , xa , xb , ya , yb ) << '\n' ;
		}
	}
	return 0 ;
}

码风可能有点与众不同，望包含。