zencart网站建设,适合新手做网站的,建设部资质查询网站,沈阳网站建设技术支持problem
luogu-P8251
solution
按照题意模拟单调栈。
求出对于 iii 而言#xff0c;当时单调栈的栈顶元素记为 pip_ipi。
如果到 iii 时#xff0c;栈顶已经为 pip_ipi 了#xff0c;意味着这中间的所有元素要么是被 iii 弹出#xff0c;要么就是被 iii 前面的某些…problem
luogu-P8251
solution
按照题意模拟单调栈。
求出对于 iii 而言当时单调栈的栈顶元素记为 pip_ipi。
如果到 iii 时栈顶已经为 pip_ipi 了意味着这中间的所有元素要么是被 iii 弹出要么就是被 iii 前面的某些元素弹出这些元素又被 iii 弹出。
总而言之会发现当询问的 pilp_ilpil 时 iii 所代表的二元组就是成功的。
于是我们只需要求 [l,r][l,r][l,r] 内有多少个 i∈[l,r]s.t.pili\in[l,r]\ s.t.\ p_ili∈[l,r] s.t. pil。
写个主席树或者差分一下转化成树状数组二维数点都行。
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;
}
