网站建设swf播放器源码,南宁好的网站建设公司,阳光电子商务平台,网页制作和设计实验报告problem
洛谷链接
solution
在一个丝毫没有单调性的问题中很难想到将其转化为二分。
二分最后在第 ppp 位置上的值 xxx。
然后将所有 ≥x\ge x≥x 的赋为 111#xff0c;所有 xxx 的赋为 000。
经过一系列区间排序操作后#xff0c;最后我们只在乎第 ppp 位…problem
洛谷链接
solution
在一个丝毫没有单调性的问题中很难想到将其转化为二分。
二分最后在第 ppp 位置上的值 xxx。
然后将所有 ≥x\ge x≥x 的赋为 111所有 xxx 的赋为 000。
经过一系列区间排序操作后最后我们只在乎第 ppp 位置上的数是否是 111。
如果是说明答案可能会更大先记录下来如果不是说明答案一定更小。
迷迷糊糊间咦~真的具有单调性。
那么一段区间的排序就是将 111 凑在一起。
如果是升序将所有 111 放在区间末尾降序就放在区间开头。
这种区间整体的操作我们可以用线段树来做区间 111 个数查询区间整体赋值。
code
#include bits/stdc.h
using namespace std;
#define maxn 100005
int n, m, q;
int p[maxn];
struct node { int op, l, r; }Q[maxn];namespace sgt {#define lson now 1#define rson now 1 | 1#define mid (l r 1)int sum[maxn 2], tag[maxn 2];void pushdown( int now, int l, int r ) {if( tag[now] 0 ) {tag[lson] sum[lson] 0;tag[rson] sum[rson] 0;}if( tag[now] 1 ) {tag[lson] tag[rson] 1;sum[lson] mid - l 1;sum[rson] r - mid;}tag[now] -1;}void modify( int L, int R, int x, int now 1, int l 1, int r n ) {if( R l or r L or L R ) return;if( L l and r R ) {tag[now] x;sum[now] ( r - l 1 ) * x;return;}pushdown( now, l, r );modify( L, R, x, lson, l, mid ), modify( L, R, x, rson, mid 1, r );sum[now] sum[lson] sum[rson];}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 sum[now];pushdown( now, l, r );return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );}void build( int x, int now 1, int l 1, int r n ) {tag[now] -1;if( l r ) { sum[now] p[l] x; return; }build( x, lson, l, mid ), build( x, rson, mid 1, r );sum[now] sum[lson] sum[rson];}int query( int now, int l, int r ) {if( l r ) return sum[now];pushdown( now, l, r );if( q mid ) return query( lson, l, mid );else return query( rson, mid 1, r );}};bool check( int x ) {sgt :: build( x );for( int i 1;i m;i ) {int cnt sgt :: query( 1, 1, n, Q[i].l, Q[i].r );sgt :: modify( Q[i].l, Q[i].r, 0 );if( ! Q[i].op ) sgt :: modify( Q[i].r - cnt 1, Q[i].r, 1 );else sgt :: modify( Q[i].l, Q[i].l cnt - 1, 1 );}return sgt :: query( 1, 1, n );
}int main() {scanf( %d %d, n, m );for( int i 1;i n;i ) scanf( %d, p[i] );for( int i 1;i m;i ) scanf( %d %d %d, Q[i].op, Q[i].l, Q[i].r );scanf( %d, q );int l 1, r n, ans;while( l r ) {if( check( mid ) ) ans mid, l mid 1;else r mid - 1;}printf( %d\n, ans );return 0;
}
