这是线段树专题考试中一道与线段树完全没有关系的题。我直接异或不解
题目大意：
给一个长度为 \(n\) 的排列 \(a\)，将其按顺序插入后构成一棵二叉搜索树，再给定 \(L,R\)，表示你可以任意调换区间 \([L,R]\) 内数字的插入顺序，要求最后树的深度和最小并输出它。
\(1\le n\le 10^5;1\le l\le r\le n;1\le r-l+1\le 200.\)
我承认，我对区间DP一点都不熟悉。
不管怎么样，你得知道怎么建树，然后对正解才会有所启发。
我们考虑如果确定了插入顺序，一个点在插入的时候要么接在其权值前驱的右儿子处，要么接在权值后继的左儿子处。而且我们可以证明不会有其它情况，简单反证即可。
对于整棵树来说，\(\sum size_i=\sum depth_i\)。
这个结论很容易看懂，但想到它并不容易(也许是我太弱了QAQ)。
当然你可以用 \(\tt part1\) 中的方法，用 \(set\) 维护前驱后继建树，然后求出深度和或者子树大小和，但是我们有一个更为牛逼的做法，并且可以运用到接下来的 DP 当中。
我们真的需要将整棵树都建出来之后才能求答案吗？
如图，当我们插入 \(a_1\) 时，难道不知道它的子树大小吗？显然为它的后继 \(n+1\) 减去前驱 \(0\) 再减 \(1\)，也就是 \(n\)。
当我们插入 \(a_2\) 时，我们能够知道它的子树大小吗？显然可以，即为 \(a_1-0-1\)，也是后继减前驱减 \(1\)。
这样做有什么好处呢？我们发现我们不需要依赖于整棵树的最终形态，而是依靠前面已经有的信息就可以求出其对答案的贡献。
或者我们将其称为无后效性。
在 \(\tt part3\) 中我们已经发现了一种无后效性求答案的方法，可以应用于 DP 中，\([L,R]\) 区间的数对答案的影响仅仅只在于其插入顺序的不同，接下来要做的事我用一张图来表示也许更容易理解：
黑点为之前已经插入的 \(0,n+1\) 以及 \(L\) 之前的点，红点为 \([L,R]\) 之间的数，可以发现，黑点将整个值域割裂成了很多个小区间，两两小区间中的红点互不影响，于是我们可以对每一个小区间中的红点做区间DP，求出最优答案，最后再将 \(R\) 之后的点插入进去求答案即可。
区间DP 就是小区间合并成大区间的DP转移，并不困难。
时间复杂度为 \(O(n\log_2n+(R-L)^3)\)。
一个猜测：直觉告诉问我们可以优先插入小区间中间的数来达到最优，但是 \(偶耶XJX\) 试过了，会 \(\tt \color{red}WA\)，但是分不低。
//12252024832524
#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const LL INF = 1ll << 60;
int n,L,R;
int a[MAXN];
LL ans;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > ‘9‘ || c < ‘0‘){if(c == ‘-‘)f = -1;c = getchar();}
while(c >= ‘0‘ && c <= ‘9‘){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar(‘-‘),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
set<int> s;
set<int>::iterator it1,it2;
vector<int> cao[MAXN];
void Add(int x)
{
it1 = it2 = s.upper_bound(x);
--it1;
ans += (*it2) - (*it1) - 1;
s.insert(x);
}
int t[MAXN],tot;
LL dp[205][205];
void DP(int ll,int rr)
{
sort(cao[rr].begin(),cao[rr].end());
t[tot = 1] = ll;
for(int i = 0,len = cao[rr].size();i < len;++ i) t[++tot] = cao[rr][i];
t[++tot] = rr;
for(int i = 2;i < tot;++ i)
for(int j = i;j < tot;++ j)
dp[i][j] = INF;
for(int l = tot-1;l >= 2;-- l)
for(int r = l;r <= tot-1;++ r)
for(int i = l;i <= r;++ i)
dp[l][r] = Min(dp[l][r],dp[l][i-1]+dp[i+1][r]+t[r+1]-t[l-1]-1);
ans += dp[2][tot-1];
}
int main()
{
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
n = Read();
for(int i = 1;i <= n;++ i) a[i] = Read();
L = Read(); R = Read();
s.insert(0); s.insert(n+1);
for(int i = 1;i < L;++ i) Add(a[i]);
for(int i = L;i <= R;++ i) cao[*s.upper_bound(a[i])].push_back(a[i]);
for(it2 = it1 = s.begin(),++it2;it2 != s.end();it1 = it2,++it2)
if(cao[*it2].size())
DP(*it1,*it2);
for(int i = L;i <= R;++ i) s.insert(a[i]);
for(int i = R+1;i <= n;++ i) Add(a[i]);
Put(ans);
return 0;
}
可以发现，无论 \([L,R]\) 中的数字插入顺序是什么样的，由于插入的位置一定不会变，所以 \(R\) 之后的数再插入进去其实对答案的贡献是不会有变化的，而如果我们从二叉搜索树的形态的角度来看，似乎很难发现这一性质。
也许从 \(200\) 的数据范围想到区间DP这道题就很好做了吧。
或者把二叉搜索树拍扁成为值域数轴更为关键？
总之做了这道题这些套路就会了。
图真的很丑，见谅。
原文：https://www.cnblogs.com/PPLPPL/p/15202117.html