5.1
闲话
做题纪要
luogu P3521 [POI2011] ROT-Tree Rotations
-
What is 先序遍历 ?
-
对于一棵子树的根节点 \(x\) ，交换其左右子树，不会对以前的节点产生影响（不会更改贡献）。
-
这棵子树产生的贡献值来自三种情况，分别是都在左子树，都在右子树，左子树和右子树各一个。只考虑第三种情况的求解，前两种可以递归处理。
-
对于每个叶子节点建立权值线段树并依次向上合并。
- 动态开点权值线段树加线段树合并板子。
- 设两棵线段树分别为 \(A,B\) ，从根节点开始递归合并。
- 递归到非叶子节点时，如果 \(A\) 树或 \(B\) 树上的对应节点为空，则直接返回另一个树上对应节点；递归到叶子节点时，直接合并（要符合区间可加性）；否则，选一个节点作为合并之后的点，用另一个点来更新信息。
- 一般情况下为节省空间，不再新开线段树而直接在其中一棵线段树上修改。
- 时空复杂度为 \(O(m \log_{2} V)\) ，其中 \(V\) 是值域，一般情况有 \(n,m\) 同阶，故常写作 \(O(n \log_{2} V)\) 。
- 动态开点权值线段树加线段树合并板子。
-
在权值线段树合并过程中，由于 \(rt_{1},rt_{2}\) 所代表的区间是同一个区间，故 \(rt_{1}\) 的右子树一定比 \(rt_{2}\) 的左子树大。此时交换其左右子树产生的贡献为 \(sum_{rson_{rt_{1}}} \times sum_{lson_{rt_{2}}}\) ，不交换其左右子树产生的贡献为 \(sum_{lson_{rt_{1}}} \times sum_{rson_{rt_{2}}}\) 。最终两者取 \(\min\) 即可。
-
LibreOJ 2163. 「POI2011 R2 Day2」旋转树木 Tree Rotations 上时限开了 \(160ms\) ，加个快读就行了。
点击查看代码
const ll Maxn=3e5+10,Maxnlogn=Maxn*log2(Maxn); ll rt_sum=0,ans=0,sum1=0,sum2=0; struct SegmentTree { ll ls,rs,sum; }tree[Maxnlogn]; #define lson(rt) (tree[rt].ls) #define rson(rt) (tree[rt].rs) void pushup(ll rt) { tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum; } ll build() { rt_sum++; lson(rt_sum)=rson(rt_sum)=tree[rt_sum].sum=0; return rt_sum; } void update(ll rt,ll l,ll r,ll pos,ll val) { if(l==r) { tree[rt].sum+=val; return; } ll mid=(l+r)/2; if(pos<=mid) { lson(rt)=(lson(rt)==0)?build():lson(rt); update(lson(rt),l,mid,pos,val); } else { rson(rt)=(rson(rt)==0)?build():rson(rt); update(rson(rt),mid+1,r,pos,val); } pushup(rt); } ll merge(ll rt1,ll rt2,ll l,ll r) { if(rt1==0)//如果有节点为空返回另一个节点 { return rt2; } if(rt2==0) { return rt1; } if(l==r)//找到叶子节点合并并返回 { tree[rt1].sum+=tree[rt2].sum; return rt1; } sum1+=tree[rson(rt1)].sum*tree[lson(rt2)].sum; sum2+=tree[lson(rt1)].sum*tree[rson(rt2)].sum; ll mid=(l+r)/2; lson(rt1)=merge(lson(rt1),lson(rt2),l,mid); rson(rt1)=merge(rson(rt1),rson(rt2),mid+1,r); pushup(rt1); return rt1; } ll dfs(ll n) { ll root,ls,rs,x; x=read(); if(x==0) { ls=dfs(n); rs=dfs(n); sum1=sum2=0; root=merge(ls,rs,1,n);//合并 ans+=min(sum1,sum2); } else { root=build(); update(root,1,n,x,1); } return root; } int main() { ll n; n=read(); dfs(n); write(ans); return 0; }