文章目錄

• [JSOI2008]火星人prefix
• Strange Queries

[JSOI2008]火星人prefix

BZOJ1014
思路很好想，哈希字符串即可

只是平衡樹的碼量大

注意因為splay加入哨兵的原因，每個點在平衡樹內的排名比真實排名大$1$（有極小值的占位）

考慮的時候就只在詢問的時候考慮，修改的時候忘了就掛了

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define maxn 100005 #define ull unsigned long long struct node {int son[2], f, val, siz;ull hash; }t[maxn]; int root, n, Q; ull mi[maxn]; int val[maxn]; char s[maxn];void read( int &x ) {x = 0; char c = getchar();while( c < '0' or c > '9' ) c = getchar();while( '0' <= c and c <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ( c ^ 48 ); c = getchar(); } }void pushup( int x ) {if( ! x ) return;t[x].siz = 1;if( t[x].son[0] ) t[x].siz += t[t[x].son[0]].siz;if( t[x].son[1] ) t[x].siz += t[t[x].son[1]].siz;t[x].hash = mi[t[t[x].son[0]].siz] * t[x].val + t[t[x].son[0]].hash + t[t[x].son[1]].hash * mi[t[t[x].son[0]].siz + 1]; }void rotate( int x ) {int fa = t[x].f;int Gfa = t[fa].f;int k = t[fa].son[1] == x;t[Gfa].son[t[Gfa].son[1] == fa] = x;t[x].f = Gfa;t[fa].son[k] = t[x].son[k ^ 1];if( t[x].son[k ^ 1] ) t[t[x].son[k ^ 1]].f = fa;t[x].son[k ^ 1] = fa;t[fa].f = x;pushup( fa );pushup( x ); }void splay( int x, int goal ) {while( t[x].f ^ goal ) {int fa = t[x].f, Gfa = t[fa].f;if( Gfa ^ goal ) ( t[Gfa].son[0] == fa ) ^ ( t[fa].son[0] == x ) ? rotate( x ) : rotate( fa );rotate( x );}if( ! goal ) root = x; }int build( int now, int l, int r ) {if( l > r ) return 0;int mid = ( l + r ) >> 1;t[mid].hash = val[mid];t[mid].val = val[mid];t[mid].siz = 1;t[mid].f = now;if( l == r ) return l;t[mid].son[0] = build( mid, l, mid - 1 );t[mid].son[1] = build( mid, mid + 1, r );pushup( mid );return mid; }int find( int x ) {int now = root;while( 1 ) {if( t[t[now].son[0]].siz >= x ) now = t[now].son[0];else if( t[t[now].son[0]].siz + 1 == x ) return now;else x -= t[t[now].son[0]].siz + 1, now = t[now].son[1];} }int Hash( int x, int y ) {int l = find( x - 1 );int r = find( y + 1 );splay( l, 0 );splay( r, l );return t[t[r].son[0]].hash; }int main() {mi[0] = 1;for( int i = 1;i < maxn;i ++ ) mi[i] = mi[i - 1] * 27ull;scanf( "%s", s ); read( Q ); val[++ n] = 0;int len = strlen( s );for( int i = 0;i < len;i ++ )val[++ n] = s[i] - 'a' + 1;val[++ n] = 0;root = build( root, 1, n );char opt[5], ch[5]; int x, y;while( Q -- ) {scanf( "%s", opt ); read( x ); x ++;switch( opt[0] ) {case 'Q' : {read( y ); y ++;if( x > y ) swap( x, y );int ans = 0, l = 1, r = n - y;while( l <= r ) {int mid = ( l + r ) >> 1;if( Hash( x, x + mid - 1 ) == Hash( y, y + mid - 1 ) )ans = mid, l = mid + 1;elser = mid - 1;}printf( "%d\n", ans );break;}case 'R' : {scanf( "%s", ch );splay( find( x ), 0 );t[root].val = ch[0] - 'a' + 1;pushup( root );break;}case 'I' : {scanf( "%s", ch );int l = find( x );int r = find( x + 1 );splay( l, 0 );splay( r, l );t[r].son[0] = ++ n;t[n].hash = ch[0] - 'a' + 1;t[n].val = ch[0] - 'a' + 1;t[n].siz = 1;t[n].f = r;splay( n, 0 );break;}}}return 0; }

Strange Queries

CODECHEF

顯然每個點只會與其左右相鄰點連邊

這種區間內合并的問題，是非常常見的類似線段樹維護區間最大子段和的感覺

但是這是動態維護，所以用平衡樹就行

具體而言，對于每一段區間

• 維護區間只左端點還沒有連線的最小值l_
• 只右端點還沒有連線的最小值_r
• 只左右端點都沒有連線的最小值l__r
• 區間每個點都至少有一條連線的最小值ans
• 維護區間左右端點的權值val_l val_r

考慮兩個區間的合并

• ans

  • 兩個區間的答案相加

  • 左區間的右端點和右區間的左端點都沒連線，此時在兩點之間連線

    花費為右區間左端點的權值與左區間右端點的權值差

• l_

  • 左區間仍只有左端點沒連線l_，右區間均連線ans
  • 左區間兩端都沒連線l__r，右區間左端點沒連線l_，同樣兩區間可以連線

• _r

  • 右區間只有右端點沒連線_r，左區間均連線ans
  • 右區間兩端都沒連線l__r，左區間右端點沒連線_r，兩區間連線

• l__r

  • 左區間只有左端點沒連線l_，右區間只有右端點沒連線_r
  • 左區間和右區間兩端都沒連線l__r，此時左區間右端點和右區間左端點連線

用fhq-treap維護即可

#include <cstdio> #include <algorithm> using namespace std; #define int long long #define maxn 200005 #define inf 1e9 struct node {int key, lson, rson, val, val_l, val_r, l_, _r, l__r, ans;node(){}node( int v ) {ans = inf;key = rand();val = val_l = val_r = v;lson = rson = l_ = _r = l__r = 0;} }t[maxn]; int T, n, Q, root, cnt; int a[maxn];void pushup( node lst, node nxt, int &ans, int &l_, int &_r, int &l__r ) {if( lst.val_l <= -inf and lst.val_r >= inf ) {ans = nxt.ans;l_ = nxt.l_;_r = nxt._r;l__r = nxt.l__r;return;}if( nxt.val_l <= -inf and nxt.val_r >= inf ) {ans = lst.ans;l_ = lst.l_;_r = lst._r;l__r = lst.l__r;return;}int w = nxt.val_l - lst.val_r;ans = min( lst.ans + nxt.ans, lst._r + nxt.l_ + w );l_ = min( lst.l_ + nxt.ans, lst.l__r + nxt.l_ + w );_r = min( nxt._r + lst.ans, nxt.l__r + lst._r + w );l__r = min( lst.l_ + nxt._r, lst.l__r + nxt.l__r + w ); }void pushup( int x ) {t[x].val_l = t[x].val_r = t[x].val;t[x].l_ = t[x]._r = t[x].l__r = 0;t[x].ans = inf;if( t[x].lson ) {pushup( t[t[x].lson], t[x], t[x].ans, t[x].l_, t[x]._r, t[x].l__r );t[x].val_l = t[t[x].lson].val_l;}if( t[x].rson ) {pushup( t[x], t[t[x].rson], t[x].ans, t[x].l_, t[x]._r, t[x].l__r );t[x].val_r = t[t[x].rson].val_r;} }void split( int now, int val, int &x, int &y ) {if( ! now ) x = y = 0;else {if( t[now].val <= val ) {x = now;split( t[now].rson, val, t[now].rson, y );pushup( x );}else {y = now;split( t[now].lson, val, x, t[now].lson );pushup( y );}} }int merge( int x, int y ) {if( ! x or ! y ) return x + y;if( t[x].key < t[y].key ) {t[x].rson = merge( t[x].rson, y );pushup( x );return x;}else {t[y].lson = merge( x, t[y].lson );pushup( y );return y;} }signed main() {t[0].val_l = -inf, t[0].val_r = inf;scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld", &n, &Q );root = 0;for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );sort( a + 1, a + n + 1 );for( int i = 1;i <= n;i ++ ) {t[i] = node( a[i] );root = merge( root, i );}cnt = n;int opt, x, l, r, L, R;while( Q -- ) {scanf( "%lld %lld", &opt, &x );if( opt & 1 ) {split( root, x, l, r );t[++ cnt] = node( x );root = merge( l, merge( cnt, r ) );}else {split( root, x, l, r );split( l, x - 1, L, R );root = merge( L, r );}printf( "%lld\n", t[root].ans >= inf ? 0 : t[root].ans );}}return 0; }

總結

以上是生活随笔為你收集整理的splay/fhq-treap 问卷调查反馈—— [JSOI2008]火星人prefix（splay），Strange Queries（fhq-treap）的全部內容，希望文章能夠幫你解決所遇到的問題。

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