鋪地毯

• problem
• solution
• code

problem

給定矩陣的長寬 $P,Q$，矩陣從下往上從左往后編號增加，$(0,0)～(P,Q)$。

給定 $n$ 張長寬平行于坐標軸的矩形地毯，左下角和右上角的坐標。

求被至少 $n?1$ 張地毯覆蓋到的格子數量。

$n\le 3e5,P,Q\le 1e9$。

solution

矩形欸！算的也是矩形相關的覆蓋面積。

樹套樹 $n{\log }^{2}n$，掃描線 $n\log n$。笑死，根本寫不動。

observation1：任何矩形的交最后一定也是平行于坐標軸的矩形或為空。

observation2：矩形的交不可逆，即不能將所有矩形交起來再去掉其中一個得到 $n?1$ 個矩形的交。

對于矩陣序列計算前綴交和后綴交，然后排除掉第 $i$ 個矩形。

即算 $[1,i)?(i,n]$ 的矩形的交，然后計算給答案。

這樣就計算了每 $n?1$ 個矩形的交。

但是如果某些部分是 $n$ 個矩形的交，就會被計算 $n$ 次，最后去重一下減掉 $n?1$ 次的計算結果即可。

code

#include <bits/stdc++.h> using namespace std; #define maxn 300005 int P, Q, n, T; struct node {int l1, r1, l2, r2;friend node cross( node x, node y ) {return { max( x.l1, y.l1 ), max( x.r1, y.r1 ), min( x.l2, y.l2 ), min( x.r2, y.r2 ) };}long long calc() { if( l1 > l2 or r1 > r2 ) return 0;else return 1ll * ( l2 - l1 ) * ( r2 - r1 );} }matrix[maxn], pre[maxn], suf[maxn];int main() {freopen( "carpet.in", "r", stdin );freopen( "carpet.out", "w", stdout );scanf( "%d", &T );while( T -- ) {scanf( "%d %d %d", &P, &Q, &n );for( int i = 1, l1, r1, l2, r2;i <= n;i ++ ) {scanf( "%d %d %d %d", &l1, &r1, &l2, &r2 );matrix[i] = { l1, r1, l2, r2 };}if( n == 1 ) { printf( "%lld\n", matrix[1].calc() ); continue; }long long ans = 0;pre[1] = matrix[1], suf[n] = matrix[n];for( int i = 2;i <= n;i ++ ) pre[i] = cross( pre[i - 1], matrix[i] );for( int i = n - 1;i;i -- ) suf[i] = cross( suf[i + 1], matrix[i] );ans += pre[n - 1].calc();ans += suf[2].calc();for( int i = 2;i < n;i ++ ) ans += cross( pre[i - 1], suf[i + 1] ).calc();ans -= ( n - 1 ) * pre[n].calc();printf( "%lld\n", ans );}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的铺地毯（矩形的交+前后缀矩形交）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。