CF526F Pudding Monsters

• problem
• solution
• code

problem

luogu翻譯

solution

observation ：每行每列恰好有一個(gè)棋子，所以如果一段區(qū)間 $[l,r]$ 會被某個(gè) $k$ 統(tǒng)計(jì)，當(dāng)且僅當(dāng)這個(gè)區(qū)間內(nèi)棋子縱坐標(biāo) $y_{max}?y_{min}+1=r?l+1$。

發(fā)現(xiàn)這是經(jīng)典的連續(xù)段計(jì)數(shù)問題。

標(biāo)配：單調(diào)棧 $+$ 線段樹。

將所有棋子按照橫坐標(biāo)升序排序。

枚舉右端點(diǎn) $r$，線段樹上每個(gè)葉子節(jié)點(diǎn) $l$ 維護(hù)的是 $[l,r]$ 的信息。

轉(zhuǎn)換一下條件判定：$y_{max}?y_{min}+l?r=0$。

因?yàn)?strong>每行每列恰好一個(gè)棋子，所以所有情況都有 $y_{max}?y_{min}\ge r?l$。

而最后要計(jì)入答案的是取等的情況，即最小值。

所以線段樹就維護(hù) $y_{max}?y_{min}+l?r$ 的最小值，以及最小值個(gè)數(shù)。

最后統(tǒng)計(jì)的時(shí)候，就統(tǒng)計(jì)最小值為 $0$ 的節(jié)點(diǎn)信息。

• $r$ 每次都是 $+1$，對應(yīng)的是線段樹整體 $?1$。

• $l$ 與 $r$ 無關(guān)，在最開始建樹是加上即可。

• $y_{max}$，維護(hù)一個(gè)單增棧，棧中第 $top$ 個(gè)元素維護(hù)的是區(qū)間 $[sMax[top?1]+1,sMax[top]]$ 的最大值信息，即這一段的縱坐標(biāo)最大值都是 $sMax[top]$。

  每次用右端點(diǎn) $r$ 與棧比較縱坐標(biāo)大小，如果 $r$ 大則彈棧，將 $top$ 維護(hù)的區(qū)間加上 $y_r?y_{sMax[top]}$。

• $y_{min}$，維護(hù)一個(gè)單減棧，棧中第 $top$ 個(gè)元素維護(hù)的是區(qū)間 $[sMin[top?1]+1,sMin[top]]$ 的最大值信息，即這一段的縱坐標(biāo)最小值都是 $sMin[top]$。

  每次用右端點(diǎn) $r$ 與棧比較縱坐標(biāo)大小，如果 $r$ 小則彈棧，將 $top$ 維護(hù)的區(qū)間加上 $y_{sMin[top]?y_i}$。

事件復(fù)雜度為 $O(n\log n)$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 300005 int n, tMax, tMin; int x[maxn], y[maxn], id[maxn], sMax[maxn], sMin[maxn]; struct node { int tag, Min, cnt; }t[maxn << 2];#define lson now << 1 #define rson now << 1 | 1 #define mid ( ( l + r ) >> 1 )void pushup( int now ) {if( t[lson].Min < t[rson].Min ) t[now].Min = t[lson].Min, t[now].cnt = t[lson].cnt;else if( t[lson].Min > t[rson].Min ) t[now].Min = t[rson].Min, t[now].cnt = t[rson].cnt;else t[now].Min = t[lson].Min, t[now].cnt = t[lson].cnt + t[rson].cnt; }void pushdown( int now ) {if( t[now].tag ) {t[lson].tag += t[now].tag;t[rson].tag += t[now].tag;t[lson].Min += t[now].tag;t[rson].Min += t[now].tag;t[now].tag = 0;return;} }void build( int now, int l, int r ) {if( l == r ) { t[now].Min = l, t[now].cnt = 1; return; }build( lson, l, mid );build( rson, mid + 1, r );pushup( now ); }void modify( int now, int l, int r, int L, int R, int k ) {if( R < l or r < L ) return;if( L <= l and r <= R ) { t[now].Min += k, t[now].tag += k; return; }pushdown( now );modify( lson, l, mid, L, R, k );modify( rson, mid + 1, r, L, R, k );pushup( now ); }int query( int now, int l, int r, int L, int R ) { if( R < l or r < L ) return 0;if( L <= l and r <= R ) return t[now].Min ? 0 : t[now].cnt;return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R ); }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) scanf( "%d %d", &x[i], &y[i] ), id[i] = i;sort( id + 1, id + n + 1, []( int u, int v ) { return x[u] < x[v]; } );build( 1, 1, n );long long ans = 0;for( int i = 1;i <= n;i ++ ) {modify( 1, 1, n, 1, n, -1 );modify( 1, 1, n, x[sMax[tMax]] + 1, i, y[id[i]] );modify( 1, 1, n, x[sMin[tMin]] + 1, i, -y[id[i]] );while( tMax and y[sMax[tMax]] < y[id[i]] ) {modify( 1, 1, n, x[sMax[tMax - 1]] + 1, x[sMax[tMax]], y[id[i]] - y[sMax[tMax]] );tMax --;}while( tMin and y[sMin[tMin]] > y[id[i]] ) {modify( 1, 1, n, x[sMin[tMin - 1]] + 1, x[sMin[tMin]], y[sMin[tMin]] - y[id[i]] );tMin --;}sMax[++ tMax] = sMin[++ tMin] = id[i];ans += query( 1, 1, n, 1, i );}printf( "%lld\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[CF 526 F] Pudding Monsters（单调栈 + 线段树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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