文章目錄

• Chef and Churu
• • source
  • solution
  • code
• Chef and Problems
• • source
  • solution
  • code
• Children Trips
• • source
  • solution
  • code

Chef and Churu

source

solution

對于單獨的$i$，查詢可以用線段樹/樹狀數(shù)組$O(n\log n)$，這暗示可以平衡查詢修改次數(shù)

分塊

預處理$cn{t}_{i,j}:$ $A_j$對第$i$塊包含的函數(shù)貢獻次數(shù)

每次修改的時候，相當于$+val?A_{pos}$

枚舉塊，直接整體修改$cnt\times (val?A_{pos})$?

• 如果是$O(\log n)$修改值
• 查詢整塊直接調用$\sqrt{n}$
• 散塊區(qū)間查詢$\sqrt{n}\log n$
• 最后時間復雜度是$O(Q_1(\sqrt{n}+logn)+Q_2(\sqrt{n}+\sqrt{n}\log n))$
• 卡在查詢的$\sqrt{n}\log n$，非常難受

再分塊，$O(\sqrt{n})$ 修改，$O(1)$查詢

用tag記錄整塊的整體加標記，w記錄散塊暴力加

查詢的時候，找到$i$?的w值再加上所在塊的整體加tag

時間復雜度$O(Q_1(\sqrt{n}+\sqrt{n})+Q_2(\sqrt{n}+\sqrt{n}))=O(Q\sqrt{n})$?

code

#include <cmath> #include <cstdio> #include <iostream> using namespace std; #define int unsigned long long #define maxn 100005 #define maxB 320 int n, Q, B; int A[maxn], L[maxn], R[maxn], block[maxn], sum[maxB], w[maxn], tag[maxB]; int cnt[maxB][maxn];void modify( int pos, int val ) {for( int i = 1;i <= block[n];i ++ )sum[i] += cnt[i][pos] * ( val - A[pos] );for( int i = block[pos] + 1;i <= block[n];i ++ )tag[i] += val - A[pos];for( int i = pos;i <= min( n, B * block[pos] );i ++ )w[i] += val - A[pos];A[pos] = val; }int query( int i ) { return w[i] + tag[block[i]]; }int query( int l, int r ) {int ans = 0;if( block[l] == block[r] )for( int i = l;i <= r;i ++ )ans += query( R[i] ) - query( L[i] - 1 );else {for( int i = l;i <= B * block[l];i ++ )ans += query( R[i] ) - query( L[i] - 1 );for( int i = B * ( block[r] - 1 ) + 1;i <= r;i ++ )ans += query( R[i] ) - query( L[i] - 1 );for( int i = block[l] + 1;i < block[r];i ++ )ans += sum[i];}return ans; }signed main() {scanf( "%llu", &n );B = sqrt( n );for( int i = 1;i <= n;i ++ ) {scanf( "%llu", &A[i] ), w[i] = A[i];block[i] = ( i - 1 ) / B + 1;}for( int i = 1;i <= n;i ++ )scanf( "%llu %llu", &L[i], &R[i] );for( int i = 1;i <= n;i ++ )w[i] += w[i - 1];for( int i = 1;i <= block[n];i ++ ) {for( int j = ( i - 1 ) * B + 1;j <= min( n, i * B );j ++ )cnt[i][L[j]] ++, cnt[i][R[j] + 1] --;for( int j = 1;j <= n;j ++ )cnt[i][j] += cnt[i][j - 1];for( int j = 1;j <= n;j ++ )sum[i] += cnt[i][j] * A[j];}scanf( "%llu", &Q );int opt, x, y;while( Q -- ) {scanf( "%llu %llu %llu", &opt, &x, &y );if( opt & 1 ) modify( x, y );else printf( "%llu\n", query( x, y ) );}return 0; }

Chef and Problems

source

solution

分塊

預處理出整塊$i,j$之間的答案

具體而言，用$las{t}_i$記錄年齡為$i$的第一個人的出現(xiàn)位置，顯然越往后的人與第一個年齡相同的人距離越大

對于查詢，包含的整塊直接調用預處理的數(shù)組

散塊部分，就在區(qū)間中l(wèi)ower_bound找最遠的，把人按年齡分道不同容器vector找坐標

code

#include <cmath> #include <cstdio> #include <vector> #include <iostream> using namespace std; #define maxn 100005 #define maxB 1005 vector < int > pos[maxn]; int n, m, Q, B; int A[maxn], block[maxn], last[maxn]; int len[maxB][maxB];int main() {scanf( "%d %d %d", &n, &m, &Q );B = 100;for( int i = 1;i <= n;i ++ ) {scanf( "%d", &A[i] );block[i] = ( i - 1 ) / B + 1;}for( int i = 1;i <= block[n];i ++ ) {for( int j = 1;j <= m;j ++ ) last[j] = 0;int l = ( i - 1 ) * B + 1, ans = 0;for( int j = l;j <= n;j ++ ) {if( ! last[A[j]] ) last[A[j]] = j;else ans = max( ans, j - last[A[j]] );if( j % B == 0 ) len[i][block[j]] = ans; }}for( int i = 1;i <= n;i ++ ) pos[A[i]].push_back( i );while( Q -- ) {int l, r;scanf( "%d %d", &l, &r );int ans = len[block[l] + 1][block[r] - 1];for( int i = l;i <= min( r, block[l] * B );i ++ ) {int p = lower_bound( pos[A[i]].begin(), pos[A[i]].end(), r ) - pos[A[i]].begin() - 1;if( ! ~ p ) continue;else ans = max( ans, pos[A[i]][p] - i );}for( int i = max( l, ( block[r] - 1 ) * B + 1 );i <= r;i ++ ) {int p = lower_bound( pos[A[i]].begin(), pos[A[i]].end(), l ) - pos[A[i]].begin();if( p == pos[A[i]].size() ) continue;else ans = max( ans, i - pos[A[i]][p] );}printf( "%d\n", ans );}return 0; }

Children Trips

source

solution

先dfs確定每個點到根的距離$dis$以及深度$dep$

按$c$與$\sqrt{n}$的大小關系分塊

• $c>\sqrt{n}$

  對于$u,v$，找到其$lca$，暴力一次一次跳，一次最多跳$p$長度，最多跳$\sqrt{n}$次

  最后得到跳的次數(shù)以及距離$lca$的距離，兩個距離合在一起看是再跳一次還是兩次

• $c\le \sqrt{n}$

  這個時候就不能暴力跳了，因為可能會達到$n$級別

  但是$c$最多只有$\sqrt{n}$個取值

  將排序按$c$從小到大排序，預處理倍增數(shù)組$g_{i,j}:$ 點$i$跳$2^j$?次所達到的點

按理來說$O(n\sqrt{n}\log n)$有點尷尬，但這道題是八秒，交上去倒是挺快的，╮(╯▽╰)╭

code

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define Pair pair < int, int > #define maxn 100005 int n, m, B; vector < Pair > G[maxn]; int dis[maxn], dep[maxn], ans[maxn]; int f[maxn][20], g[maxn][20];void dfs( int u, int fa ) {f[u][0] = fa, dep[u] = dep[fa] + 1;for( int i = 1;i <= 16;i ++ )f[u][i] = f[f[u][i - 1]][i - 1];for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].first;int w = G[u][i].second;if( v == fa ) continue;else dis[v] = dis[u] + w, dfs( v, u );} }struct node {int u, v, p, id;node(){}node( int U, int V, int P, int ID ) { u = U, v = V, p = P, id = ID; } }block_little[maxn], block_large[maxn];int get_lca( int u, int v ) {if( dep[u] < dep[v] ) swap( u, v );for( int i = 16;~ i;i -- ) if( dep[f[u][i]] >= dep[v] ) u = f[u][i];if( u == v ) return u;for( int i = 16;~ i;i -- ) if( f[u][i] ^ f[v][i] ) u = f[u][i], v = f[v][i];return f[u][0]; }int jump_once( int u, int p ) {int t = u;for( int i = 16;~ i;i -- ) {if( dis[u] - dis[f[t][i]] > p ) continue;else t = f[t][i];}return t; }Pair climb_large( int u, int lca, int p ) {int cnt = 0;while( u ^ lca ) {int t = jump_once( u, p );if( dep[t] > dep[lca] ) cnt ++, u = t;else break;}return make_pair( cnt, dis[u] - dis[lca] ); }void solve_large( int n ) {for( int i = 1;i <= n;i ++ ) {int u = block_large[i].u;int v = block_large[i].v;int p = block_large[i].p;int id = block_large[i].id;int lca = get_lca( u, v );Pair l = climb_large( u, lca, p );Pair r = climb_large( v, lca, p );int len = l.second + r.second;ans[id] = l.first + r.first + ( int )ceil( len * 1.0 / p );} }Pair climb_little( int u, int lca, int p ) {int cnt = 0;for( int i = 16;~ i;i -- )if( dep[g[u][i]] > dep[lca] ) cnt += 1 << i, u = g[u][i];return make_pair( cnt, dis[u] - dis[lca] ); }void build( int p ) {for( int i = 1;i <= n;i ++ ) g[i][0] = jump_once( i, p );for( int j = 1;j <= 16;j ++ )for( int i = 1;i <= n;i ++ )g[i][j] = g[g[i][j - 1]][j - 1]; }void solve_little( int n ) {sort( block_little + 1, block_little + n + 1, []( node x, node y ) { return x.p < y.p; } );for( int i = 1;i <= n;i ++ ) {int u = block_little[i].u;int v = block_little[i].v;int p = block_little[i].p;int id = block_little[i].id;int lca = get_lca( u, v );if( p != block_little[i - 1].p ) build( p );Pair l = climb_little( u, lca, p );Pair r = climb_little( v, lca, p );int len = l.second + r.second;ans[id] = l.first + r.first + ( int )ceil( len * 1.0 / p );} }int main() {scanf( "%d", &n );for( int i = 1, u, v, w;i < n;i ++ ) {scanf( "%d %d %d", &u, &v, &w );G[u].push_back( make_pair( v, w ) );G[v].push_back( make_pair( u, w ) ); }dfs( 1, 0 );B = sqrt( n );scanf( "%d", &m );int little = 0, large = 0;for( int i = 1, u, v, p;i <= m;i ++ ) {scanf( "%d %d %d", &u, &v, &p );if( p <= B ) block_little[++ little] = node( u, v, p, i );else block_large[++ large] = node( u, v, p, i );}solve_large( large ); solve_little( little );for( int i = 1;i <= m;i ++ ) printf( "%d\n", ans[i] );return 0; }

總結

以上是生活随笔為你收集整理的一二三系列之CodeChef分块——Chef and Churu，Chef and Problems，Children Trips的全部內容，希望文章能夠幫你解決所遇到的問題。

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