网站开发遇到什么问题,网站建设课件,珠海网站建设方案开发,什么网站可以做市场分析呢文章目录左偏树左偏树的合并(merge)操作例题罗马游戏[Apio2012]dispatching[JLOI2015]城池攻占[Baltic2004]sequence左偏树
左偏树是一个堆#xff0c;而且是一个可并堆#xff0c;所以一定有权值的限制
以小根堆为例#xff0c;那么必须满足节点权值小于左右儿子权值而且是一个可并堆所以一定有权值的限制
以小根堆为例那么必须满足节点权值小于左右儿子权值即val[i]val[lson[i]] val[i]val[rson[i]]
为了维护左偏树的时间复杂度就要设计一些左偏树独有的工具定义
外节点满足左右儿子至少有一个没有的点距离dis[i]点iii到离它最近的一个外节点的距离特别的空节点的距离为−1-1−1外节点本身距离为000
左偏树树如其名向左偏的树
也就是说左边要“重一点”但这个重不是常见的子树大小或者高度而是我们定义的dis
对于左偏树的每个点iii满足dis[lson[i]]dis[rson[i]] 完全有可能左儿子只有一个点右儿子是一条链不管是左儿子的一个点还是右儿子一条链上的点都符合外节点定义所以dis都是000 考虑由下向上更新距离数组即dis[i]min(dis[lson[i]],dis[rson[i]])1
由于左偏树的性质右儿子距离一定是小的所以左偏树的更新直接就是从右儿子处更新
dis[i]dis[rson[i]]1
左偏树特殊距离的定义就保证了左偏树的时间复杂度
节点数为nnn的树树根的dis≤log(n1)−1dis\le \log(n1)-1dis≤log(n1)−1 一个点的距离大于xxx意味着x−1x-1x−1层内都是满二叉树 左偏树的合并(merge)操作
左偏树最重要的或者说特色就是它的合并操作
有了以上的理论基础结合fhq-treap的返回根合并操作左偏树的合并还是很好写的
struct node { int l, r, val, dis; } t[maxn];
int merge( int x, int y ) {if( ! x or ! y ) return x y;if( t[x].val t[y].val ) swap( x, y );t[x].r merge( t[x].r, y );if( t[t[x].l].dis t[t[x].r].dis ) swap( t[x].l, t[x].r );t[x].dis t[t[x].r].dis 1;return x;
}int lson[maxn], rson[maxn], val[maxn], dis[maxn];
int merge( int x, int y ) {if( ! x or ! y ) return x y;if( val[x] val[y] ) swap( x, y );rson[x] merge( rson[x], y );if( dis[lson[x]] dis[rson[x]] ) swap( lson[x], rson[x] );dis[x] dis[rson[x]] 1;return x;
}例题
罗马游戏
luogu 2713
这就是比较板的题了初始时把每个士兵当成一个左偏树合并就是两个士兵的左偏树合并
杀士兵就是去掉左偏树的根节点直接合并左右儿子即可
但是怎么找士兵所在的兵团呢——并查集
#include cstdio
#include iostream
using namespace std;
#define maxn 1000005
struct node { int l, r, val, dis; } t[maxn];
bool vis[maxn];
int f[maxn];
int n, m;int find( int x ) { return x f[x] ? x : f[x] find( f[x] ); }int merge( int x, int y ) {if( ! x or ! y ) return x y;if( t[x].val t[y].val ) swap( x, y );t[x].r merge( t[x].r, y );if( t[t[x].l].dis t[t[x].r].dis ) swap( t[x].l, t[x].r );t[x].dis t[t[x].r].dis 1;return x;
}int main() {scanf( %d, n );t[0].dis -1;for( int i 1;i n;i ) {scanf( %d, t[i].val );f[i] i;}scanf( %d, m );char opt[5]; int i, j;while( m -- ) {scanf( %s, opt );if( opt[0] M ) {scanf( %d %d, i, j );if( vis[i] or vis[j] ) continue;i find( i ), j find( j );if( i ^ j ) f[j] f[i] merge( i, j );}else {scanf( %d, i );if( vis[i] ) printf( 0\n );else {i find( i );vis[i] 1;printf( %d\n, t[i].val );f[i] f[t[i].l] f[t[i].r] merge( t[i].l, t[i].r );/*就算杀了根节点代表的这个士兵也要更新士兵的并查集集合因为可能有些士兵跨过了根节点的左右儿子直接并查集是接在根节点并查集的下面的find的时候是会跳到根节点的并查集点的*/}}}return 0;
}[Apio2012]dispatching
BZOJ 2809
dfs树从下往上合并
每次丢掉最大的CiC_iCi即可
同样别忘了并查集
#include cstdio
#include vector
#include iostream
using namespace std;
#define maxn 100005
#define int long long
vector int G[maxn];
int lson[maxn], rson[maxn], dis[maxn], f[maxn], L[maxn], C[maxn];
int n, m, root;
long long ans;int find( int x ) { return f[x] x ? x : f[x] find( f[x] ); }int merge( int x, int y ) {if( ! x or ! y ) return x y;if( C[x] C[y] ) swap( x, y );rson[x] merge( rson[x], y );if( dis[lson[x]] dis[rson[x]] ) swap( lson[x], rson[x] );dis[x] dis[rson[x]] 1;return x;
}pair int, int dfs( int u ) {int cnt 1, sum C[u];for( auto v : G[u] ) {pair int, int son dfs( v );cnt son.first, sum son.second;int x find( u ), y find( v );root f[u] f[v] merge( x, y );while( sum m ) {sum - C[root], cnt --;f[root] f[lson[root]] f[rson[root]] merge( lson[root], rson[root] );root f[root];}ans max( ans, L[u] * cnt );}ans max( ans, L[u] * cnt );return make_pair( cnt, sum );
}signed main() {scanf( %lld %lld, n, m );for( int i 1, B;i n;i ) {scanf( %lld %lld %lld, B, C[i], L[i] );G[B].push_back( i );f[i] i;}dis[0] -1;dfs( 1 );printf( %lld\n, ans );return 0;
}[JLOI2015]城池攻占
luogu 3261
初始时将每一座城市当成一个左偏树并把在该城市的士兵在左偏树上完成合并
与上一题一样的从下往上合并左偏树把所有儿子的骑士聚集到当前根节点城市
把战斗力不足的扔掉所以需要小根堆
利用初末城市的深度差巧妙计算出每个骑士能攻占的城市数量
至于城市对骑士的战斗力影响一样的整体懒标记碰到了再下传
#include cstdio
#include vector
#include iostream
using namespace std;
#define int long long
#define maxn 300005
vector int G[maxn];
struct node { int lson, rson, dis, val, add, mul; }t[maxn];
int root[maxn], h[maxn], a[maxn], v[maxn], c[maxn];
int ans1[maxn], ans2[maxn], dep[maxn];
int n, m;void modify( int x, int mul, int add ) {if( ! x ) return;t[x].val * mul;t[x].val add;t[x].mul * mul;t[x].add * mul;t[x].add add;
}void pushdown( int x ) { if( ! x ) return;modify( t[x].lson, t[x].mul, t[x].add );modify( t[x].rson, t[x].mul, t[x].add );t[x].mul 1;t[x].add 0;
}int merge( int x, int y ) {if( ! x or ! y ) return x y;pushdown( x );pushdown( y );if( t[x].val t[y].val ) swap( x, y );t[x].rson merge( t[x].rson, y );if( t[t[x].lson].dis t[t[x].rson].dis ) swap( t[x].lson, t[x].rson );t[x].dis t[t[x].rson].dis 1;return x;
}void dfs( int u, int fa ) {dep[u] dep[fa] 1;for( auto v : G[u] ) {dfs( v, u );root[u] merge( root[u], root[v] );//将所有从子树的管辖城市中存活到u城市的骑士进行合并 }while( root[u] and t[root[u]].val h[u] ) {//从最小杀伤力骑士开始 将所有在u城市死亡的骑士剔除 并记录最后答案 pushdown( root[u] );ans1[u] ;ans2[root[u]] dep[c[root[u]]] - dep[u];//骑士能攻占的数量巧妙利用初末深度差 最开始的城市深度-u的深度 root[u] merge( t[root[u]].lson, t[root[u]].rson ); }if( a[u] ) modify( root[u], v[u], 0 );else modify( root[u], 1, v[u] );
}signed main() {scanf( %lld %lld, n, m );for( int i 1;i n;i ) scanf( %lld, h[i] );for( int i 2, f;i n;i ) {scanf( %lld %lld %lld, f, a[i], v[i] );G[f].push_back( i );}t[0].dis -1;//在每一座城市都建立一个左偏树 for( int i 1;i m;i ) {scanf( %lld %lld, t[i].val, c[i] );root[c[i]] merge( root[c[i]], i );//将在同一座城市的骑士在左偏树上体现合并 //root[i]:在城市i的左偏树的最小杀伤力骑士的编号 }dfs( 1, 0 );//搜城 从下往上爬 while( root[1] ) {/*最后在总城市根1的骑士答案还未计算 暴力弹出所有存活的骑士 攻占的数量就是初始城市到1号超级城市一路经过的城市也就是深度*/ ans2[root[1]] dep[c[root[1]]];root[1] merge( t[root[1]].lson, t[root[1]].rson );}for( int i 1;i n;i ) printf( %lld\n, ans1[i] );for( int i 1;i m;i ) printf( %lld\n, ans2[i] );return 0;
}[Baltic2004]sequence
BZOJ 1367
给定nnn以及长度为nnn的整数序列a1,...,ana_1,...,a_na1,...,an你需要构造一个严格上升的长度为nnn整数序列t1,...,tnt_1,...,t_nt1,...,tn定义R∣t1−a1∣...∣ti−ai∣...∣tn−an∣R|t_1-a_1|...|t_i-a_i|...|t_n-a_n|R∣t1−a1∣...∣ti−ai∣...∣tn−an∣求最小的RRR
n≤106n\le 10^6n≤106 假设是构造不下降序列
考虑两种特殊的序列
a1≤a2≤...≤ana_1\le a_2\le ...\le a_na1≤a2≤...≤an直接让tiait_ia_itiai最后答案就是000a1≥a2≥...≥ana_1\ge a_2\ge ...\ge a_na1≥a2≥...≥an直接让t1amidt_1a_{mid}t1amid序列的中位数
现在考虑一般形式的aaa
将aaa序列划分成这两种特殊序列的若干段
考虑1...i1...i1...i的答案为w1,...wiw_1,...w_iw1,...wi现在考虑i1i1i1先让wi1ai1w_{i1}a_{i1}wi1ai1
然后就要根据第二种特殊序列进行合并如果wi≥wi1w_i\ge w_{i1}wi≥wi1就合并后wiwi1w_iw_{i1}wiwi1中位数直到wjwi1w_jw_{i1}wjwi1
这个中位数是参与合并的www中的中位数不是整体的中位数
用左偏树维护一个sizsizsiz大小即可
#include cstdio
#include iostream
using namespace std;
#define maxn 1000005
struct node {int lson, rson, val, siz, dis;
}t[maxn];
int n, cnt;
int root[maxn], L[maxn], R[maxn], a[maxn];int merge( int x, int y ) {if( ! x or ! y ) return x y;if( t[x].val t[y].val ) swap( x, y );t[x].rson merge( t[x].rson, y );t[x].siz t[t[x].lson].siz t[t[x].rson].siz 1;if( t[t[x].lson].dis t[t[x].rson].dis )swap( t[x].lson, t[x].rson );t[x].dis t[t[x].rson].dis 1;return x;
}long long Fabs( long long x ) {return x 0 ? -x : x;
}int NewNode( int x ) {t[ cnt].val x;t[cnt].siz 1;t[cnt].lson t[cnt].rson t[cnt].dis 0;return cnt;
}int main() {scanf( %d, n );for( int i 1;i n;i )scanf( %d, a[i] ), a[i] - i;t[0].dis -1;int ip 0;for( int i 1;i n;i ) { ip;L[ip] R[ip] i;root[ip] NewNode( a[i] );while( ip 1 and t[root[ip - 1]].val t[root[ip]].val ) {root[ip - 1] merge( root[ip - 1], root[ip] );R[ip - 1] R[ip];ip --;while( t[root[ip]].siz * 2 R[ip] - L[ip] 2 )root[ip] merge( t[root[ip]].lson, t[root[ip]].rson );}}long long ans 0;while( ip ) {int val t[root[ip]].val;for( int i L[ip];i R[ip];i )ans Fabs( 1ll * val - a[i] );ip --;}printf( %lld\n, ans );return 0;
}
