佛山企业网站优化,深度网网站建设方案,自己做网站怎么加定位,成功企业网站必备要素problem
luogu-P5579
solution
此题关键在于发现一个结论#xff1a;生长速度快的草在任何时刻都不可能矮于生长速度慢的草。
正确性显然。
所以当我们将草按照 aaa 升序排序后#xff0c;每次收割的草一定是一个后缀。
那么这个后缀的起点就可以二分找到。
割完后要对…problem
luogu-P5579
solution
此题关键在于发现一个结论生长速度快的草在任何时刻都不可能矮于生长速度慢的草。
正确性显然。
所以当我们将草按照 aaa 升序排序后每次收割的草一定是一个后缀。
那么这个后缀的起点就可以二分找到。
割完后要对后缀所有草的高度全削成一样的且在下一次收割前要让所有草生长高度。
这可以用线段树解决。
找后缀起点就是线段树上二分。维护一段区间中最长的草的高度。
对草进行高度削减。就是对一段区间整体赋值操作。
两次收割间每个草都要生长。维护区间的草高度之和以及天数的标记。
这里的线段树实现要注意一个点就是懒标记的下放如果整体覆盖了那么之前存的天数标记也要清空。
也就是要注意懒标记的先后顺序问题。
我调了好久
时间复杂度 O(nlogn)O(n\log n)O(nlogn)。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 500005
const int inf 1e15;
int n, m;
int a[maxn];namespace SGT {struct node { int suma, tag, sum, Max, Maxa, tim; }t[maxn 2];#define lson now 1#define rson now 1 | 1#define mid (l r 1)void pushdown( int now, int l, int r ) {if( t[now].tag ^ inf ) {t[lson].Max t[lson].tag t[now].tag;t[lson].sum t[now].tag * (mid - l 1);t[rson].Max t[rson].tag t[now].tag;t[rson].sum t[now].tag * (r - mid);t[lson].tim t[rson].tim 0;t[now].tag inf;}if( t[now].tim ) {t[lson].sum t[lson].suma * t[now].tim;t[rson].sum t[rson].suma * t[now].tim;t[lson].Max t[lson].Maxa * t[now].tim;t[rson].Max t[rson].Maxa * t[now].tim;t[lson].tim t[now].tim;t[rson].tim t[now].tim;t[now].tim 0;}}void add( int d ) {pushdown( 1, 1, n );t[1].sum d * t[1].suma;t[1].Max d * t[1].Maxa;t[1].tim d;}void build( int now, int l, int r ) {t[now].tag inf; if( l r ) { t[now].suma a[l];t[now].Maxa a[l]; return; }build( lson, l, mid );build( rson, mid 1, r );t[now].suma t[lson].suma t[rson].suma;t[now].Maxa t[rson].Maxa;}void modify( int now, int l, int r, int L, int R, int x ) {if( R l or r L ) return;if( L l and r R ) { t[now].sum (r - l 1) * x; t[now].tag x;t[now].Max x;t[now].tim 0;return; }pushdown( now, l, r );modify( lson, l, mid, L, R, x );modify( rson, mid 1, r, L, R, x );t[now].sum t[lson].sum t[rson].sum;t[now].Max t[rson].Max;}int query( int now, int l, int r, int x ) {if( l r ) return l;pushdown( now, l, r );if( x t[lson].Max ) return query( lson, l, mid, x );else return query( rson, mid 1, r, x );}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].sum;pushdown( now, l, r );return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );}
}signed main() {scanf( %lld %lld, n, m );for( int i 1;i n;i ) scanf( %lld, a[i] );sort( a 1, a n 1 );SGT :: build( 1, 1, n );for( int i 1, lst 0, d, b;i m;i ) {scanf( %lld %lld, d, b );SGT :: add( d - lst ); lst d;if( SGT :: t[1].Max b ) { puts(0); continue; }int p SGT :: query( 1, 1, n, b );printf( %lld\n, SGT :: query( 1, 1, n, p, n ) - (n - p 1) * b );SGT :: modify( 1, 1, n, p, n, b );}return 0;
}
