值域线段树+势能线段树+扫描线

• KiKi's K-Number
• ball
• The Child and Sequence
• 「雅礼集训 2017 Day1」市场
• Atlantis

KiKi’s K-Number

HDU-2852

权值线段树维护插入删除很简单

对于查询大于$x$的第$k$个，可以不用二分，转化一下

先查小于等于$x$的个数$cnt$，然后查排名为第$cnt+k$个值

#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

虚假的三维偏序

• 以$B$离散化后作权值线段树下标
• 按$I$降序排列，相同的按$R$升序排列
• 查$B_i$后面$[x+1,N]$的$R$最大值，如果最大值大于$R_i$，那么$i$就会出局
  • 首先$B_i$后面，满足$B_i<B^{\prime }$
  • 其次按照$I$排序，天然满足$I_i<I^{\prime }$
  • 最后最大值$R_i<R^{\prime }$
• 将$R_i$插到$B_i$对应下标上$[1,x]$，维护区间$R$最大值

#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$次后取模就对其没有意义了

考虑维护区间最大值，如果最大值都比取模的数小，那么这个区间就没有操作的意义

否则就暴力往下取模

#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

对于下取整的维护，考虑$\Delta =\mathrm{m}\mathrm{a}\mathrm{x}-\lfloor \frac{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{x}}{\mathrm{k}}\rfloor =\mathrm{m}\mathrm{i}\mathrm{n}-\lfloor \frac{\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{n}}{\mathrm{k}}\rfloor$

则整个区间的每个数都会$-\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

线段树维护扫描线的模板题

离散化$x$坐标，矩阵左右成为线段树区间，遇到矩阵的下面一条线$+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; }

总结

以上是生活随笔为你收集整理的数据结构二之线段树Ⅱ——KiKi‘s K-Number，ball，The Child and Sequence，「雅礼集训 2017 Day1」市场，Atlantis的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。