[CF_GYM102798K]Tree Tweaking题目思路代码后记

72 阅读 0 评论 48 点赞

我是靠谱客的博主粗心大炮，最近开发中收集的这篇文章主要介绍[CF_GYM102798K]Tree Tweaking题目思路代码后记，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

传送门 to CF

思路

首先第一步就把我难倒了：建树。~~我连树都建不出来，还要我在树上求解问题？吔屎啦你！~~

当然仔细想想，二叉搜索树实际上是 用树中已存在的节点的值，将值域分割了。对吧？每个点作为分界线，大于它和小于它的，一定不在同一个子树内。反之，若两个点不在同一个子树内，那么存在一个点作为分界线。

那么更进一步，某个叶节点的父节点一定是它的前驱，或者后继。这也是毫无疑问的，从求前驱后继的过程就能得知了。

于是我们有一种简单但是实用的建树方式：用 $s e t$ 维护目前所有点的值，加入一个点的时候，查询它的前驱后继，谁没有对应的儿子，当前点就可以当儿子。

建树讲完了。接下来的工作反而简单。 $i n s e r t$ 顺序可以任意调整，听上去很恐怖吗？只需要考察相邻的两个数交换。显然如果二者不是父亲儿子关系，就没有任何影响。如果是父子关系，二者就会进行一个平衡树中的 $r o t a t e$ 操作。

很容易推广：对于特殊点（在区间 $[L, R]$ 内的数）构成的连通块，可以任意 $r o t a t e$ 。直观地想，也挺容易理解的。当然两个连通块之间不存在祖先关系。

仍然用到上面对于 $B S T$ 的思考。特殊点无论怎么转，总是割出 $s i z e + 1$ 个区间，并且每个区间内包含的数字是固定的。任意两个相邻区间可以是兄弟节点。所以问题变成了一个 $H u f f m a n$ 编码的问题，只不过兄弟节点必须相邻。

这玩意儿就不那么容易贪心了。同样可以证明，权值最小的点必然是直接与旁边某个点作为兄弟节点。然而究竟是左还是右呢？~~严厉抨击左倾思想！~~

考虑到 $R - L + 1 ⩽ 200$ ，也就是说最多 $201$ 个点，那就直接区间 $d p$ 好了呗！

时间复杂度 $n+(R-L)^3]$ 。当然对于前面这部分，就有说法了，即插入顺序本质上就是影响父子关系的。对于插入时间而言，满足小根堆性质。所以我们只需要按照普通的笛卡尔树 $O (n)$ 单调栈建树！~~可惜需要先按照权值排序，没能跃入线性。~~

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
const int MaxN = 100005;
int ch[MaxN][2], dep[MaxN], siz[MaxN];
void getInfo(int x){
if(!x) return ;
rep(j,(siz[x]=1)^1,1){
getInfo(ch[x][j]);
siz[x] += siz[ch[x][j]];
}
}
int_ ans; bool vis[MaxN];
void sumDep(int x){
if(!x) return ;
ans += dep[x]; vis[x] = 1;
rep(j,0,1) sumDep(ch[x][j]);
}
vector<int> v;
bool good[MaxN]; // if it's special
void collect(int x){
if(!x) return v.push_back(0);
if(!good[x]){
v.push_back(siz[x]);
ans -= 1ll*dep[x]*siz[x];
return sumDep(x);
}
vis[x] = true;
rep(j,0,1) collect(ch[x][j]);
}
const int MaxM = 205;
const int infty = (1<<30)-1;
int dp[MaxM][MaxM], pre[MaxM];
int solve(){
int len = int(v.size())-1;
for(int i=1; i<=len; ++i)
pre[i] = pre[i-1]+v[i];
drep(i,len,1) rep(j,i+1,len){
dp[i][j] = infty;
rep(k,i,j-1){
int t = dp[i][k]+dp[k+1][j];
dp[i][j] = min(dp[i][j],t);
}
dp[i][j] += pre[j]-pre[i-1]+j-i-1;
}
return dp[1][len];
}
set<int> s; int a[MaxN];
int main(){
int n = readint();
s.insert(n+1); // guard
s.insert(a[1] = readint());
for(int i=2; i<=n; ++i){
a[i] = readint();
auto fa = s.lower_bound(a[i]);
if((*fa) <= n && !ch[*fa][0])
ch[*fa][0] = a[i];
else ch[*(--fa)][1] = a[i];
dep[a[i]] = dep[*fa]+1;
s.insert(a[i]); // important!
}
getInfo(a[1]); // scan
int l = readint(), r = readint();
rep(i,l,r) good[a[i]] = 1;
for(int i=l; i<=r; ++i){
if(vis[a[i]]) continue;
v.resize(1); // guard
collect(a[i]), ans += solve();
ans += 1ll*siz[a[i]]*dep[a[i]];
}
for(int i=1; i<=n; ++i)
if(!vis[i])
ans += dep[i];
printf("%lldn",ans+n);
return 0;
}