CF765F Souvenirs

• problem
• solution
• code

problem

題目鏈接

solution

這個勢能線段樹簡直是太巧妙了！！！( ??? )ﾉ

將詢問按右端點升序離線下來。

對于每一個右端點 $r$，維護 $an{s}_i=\min \{|a_i?a_j|,j\in [i,r]\}$。

用線段樹查詢區間 $[l,r]$ 內的 $\min \{an{s}_i,i\in [l,r]\}$ 就是答案了。

時間復雜度的瓶頸在于修改維護線段樹上面。暴力做是 $O(n^2)$ 的。

考慮優化。假設 $an{s}_i$ 的最優選擇點在 $j$。

• 如果 $a_r$ 是在黃色點，即 $<\frac{a_i+a_j}{2}$ ，這個時候要必須更新 $an{s}_i$。這會讓 $an{s}_i$ 的值變小至少一半。

• 如果 $a_r$ 是在藍色點，即 $>\frac{a_i+a_j}{2}$，這個時候直接更新 $an{s}_j$ 而不再更新 $an{s}_i$。

  因為 $j>i\wedge an{s}_j<an{s}_i$ ，最后 $r$ 的詢問肯定答案是不會選到 $an{s}_i$ 的。

  所以就算 $an{s}_i$ 是錯的，也不影響！

• 如果 $a_r$ 在 $a_i$ 等值線下面，也是一樣的。

將 $an{s}_i$ 看作勢能，遞減到 $0$ 時就不再更新。每次更新至少減少一半。

所以修改點數應該是 $n\log a$ 的。

具體而言：先修改右區間，再修改左區間。且如果當前修改的答案不如之前更新的答案，就直接跳過即可。同時需要存儲下區間內所有的 $a$。

這樣實際操作的只有必須更新的點。

總時間復雜度為：$O(n\log n\log a)$

code

#include <vector> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 400005 #define inf 0x7f7f7f7f vector < int > G[maxn]; struct node { int l, r, id; }q[maxn]; int n, Q; int a[maxn], ans[maxn];namespace SegMentTree {int ans = inf;int Min[maxn];#define lson now << 1#define rson now << 1 | 1void build( int now, int l, int r ) {Min[now] = inf;for( int i = l;i <= r;i ++ ) G[now].push_back( a[i] );sort( G[now].begin(), G[now].end() );if( l == r ) return;int mid = ( l + r ) >> 1;build( lson, l, mid );build( rson, mid + 1, r );}/*void modify( int now, int l, int r, int R, int x ) {if( R < l ) return;if( r <= R ) {auto it = lower_bound( G[now].begin(), G[now].end(), x );if( it != G[now].end() ) Min[now] = min( Min[now], (*it) - x );if( it != G[now].begin() ) Min[now] = min( Min[now], x - *(it - 1) );if( Min[now] >= ans ) return;}if( l == r ) { ans = min( ans, Min[now] ); return; }int mid = ( l + r ) >> 1;modify( rson, mid + 1, r, R, x ); //優先更新最近的點modify( lson, l, mid, R, x );Min[now] = min( Min[lson], Min[rson] );ans = min( ans, Min[now] );}*/void modify( int now, int l, int r, int R, int x ) {if( R < l ) return;if( r <= R ) {it = lower_bound( G[now].begin(), G[now].end(), x );int tmp = inf;if( it != G[now].end() ) tmp = *it - x;if( it != G[now].begin() ) it--, tmp = min( tmp, x - *it );Min[now] = min( Min[now], tmp );if( tmp >= ans ) return;}if( l == r ) { ans = min( ans, Min[now] ); return; }modify( rson, mid + 1, r, R, x );ans = min( ans, Min[rson] );modify( lson, l, mid, R, x );Min[now] = min( Min[lson], Min[rson] );ans = min( ans, Min[now] );}int query( int now, int l, int r, int L ) {if( r < L ) return inf;if( L <= l ) return Min[now];int mid = ( l + r ) >> 1;return min( query( lson, l, mid, L ), query( rson, mid + 1, r, L ) );}}int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) scanf( "%d", &a[i] );scanf( "%d", &Q );for( int i = 1;i <= Q;i ++ ) scanf( "%d %d", &q[i].l, &q[i].r ), q[i].id = i;SegMentTree :: build( 1, 1, n );sort( q + 1, q + Q + 1, []( node x, node y ) { return x.r < y.r; } );int ip = 1;while( q[ip].r <= 1 ) ip ++;for( int i = 2;i <= n;i ++ ) {SegMentTree :: ans = inf;SegMentTree :: modify( 1, 1, n, i - 1, a[i] );while( q[ip].r == i )ans[q[ip].id] = SegMentTree :: query( 1, 1, n, q[ip].l ), ip ++;}for( int i = 1;i <= Q;i ++ ) printf( "%d\n", ans[i] );return 0; }

Upd：感謝評論區的 $\text{hack}$ 數據讓我發現自己的代碼寫得有點問題。
和小同志研究了一天發現是代碼注釋部分的問題。
大概就是，當前 $i$ 插入時，按照分析應該是遇到更優秀 $j$ 就不再往左子樹找了。
這個更優秀是和以前存的答案比較。
但是之前代碼實現是和現在被覆蓋的答案比較。勢能就差得離譜。
現在新代碼在葉子節點時輸出訪問次數就大概是 $1$。

但是。。。呃呃呃呃，現在這份代碼加上讀優跑評論區的數據最快也要 $5s$。。。
我們討論了一下我這份代碼的寫法，更偏向 $n\log n^2\log V$ 的時間復雜度，因為要走 $\log n$ 層線段樹，每層內還有個 $\text{vector}$ 的二分。
可能把二分寫在外面能少個 $\text{log}$ 的嵌套。
但是跑評論區的數據每個點都只被訪問了一次，時間復雜度我就不是很懂了？。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF765F Souvenirs（势能线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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