柳州网站建设33,上海注册公司详细流程,长宁区公司网站建设,用腾讯云服务器做网站CF526F Pudding Monstersproblemsolutioncodeproblem
luogu翻译
solution
observation #xff1a;每行每列恰好有一个棋子#xff0c;所以如果一段区间 [l,r][l,r][l,r] 会被某个 kkk 统计#xff0c;当且仅当这个区间内棋子纵坐标 ymax−ymin1r−l1y_{max}-y_{min}1r-l…
CF526F Pudding Monstersproblemsolutioncodeproblem
luogu翻译
solution
observation 每行每列恰好有一个棋子所以如果一段区间 [l,r][l,r][l,r] 会被某个 kkk 统计当且仅当这个区间内棋子纵坐标 ymax−ymin1r−l1y_{max}-y_{min}1r-l1ymax−ymin1r−l1。
发现这是经典的连续段计数问题。
标配单调栈 线段树。
将所有棋子按照横坐标升序排序。
枚举右端点 rrr线段树上每个叶子节点 lll 维护的是 [l,r][l,r][l,r] 的信息。
转换一下条件判定ymax−yminl−r0y_{max}-y_{min}l-r0ymax−yminl−r0。
因为每行每列恰好一个棋子所以所有情况都有 ymax−ymin≥r−ly_{max}-y_{min}\ge r-lymax−ymin≥r−l。
而最后要计入答案的是取等的情况即最小值。
所以线段树就维护 ymax−yminl−ry_{max}-y_{min}l-rymax−yminl−r 的最小值以及最小值个数。
最后统计的时候就统计最小值为 000 的节点信息。 rrr 每次都是 111对应的是线段树整体 −1-1−1。 lll 与 rrr 无关在最开始建树是加上即可。 ymaxy_{max}ymax维护一个单增栈栈中第 toptoptop 个元素维护的是区间 [sMax[top−1]1,sMax[top]]\Big[sMax[top-1]1,sMax[top]\Big][sMax[top−1]1,sMax[top]] 的最大值信息即这一段的纵坐标最大值都是 sMax[top]sMax[top]sMax[top]。 每次用右端点 rrr 与栈比较纵坐标大小如果 rrr 大则弹栈将 toptoptop 维护的区间加上 yr−ysMax[top]y_r-y_{sMax[top]}yr−ysMax[top]。 yminy_{min}ymin维护一个单减栈栈中第 toptoptop 个元素维护的是区间 [sMin[top−1]1,sMin[top]]\Big[sMin[top-1]1,sMin[top]\Big][sMin[top−1]1,sMin[top]] 的最大值信息即这一段的纵坐标最小值都是 sMin[top]sMin[top]sMin[top]。 每次用右端点 rrr 与栈比较纵坐标大小如果 rrr 小则弹栈将 toptoptop 维护的区间加上 ysMin[top]−yiy_{sMin[top]-y_i}ysMin[top]−yi。
事件复杂度为 O(nlogn)O(n\log n)O(nlogn)。
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;
}
