文章目錄

• SP2940 UNTITLE1 - Untitled Problem II
• • source
  • solution
  • code
• Balanced Lineup
• • source
  • code
• Count on a tree II
• [ioi2009]Regions

SP2940 UNTITLE1 - Untitled Problem II

source

solution

分塊
$$s_i=\{\begin{array}{llc}{s}_i+k\times (i?l+1)=s_i+k\times i+k\times (1?l)& & l\le i\le r\\ s_i+k\times (r?l+1)& & r<i\end{array}$$
對(duì)于整塊而言$k\times (1?l)$和$k\times (r?l+1)$都可以看作常數(shù)，用區(qū)間標(biāo)記tag記錄，再單獨(dú)記錄一下k
$$ans=\max \{s_i+k_{bloc{k}_i}\times i+ta{g}_{bloc{k}_i}\}l\le i\le r$$
對(duì)于$l,r$在的散塊，暴力下放標(biāo)記到塊區(qū)間內(nèi)，然后暴力查詢

對(duì)于整塊，發(fā)現(xiàn)max的方程類似$dp$?斜率優(yōu)化轉(zhuǎn)移，維護(hù)塊內(nèi)的上凸殼，二分求解

• 假設(shè)塊內(nèi)$i<j$，且$an{s}_i<an{s}_j$

  • $$an{s}_i=s_i+k_{bloc{k}_p}i+ta{g}_{bloc{k}_p}$$

  • $$an{s}_j=s_j+k_{bloc{k}_p}j+ta{g}_{bloc{k}_p}$$

• $$\begin{gathered} an{s}_i<an{s}_j?s_i+k_{bloc{k}_p}i<s_j+k_{bloc{k}_p}j?s_i?s_j<k_{bloc{k}_p}(j?i) \\ ?\frac{s_j?s_i}{j?i}>?k_{bloc{k}_p} \end{gathered}$$

code

#include <cmath> #include <cstdio> #include <iostream> using namespace std; #define int long long #define maxn 50005 #define maxB 255 int n, B; int s[maxn], block[maxn];struct node {int l, r, tag, k, top;struct point {int x, y;point(){}point( int X, int Y ) { x = X, y = Y; }friend double slope( point s, point t ) { return 1.0 * ( s.y - t.y ) / ( s.x - t.x ); }}sta[maxB];void build_hall() {top = k = tag = 0;for( int i = l;i <= r;i ++ ) {point now( i, s[i] );while( top > 1 && slope( sta[top], now ) >= slope( sta[top - 1], now ) ) top --;sta[++ top] = now;}sta[top + 1] = point( r + 1, -1e18 );}int calc() {int l = 1, r = top, pos = 0;while( l <= r ) {int mid = ( l + r ) >> 1;if( slope( sta[mid + 1], sta[mid] ) > -k ) l = mid + 1;else r = mid - 1, pos = mid;}return tag + sta[pos].x * k + sta[pos].y;}void init( int L, int R ) { l = L, r = R, build_hall(); }void pushdown() { for( int i = l;i <= r;i ++ ) s[i] += tag + k * i; }}t[maxB];void modify( int l, int r, int k ) {for( int i = block[r] + 1;i <= block[n];i ++ )t[i].tag += ( r - l + 1 ) * k;if( block[l] == block[r] ) {t[block[l]].pushdown();for( int i = l;i <= r;i ++ )s[i] += ( i - l + 1 ) * k;for( int i = r + 1;i <= t[block[l]].r;i ++ )s[i] += ( r - l + 1 ) * k;t[block[l]].build_hall();}else {for( int i = block[l] + 1;i < block[r];i ++ ) t[i].k += k, t[i].tag -= ( l - 1 ) * k;t[block[l]].pushdown();t[block[r]].pushdown();for( int i = l;i <= t[block[l]].r;i ++ )s[i] += ( i - l + 1 ) * k;for( int i = t[block[r]].l;i < r;i ++ )s[i] += ( i - l + 1 ) * k;for( int i = r;i <= t[block[r]].r;i ++ ) s[i] += ( r - l + 1 ) * k;t[block[l]].build_hall();t[block[r]].build_hall();} }int query( int l, int r ) {int ans = -1e18;if( block[l] == block[r] ) {t[block[l]].pushdown();for( int i = l;i <= r;i ++ )ans = max( ans, s[i] );t[block[l]].build_hall();}else {t[block[l]].pushdown();t[block[r]].pushdown();for( int i = l;i <= t[block[l]].r;i ++ ) ans = max( ans, s[i] );for( int i = t[block[r]].l;i <= r;i ++ ) ans = max( ans, s[i] );for( int i = block[l] + 1;i < block[r];i ++ ) ans = max( ans, t[i].calc() );t[block[l]].build_hall();t[block[r]].build_hall();}return ans; }signed main() {scanf( "%lld", &n );B = sqrt( n );for( int i = 1;i <= n;i ++ ) {scanf( "%lld", &s[i] );s[i] += s[i - 1];block[i] = ( i - 1 ) / B + 1;}for( int i = 1;i <= block[n];i ++ )t[i].init( B * ( i - 1 ) + 1, min( n, B * i ) );int Q, opt, x, y, k;scanf( "%lld", &Q );while( Q -- ) {scanf( "%lld %lld %lld", &opt, &x, &y );if( opt ) printf( "%lld\n", query( x, y ) );else scanf( "%lld", &k ), modify( x, y, k );}return 0; }

Balanced Lineup

source

code

#include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; #define inf 0x3f3f3f3f #define maxn 50005 #define maxB 250 int n, Q, B; int block[maxn], h[maxn], Max[maxB], Min[maxB];void solve( int l, int r ) {int maxx = -inf, minn = inf;for( int i = l;i <= min( block[l] * B, r );i ++ )maxx = max( maxx, h[i] ), minn = min( minn, h[i] );for( int i = block[l] + 1;i < block[r];i ++ )maxx = max( maxx, Max[i] ), minn = min( minn, Min[i] );for( int i = max( l, ( block[r] - 1 ) * B + 1 );i <= r;i ++ )maxx = max( maxx, h[i] ), minn = min( minn, h[i] );printf( "%d\n", maxx - minn ); }int main() {scanf( "%d %d", &n, &Q );B = sqrt( n );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &h[i] );block[i] = ( i - 1 ) / B + 1;}memset( Min, 0x3f, sizeof( Min ) );for( int i = 1;i <= n;i ++ ) {Max[block[i]] = max( Max[block[i]], h[i] );Min[block[i]] = min( Min[block[i]], h[i] );}while( Q -- ) {int l, r;scanf( "%d %d", &l, &r );solve( l, r );}return 0; }

Count on a tree II

已經(jīng)合并到莫隊(duì)算法里面去了

[ioi2009]Regions

source
將詢問按顏色出現(xiàn)次數(shù)分塊

小于等于$\sqrt{n}$的就掛在$e2$上，統(tǒng)計(jì)從根到該點(diǎn)顏色的出現(xiàn)次數(shù)

大于$\sqrt{n}$的就掛在$e1$上，統(tǒng)計(jì)該點(diǎn)子樹內(nèi)顏色的出現(xiàn)次數(shù)

復(fù)雜度就是$n\sqrt{n}$

#include <map> #include <cmath> #include <cstdio> #include <vector> #include <cstring> using namespace std; #define maxn 200005 #define maxR 25005 struct node {int x, y;node(){}node( int X, int Y ) { x = X, y = Y; }bool operator < ( node t ) const {return x == t.x ? y < t.y : x < t.x;}bool operator == ( node t ) {return x == t.x && y == t.y;} }MS[maxn]; map < node, int > mp; vector < int > G[maxn], f[maxR], g[maxR]; int n, R, Q, block; int r[maxn], cnt[maxR], ans[maxn], id[maxn];void dfs1( int u ) {cnt[r[u]] ++;for( auto v : g[r[u]] ) ans[v] += cnt[MS[v].x];for( auto v : G[u] ) dfs1( v );cnt[r[u]] --; }void dfs2( int u ) { for( auto v : f[r[u]] ) ans[v] -= cnt[MS[v].y];cnt[r[u]] ++;for( auto v : G[u] ) dfs2( v );for( auto v : f[r[u]] ) ans[v] += cnt[MS[v].y]; }int main() {scanf( "%d %d %d %d", &n, &R, &Q, &r[1] );for( int i = 2, x;i <= n;i ++ ) {scanf( "%d %d", &x, &r[i] );G[x].push_back( i );}for( int i = 1;i <= n;i ++ )cnt[r[i]] ++;block = sqrt( n );for( int i = 1, x, y;i <= Q;i ++ ) {scanf( "%d %d", &x, &y );MS[i] = node( x, y );if( mp.count( node( x, y ) ) ) id[i] = mp[node( x, y )];else {id[i] = mp[node( x, y )] = i;if( cnt[y] <= block ) g[y].push_back( i );else f[x].push_back( i );}}memset( cnt, 0, sizeof( cnt ) );dfs1( 1 );dfs2( 1 );for( int i = 1;i <= Q;i ++ )printf( "%d\n", ans[id[i]] );return 0; }

總結(jié)

以上是生活随笔為你收集整理的专题突破一之分块——Untitled Problem II，Balanced Lineup，[ioi2009]Regions的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。