萬豬拱塔

• description
• solution
• code

description

題目描述
小七養(yǎng)了很多頭豬，它們分布在 n 行 m 列中，其中第 i 行第 j 列的豬圈養(yǎng)的是第 $w_{i,j}$ 種豬。
小七有時會選擇一個子矩形范圍內(nèi)的豬圈進行巡視，如果該子矩形包含 i 行 j 列 (1 ≤ i ≤ n; 1 ≤ j ≤ m)，且子矩形內(nèi)含有的豬種類編號最大值減去編號最小值恰好為 i × j - 1 ，則小七會獲得 i × j 的愉悅值。
小七想知道，如果他將每個可能的子矩形都巡視一次，總共能獲得多少愉悅值呢？你只需要輸出答案對 998244353 取模的結(jié)果。

輸入格式
輸入文件 pig.in 包含 1 + n × m 行。
第一行輸入兩個正整數(shù)依次表示 n; m 。
接下來 n 行每行包含 m 個正整數(shù)，其中第 i 行的第 j 個正整數(shù)表示 wi;j 。

輸出格式
輸出文件 pig.out 包含一行，僅一個非負整數(shù)，表示答案對 998244353 取模
的結(jié)果。
樣例輸入

2 2 1 3 2 4

樣例輸出

12

樣例解釋
合法子矩形面積為 1 的有 4 個，面積為 2 的有 2 個，面積為 4 的有 1 個。
數(shù)據(jù)范圍及約定

測試點編號n × m特殊性質(zhì)

1 ～ 2	≤ 50	無
3 ～ 6	≤ 10^4	無
7 ～ 12	≤ 2 × 10^5	n = 1
13 ～ 20	≤ 2 × 10^5	無

對于 100% 的數(shù)據(jù), 1 ≤ wi;j ≤ n × m ≤ 2 × 105 , 保證 wi;j 互不相同。

solution

先吐槽一下題目的 包含 真的是誤導(dǎo)新青年！！

我以為是原矩陣的$i$行$j$列，結(jié)果是選的矩陣重新編號后的$i$行$j$列

實際上就是問多少矩陣內(nèi)種類編號的極差等于矩陣行數(shù)乘列數(shù)再減一

---

應(yīng)該不會有人只拿case 1~2的暴力吧

case 1~6 ：枚舉所選矩陣的左上角，求出以其右下方每一個點為矩陣右下角的種類最大值和最小值，可以通過掃一遍，然后行加一的時候繼承上面一行信息，再操作

case 7~12 ：n=1是一個一維問題，可以用線段樹和單調(diào)棧解決

具體而言，枚舉矩陣右端點$r$，如果區(qū)間$[l,r]$合法，則滿足${\text{Max}}_{l,r}?{\text{?Min}}_{l,r}=r?l+1$

對于每個$l$的定義$f[l]={\text{Max}}_{l,r}?{\text{?Min}}_{l,r}+l$，用線段樹維護$f[l]$

因為種類互不相同，所以${?}_{l}f[l]\ge r+1$，只需要線段樹維護$f[l]$的最小值，最小值個數(shù)，以及所有$l$之和，就可以統(tǒng)計了，即$(r+1)?cnt?sum$

右端點移動$1$，用單調(diào)棧維護其影響的${\text{Max}}_{l,r},{\text{Min}}_{l,r}$，在線段樹上修改

${\text{Max}}_{l,r}$維護一個單調(diào)遞減棧，${\text{Min}}_{l,r}$維護一個單調(diào)遞增棧

case 13~20 ：很不幸，一維的做法并不能處理二維情況

考慮另外一種nb的轉(zhuǎn)化

考慮判定 權(quán)值 為$[l,r]$區(qū)間的點是否構(gòu)成了一個矩陣，記這些格子的顏色為黑色，其余均為白色

將$n\times m$的豬圈算上周圍一圈的空白邊界，看成$(n+1)\times (m+1)$的豬圈

產(chǎn)生$(n+1)\times (m+1)$個$2\times 2$的小正方形豬圈（不能超出邊界），標記在$2\times 2$這個矩陣的左上角

如果所有黑色格子能圍成一個矩陣，當且僅當恰好有4個小豬圈只有1個黑點，沒有任何一個小豬圈有3個黑點

不要急，仔細想想這句很妙的話，小豬圈是由其左上角表示的，只有圍成的矩陣的四個頂點所在的小豬圈，只含這個頂點一個黑點

從小到大枚舉權(quán)值$r$，定義$F[l]$為染黑權(quán)值為$[l,r]$的格子，其余格子為白色，小豬圈內(nèi)有$1/3$個合格子的小豬圈數(shù)量

顯然$F[r]=4,F[l]\ge 4$

這個時候可以利用一維的做法，線段樹維護$F[l]$的最小值，最小值個數(shù)以及這些$l$的和，貢獻計算也是一樣的

當$r$增加$1$的時候，只會影響$4$個$2\times 2$的矩陣（分別是$r+1$做左上角，右上角，左下角，右下角時的不同的$4$個小豬圈）

暴力修改即可——詳見代碼

最后就是這道題的天坑——卡常

必須開Ofast不然分竟然跟暴力差不多，快讀快輸，還有這種$n\times m\le 2e5$的必須卡著矩陣長相開數(shù)組的

這是什么jian題 好題，真的是好題！！

code

#pragma GCC optimize( "Ofast" ) #include <cstdio> #define mod 998244353 #define maxn 200005 int Min[maxn << 2], cnt[maxn << 2], tag[maxn << 2]; long long sum[maxn << 2]; int ID[maxn]; int n, m, **w;#define Make( arr ) do { \arr = new int*[n + 3]; \for( int i = 0;i <= n + 2;i ++ ) arr[i] = new int[m + 3](); \ } while( false )inline void read( int &x ) {x = 0; char s = getchar();while( s < '0' or s > '9' ) s = getchar();while( '0' <= s and s <= '9' ) {x = ( x << 1 ) + ( x << 3 ) + ( s ^ 48 );s = getchar();} }inline void write( int x ) {if( x >= 10 ) write( x / 10 );putchar( x % 10 ^ 48 ); }#define lson num << 1 #define rson num << 1 | 1 #define inf 0x3f3f3f3fint chkmin( int x, int y ) { return x < y ? x : y; }inline void pushup( int num ) {Min[num] = chkmin( Min[lson], Min[rson] );cnt[num] = sum[num] = 0;if( Min[num] == Min[lson] ) cnt[num] += cnt[lson], sum[num] += sum[lson];if( Min[num] == Min[rson] ) cnt[num] += cnt[rson], sum[num] += sum[rson]; }inline void build( int num, int l, int r ) {if( l == r ) { Min[num] = inf, cnt[num] = 1, sum[num] = l; return; }int mid = ( l + r ) >> 1;build( lson, l, mid );build( rson, mid + 1, r );pushup( num ); }inline void pushdown( int num ) {if( ! tag[num] ) return;Min[lson] += tag[num];tag[lson] += tag[num];Min[rson] += tag[num];tag[rson] += tag[num];tag[num] = 0; }inline void modify( int num, int l, int r, int L, int R, int val ) {if( r < L or R < l ) return;if( L <= l and r <= R ) { Min[num] += val, tag[num] += val; return; }pushdown( num );int mid = ( l + r ) >> 1;modify( lson, l, mid, L, R, val );modify( rson, mid + 1, r, L, R, val );pushup( num ); }inline void modify( int r, int c, int Max, int opt ) {static int arr[4];if( ! ~opt ) {arr[0] = w[r][c], arr[1] = w[r][c + 1], arr[2] = w[r + 1][c], arr[3] = w[r + 1][c + 1];for( int i = 0;i < 3;i ++ )for( int j = 0;j < 3;j ++ )if( arr[j] > arr[j + 1] ) arr[j] ^= arr[j + 1] ^= arr[j] ^= arr[j + 1];}int ip = 0;for(;ip < 4 and arr[ip] <= Max;ip ++ );if( ip == 1 or ( ip > 1 and arr[ip - 1] ^ arr[ip - 2] ) )modify( 1, 1, n * m, ip == 1 ? 1 : arr[ip - 2] + 1, arr[ip - 1], opt );if( ip == 3 or ( ip > 3 and arr[ip - 3] ^ arr[ip - 4] ) )modify( 1, 1, n * m, ip == 3 ? 1 : arr[ip - 4] + 1, arr[ip - 3], opt ); }inline int mul( int x, int y ) { return 1ll * x * y % mod; } inline int sub( int x, int y ) { return x - y < 0 ? x - y + mod : x - y; } inline int add( int x, int y ) { return 1ll * x + y >= mod ? 1ll * x + y - mod : x + y; }int main() {freopen( "pig.in", "r", stdin );freopen( "pig.out", "w", stdout );scanf( "%d %d", &n, &m ); Make( w );for( int i = 0;i <= n + 1;i ++ ) w[i][0] = w[i][m + 1] = n * m + 1;for( int i = 1;i <= m;i ++ ) w[0][i] = w[n + 1][0] = n * m + 1;for( int i = 1;i <= n;i ++ )for( int j = 1;j <= m;j ++ )read( w[i][j] ), ID[w[i][j]] = ( i - 1 ) * m + j;build( 1, 1, n * m );int ans = 0;for( int i = 1;i <= n * m;i ++ ) {int r = ( ID[i] - 1 ) / m + 1, c = ID[i] - ( r - 1 ) * m;modify( 1, 1, n * m, i, i, -inf );for( int j = -1;j <= 0;j ++ )for( int k = -1;k <= 0;k ++ ) {modify( r + j, c + k, i - 1, -1 );modify( r + j, c + k, i, 1 );}if( Min[1] == 4 ) ans = add( ans, sub( mul( i + 1, cnt[1] ), sum[1] % mod ) );}write( ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[2020-09-11 CQBZ/HSZX多校联测 T3] 万猪拱塔（线段树+巧妙转化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。