problem

luogu-P8251

solution

按照題意模擬單調(diào)棧。

求出對于 $i$ 而言，當(dāng)時(shí)單調(diào)棧的棧頂元素記為 $p_i$。

如果到 $i$ 時(shí)，棧頂已經(jīng)為 $p_i$ 了，意味著這中間的所有元素要么是被 $i$ 彈出，要么就是被 $i$ 前面的某些元素彈出，這些元素又被 $i$ 彈出。

總而言之，會(huì)發(fā)現(xiàn)當(dāng)詢問的 $p_i<l$ 時(shí) $i$ 所代表的二元組就是成功的。

于是我們只需要求 $[l,r]$ 內(nèi)有多少個(gè) $i\in [l,r]s.t.p_i<l$。

寫個(gè)主席樹，或者差分一下轉(zhuǎn)化成樹狀數(shù)組二維數(shù)點(diǎn)都行。

code

#include <bits/stdc++.h> using namespace std; #define maxn 500005 struct node { int x, p, k, id; }q[maxn << 1]; int n, Q; int a[maxn], b[maxn], p[maxn], t[maxn], ans[maxn]; stack < int > s;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();} }void print( int x ) {if( x > 9 ) print( x / 10 );putchar( x % 10 + '0' ); }namespace BIT {void add( int x ) { x ++; for(;x <= n;x += x & -x) t[x] ++; }int ask( int x ) { x ++; int cnt = 0; for(x;x;x -= x & -x) cnt += t[x]; return cnt; } }int main() {read( n ), read( Q );for( int i = 1;i <= n;i ++ ) read( a[i] );for( int i = 1;i <= n;i ++ ) read( b[i] );for( int i = 1;i <= n;i ++ ) {while( ! s.empty() and (a[s.top()] == a[i] or b[i] >= b[s.top()]) ) s.pop();if( ! s.empty() ) p[i] = s.top();s.push( i );}for( int i = 1, l, r;i <= Q;i ++ ) {read( l ), read( r );q[i] = (node){ l - 1, l - 1, -1, i };q[i + Q] = (node){ r, l - 1, 1, i };}sort( q + 1, q + (Q << 1 | 1), [](node a, node b){ return a.x < b.x; } );int j = 1; while( ! q[j].x ) j ++;for( int i = 1;i <= n;i ++ ) {BIT :: add( p[i] );for( ;q[j].x == i and j <= (Q << 1);j ++ ) ans[q[j].id] += q[j].k * BIT :: ask( q[j].p );}for( int i = 1;i <= Q;i ++ ) print( ans[i] ), putchar( '\n' );return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[NOI Online 2022 提高组] 丹钓战（单调栈 + 树状数组 / 主席树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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