建设一个很大的视频网站需要多少钱,西安信息网站建设,网站标题字数,青岛定制网站设计公司值域线段树势能线段树扫描线KiKis K-NumberballThe Child and Sequence「雅礼集训 2017 Day1」市场AtlantisKiKi’s K-Number
HDU-2852
权值线段树维护插入删除很简单
对于查询大于xxx的第kkk个#xff0c;可以不用二分#xff0c;转化一下
先查小于等于xxx的个数cntcntc…
值域线段树势能线段树扫描线KiKis K-NumberballThe Child and Sequence「雅礼集训 2017 Day1」市场AtlantisKiKi’s K-Number
HDU-2852
权值线段树维护插入删除很简单
对于查询大于xxx的第kkk个可以不用二分转化一下
先查小于等于xxx的个数cntcntcnt然后查排名为第cntkcntkcntk个值
#include cstdio
#define maxn 100000
#define lson num 1
#define rson num 1 | 1
struct node {int sum, cnt;
}t[maxn 2 | 1];void build( int num, int l, int r ) {t[num].sum t[num].cnt 0;if( l r ) return;int mid l r 1;build( lson, l, mid );build( rson, mid 1, r );
}void modify( int num, int l, int r, int pos, int v ) {if( l r ) { t[num].cnt v, t[num].sum v; return; }int mid l r 1;if( pos mid ) modify( lson, l, mid, pos, v );else modify( rson, mid 1, r, pos, v );t[num].sum t[lson].sum t[rson].sum;
}int query_cnt( int num, int l, int r, int pos ) {if( l r ) return t[num].cnt;int mid l r 1;if( pos mid ) return query_cnt( lson, l, mid, pos );else return query_cnt( rson, mid 1, r, pos );
}int query( int num, int l, int r, int k ) {if( l r ) return l;int mid l r 1;if( k t[lson].sum ) return query( lson, l, mid, k );else return query( rson, mid 1, r, k - t[lson].sum );
}int query( int num, int l, int r, int L, int R ) {if( R l || r L ) return 0;if( L l r R ) return t[num].sum;int mid l r 1;return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );
}int main() {int n, opt, x, k, cnt, ans;while( ~ scanf( %d, n ) ) {build( 1, 1, maxn );while( n -- ) {scanf( %d %d, opt, x );switch( opt ) {case 0 : { modify( 1, 1, maxn, x, 1 ); break; }case 1 : {if( ! query_cnt( 1, 1, maxn, x ) ) printf( No Elment!\n );else modify( 1, 1, maxn, x, -1 );break;}case 2 : {scanf( %d, k );cnt query( 1, 1, maxn, 1, x );ans query( 1, 1, maxn, cnt k );if( ans maxn ) printf( Not Find!\n );else printf( %d\n, ans );break;}}}}return 0;
} ball
CF-12D
虚假的三维偏序
以BBB离散化后作权值线段树下标按III降序排列相同的按RRR升序排列查BiB_iBi后面[x1,N][x1,N][x1,N]的RRR最大值如果最大值大于RiR_iRi那么iii就会出局 首先BiB_iBi后面满足BiB′B_iBBiB′其次按照III排序天然满足IiI′I_iIIiI′最后最大值RiR′R_iRRiR′ 将RiR_iRi插到BiB_iBi对应下标上[1,x][1,x][1,x]维护区间RRR最大值
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define maxn 500005
#define lson num 1
#define rson num 1 | 1
struct node {int B, I, R;
}p[maxn];
int n, m, ans;
int x[maxn], t[maxn 2], tag[maxn 2];void pushdown( int num ) {t[lson] max( t[lson], tag[num] ) ;t[rson] max( t[rson], tag[num] ) ;tag[lson] max( tag[lson], tag[num] );tag[rson] max( tag[rson], tag[num] );tag[num] 0;
}void modify( int num, int l, int r, int L, int R, int val ) {if( R l or r L ) return;if( L l and r R ) {t[num] max( t[num], val );tag[num] max( tag[num], val );return;}pushdown( num );int mid l r 1;modify( lson, l, mid, L, R, val );modify( rson, mid 1, r, L, R, val );
}int query( int num, int l, int r, int pos ) {if( l r ) return t[num];pushdown( num );int mid l r 1;if( pos mid ) return query( lson, l, mid, pos );else return query( rson, mid 1, r, pos );
}int main() {scanf( %d, n );for( int i 1;i n;i ) scanf( %d, p[i].B );for( int i 1;i n;i ) scanf( %d, p[i].I );for( int i 1;i n;i ) scanf( %d, p[i].R );for( int i 1;i n;i ) x[i] p[i].B;sort( x 1, x n 1 );m unique( x 1, x n 1 ) - x - 1;for( int i 1;i n;i ) p[i].B lower_bound( x 1, x m 1, p[i].B ) - x;sort( p 1, p n 1, []( node x, node y ) { return x.I y.I ? x.R y.R : x.I y.I; } );for( int i 1;i n;i ) {if( query( 1, 1, m, p[i].B ) p[i].R ) ans ;modify( 1, 1, m, 1, p[i].B - 1, p[i].R );}printf( %d\n, ans );return 0;
}The Child and Sequence
CF-438D
区间求和很好维护
至于取模操作由辗转相除法可知取模后结果不超过原数的一半
所以最多log\loglog次后取模就对其没有意义了
考虑维护区间最大值如果最大值都比取模的数小那么这个区间就没有操作的意义
否则就暴力往下取模
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 100005
#define lson num 1
#define rson num 1 | 1
struct node {int sum, Max;
}t[maxn 2];
int a[maxn];void build( int num, int l, int r ) {if( l r ) { t[num].sum t[num].Max a[l]; return; }int mid l r 1;build( lson, l, mid );build( rson, mid 1, r );t[num].Max max( t[lson].Max, t[rson].Max );t[num].sum t[lson].sum t[rson].sum;
}int query( int num, int l, int r, int L, int R ) {if( R l or r L ) return 0;if( L l and r R ) return t[num].sum;int mid l r 1;return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );
}void modify( int num, int l, int r, int L, int R, int v ) {if( t[num].Max v or R l or r L ) return;if( l r ) { t[num].Max t[num].sum t[num].Max % v; return; }int mid l r 1;modify( lson, l, mid, L, R, v );modify( rson, mid 1, r, L, R, v );t[num].Max max( t[lson].Max, t[rson].Max );t[num].sum t[lson].sum t[rson].sum;
}void modify( int num, int l, int r, int pos, int val ) {if( l r ) { t[num].Max t[num].sum val; return; }int mid l r 1;if( pos mid ) modify( lson, l, mid, pos, val );else modify( rson, mid 1, r, pos, val );t[num].Max max( t[lson].Max, t[rson].Max );t[num].sum t[lson].sum t[rson].sum;
}signed main() {int n, m, opt, l, r, x, k;scanf( %lld %lld, n, m );for( int i 1;i n;i ) scanf( %lld, a[i] ); build( 1, 1, n );while( m -- ) {scanf( %lld, opt );switch ( opt ) {case 1 : {scanf( %lld %lld, l, r );printf( %lld\n, query( 1, 1, n, l, r ) );break;}case 2 : {scanf( %lld %lld %lld, l, r, x );modify( 1, 1, n, l, r, x );break;}case 3 : {scanf( %lld %lld, x, k );modify( 1, 1, n, x, k );break;}}}return 0;
}「雅礼集训 2017 Day1」市场
LOJ#6029
对于下取整的维护考虑Δmax−⌊maxxk⌋min−⌊minnk⌋\Delta\rm max-\lfloor\frac{maxx}{k}\rfloormin-\lfloor\frac{minn}{k}\rfloorΔmax−⌊kmaxx⌋min−⌊kminn⌋
则整个区间的每个数都会−Δ-\Delta−Δ可以用区间加标记记录
否则就仍然暴力往下除
利用势能分析足以通过
推荐好妹妹的本题势能分析题解戳我哦(づ3)づ╭❤
#include cmath
#include cstdio
#include iostream
using namespace std;
#define inf 1e18
#define maxn 100005
#define int long long
#define lson num 1
#define rson num 1 | 1
struct node {int sum, Min, Max, tag;
}t[maxn 2];
int a[maxn];void pushdown( int num, int l, int r ) {if( ! t[num].tag ) return;int mid l r 1;t[lson].Max t[num].tag;t[lson].Min t[num].tag;t[lson].tag t[num].tag;t[lson].sum t[num].tag * ( mid - l 1 );t[rson].Max t[num].tag;t[rson].Min t[num].tag;t[rson].tag t[num].tag;t[rson].sum t[num].tag * ( r - mid );t[num].tag 0;
}void pushup( int num ) {t[num].Min min( t[lson].Min, t[rson].Min );t[num].Max max( t[lson].Max, t[rson].Max );t[num].sum t[lson].sum t[rson].sum;
}void modify1( int num, int l, int r, int L, int R, int v ) {if( R l or r L ) return;if( L l and r R ) {t[num].Min v;t[num].Max v;t[num].tag v;t[num].sum v * ( r - l 1 );return;}pushdown( num, l, r );int mid l r 1;modify1( lson, l, mid, L, R, v );modify1( rson, mid 1, r, L, R, v );pushup( num );
}void modify2( int num, int l, int r, int L, int R, int v ) {if( r L or R l ) return;if( L l and r R ) {int maxx ( int )floor( t[num].Max * 1.0 / v );int minn ( int )floor( t[num].Min * 1.0 / v );if( t[num].Max - maxx t[num].Min - minn ) {int x t[num].Max - maxx;t[num].tag - x;t[num].Max maxx;t[num].Min minn;t[num].sum - ( r - l 1 ) * x;return;}}pushdown( num, l, r );int mid l r 1;modify2( lson, l, mid, L, R, v );modify2( rson, mid 1, r, L, R, v );pushup( num );
}pair int, int query( int num, int l, int r, int L, int R ) {if( r L or R l ) return make_pair( inf, 0 );if( L l and r R ) return make_pair( t[num].Min, t[num].sum );pushdown( num, l, r );int mid l r 1;pair int, int ans1 query( lson, l, mid, L, R );pair int, int ans2 query( rson, mid 1, r, L, R );return make_pair( min( ans1.first, ans2.first ), ans1.second ans2.second );
}void build( int num, int l, int r ) {if( l r ) { t[num].Max t[num].Min t[num].sum a[l], t[num].tag 0; return; }int mid l r 1;build( lson, l, mid );build( rson, mid 1, r );pushup( num );
}signed main() {int n, Q, opt, l, r, x;scanf( %lld %lld, n, Q );for( int i 1;i n;i ) scanf( %lld, a[i] );build( 1, 1, n );while( Q -- ) {scanf( %lld %lld %lld, opt, l, r );l , r ;switch ( opt ) {case 1 : { scanf( %lld, x ); modify1( 1, 1, n, l, r, x ); break; }case 2 : { scanf( %lld, x ); modify2( 1, 1, n, l, r, x ); break; }case 3 : { printf( %lld\n, query( 1, 1, n, l, r ).first ); break; }case 4 : { printf( %lld\n, query( 1, 1, n, l, r ).second ); break; }}}return 0;
}Atlantis
HDU-1542
线段树维护扫描线的模板题
离散化xxx坐标矩阵左右成为线段树区间遇到矩阵的下面一条线111上面一条线−1-1−1
扫描线是维护线段可以看做是维护边信息放在两点间平常线段树是维护点信息发在单点上
所以写法会有边界的丢丢不同
#include cstdio
#include cstring
#include algorithm
using namespace std;
#define maxn 205
#define lson num 1
#define rson num 1 | 1
struct node {double l, r, h; int op;node(){}node( double L, double R, double H, int Op ) {l L, r R, h H, op Op;}
}g[maxn];
double x[maxn], t[maxn 2];
int tag[maxn 2];bool cmp( node u, node v ) { return u.h v.h; }void pushup( int num, int l, int r ) {if( tag[num] ) t[num] x[r] - x[l];else if( l 1 r ) t[num] 0;else t[num] t[lson] t[rson];
}void modify( int num, int l, int r, int L, int R, int val ) {if( R l or r L ) return;if( L l and r R ) {tag[num] val;pushup( num, l, r );return;}int mid l r 1;modify( lson, l, mid, L, R, val );modify( rson, mid, r, L, R, val );pushup( num, l, r );
}int main() {int T 0, n; double x1, y1, x2, y2;while( scanf( %d, n ) and n ) {for( int i 1;i n;i ) {scanf( %lf %lf %lf %lf, x1, y1, x2, y2 );x[i] x1, x[i n] x2;g[i] node( x1, x2, y1, 1 );g[i n] node( x1, x2, y2, -1 );}n 1;sort( x 1, x n 1 );sort( g 1, g n 1, cmp );int m unique( x 1, x n 1 ) - x - 1;memset( t, 0, sizeof( t ) );memset( tag, 0, sizeof( tag ) );double ans 0;for( int i 1;i n;i ) {int l lower_bound( x 1, x m 1, g[i].l ) - x;int r lower_bound( x 1, x m 1, g[i].r ) - x;modify( 1, 1, m, l, r, g[i].op );ans t[1] * ( g[i 1].h - g[i].h );}printf( Test case #%d\nTotal explored area: %.2f\n\n, T, ans );}return 0;
}
