网站公司谁家好,响应是网站怎么做,网站建设中目录是什么意思,网上购物系统er图文章目录[JSOI2008]火星人prefixStrange Queries[JSOI2008]火星人prefix
BZOJ1014 思路很好想#xff0c;哈希字符串即可
只是平衡树的码量大
注意因为splay加入哨兵的原因#xff0c;每个点在平衡树内的排名比真实排名大111#xff08;有极小值的占位#xff09;
考虑…
文章目录[JSOI2008]火星人prefixStrange Queries[JSOI2008]火星人prefix
BZOJ1014 思路很好想哈希字符串即可
只是平衡树的码量大
注意因为splay加入哨兵的原因每个点在平衡树内的排名比真实排名大111有极小值的占位
考虑的时候就只在询问的时候考虑修改的时候忘了就挂了
#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;
}
