vector的某些操作虽然理论上 $O(n)$ 但是常数很小很小的吧，而且很难卡。不过我看不到你代码 所以我不作评价。
by liangbowen @ 2023-03-08 22:03:37
@[liangbowen](/user/367488) 我用的是纯暴力，线段树合并均摊复杂度每次都是log级的，但是我是把每一个元素都upper_bound后emplace进去的，也就是说每次操作的复杂度都是最大理论复杂度都是 $ n^2$ 的，不过因为是启发式合并，所以那个总复杂度实际会比 $O(n^3)$ 小一点，加上vector emplace的小常数，就过了。。
by 聊机 @ 2023-03-09 10:11:01
@[liangbowen](/user/367488) 我说的乱搞是指这一部分
那个 if 那里
```cpp
void dfs(int &x) {
x=++E;rd(ch);
if(ch) {
v[x].push_back(ch);
return ;
}
int ls=0,rs=0;
dfs(ls); dfs(rs);cnt=0;
if(v[ls].size()>v[rs].size()) swap(ls,rs);
for(int i=0,s=v[rs].size();i<(int)v[ls].size();i++)
cnt+=s-(upper_bound(v[rs].begin(),v[rs].end(),v[ls][i])-v[rs].begin());
ans+=mn(cnt,(long long)v[ls].size()*(long long)v[rs].size()-cnt);
if(cnt>=120000) {
int i=0,j=0;
while(i<(int)v[ls].size()&&j<(int)v[rs].size())
if(v[ls][i]<v[rs][j]) v[x].push_back(v[ls][i++]);
else v[x].push_back(v[rs][j++]);
while(i<(int)v[ls].size()) v[x].push_back(v[ls][i++]);
while(j<(int)v[rs].size()) v[x].push_back(v[rs][j++]);
vector<int>().swap(v[rs]);
}
else {
for(int i=0;i<(int)v[ls].size();i++)
v[rs].emplace(upper_bound(v[rs].begin(),v[rs].end(),v[ls][i]),v[ls][i]);
x=rs;
}
// vector<int>().swap(v[ls]);
}
```
by 聊机 @ 2023-03-09 10:11:51
@[liangbowen](/user/367488) 我感觉我启发式合并的复杂度算的有点问题，所以启发式这一类东西应该怎么求复杂度？
by 聊机 @ 2023-03-09 10:12:38
@[聊机](/user/290959) 启发式总共均摊是nlogn的啊
by Miss_SGT @ 2023-11-19 17:14:19
@[zhouchenqiao1](/user/705012) 呃这个并不是常规意义上的启发式，而且均摊也是有原因的，你就像树上线段树合并那种，是因为差入元素的个数是 n 级别所以才摊成 log 级的，我写的这个玩意就是纯面向数据的一坨乱搞，看个乐子就行了。
by 聊机 @ 2023-11-19 17:38:29
@[聊机](/user/290959) 这样啊
by Miss_SGT @ 2023-11-19 17:59:26