robinyqc @ 2023-09-21 22:24:44
RT，这是一篇通常很快的 treap，但是在极端情况下似乎根本没法工作。（也不知道是不是我的数据错了。但是我测了 Coding Jellyfish，六楼溜刘，EarthMessenger 和我的都能跑。）
数据生成思路很简单，就是全部是操作一，全部插入
生成器：
// #pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<random>
#include<set>
#include<ctime>
using namespace std;
signed main() {
ios::sync_with_stdio(false);
freopen("same0.in","w",stdout);
int n=100000,m=1000000;
cout<<n<<' '<<m<<'\n';
for(int i=1;i<=n;i++) cout<<1<<' ';
cout<<'\n';
for(int i=1;i<=m;i++) cout<<"1 1\n";
}by robinyqc @ 2023-09-21 22:37:07
我今天本来准备把我的板子改成他这种写法。幸好特殊的习惯让我测试代码。
by robinyqc @ 2023-09-21 22:38:44
@Maxmilite
by robinyqc @ 2023-09-21 22:49:36
而且，这是一篇较为知名的 Leafy Tree 讲解 中提到的写法，也是我看到这个提交的原因。那和我一样可能有很多人看到这种写法认为它是一种优化。
普通 FHQ 写的再烂这个数据都能过的，我机房里面一个超大常数同学的代码也能过，所以不存在卡不卡的问题。
by robinyqc @ 2023-09-22 07:50:34
鉴于没有实际输出的行为在题目中未定义，这样一份输入是更好的：
// #pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<random>
#include<set>
#include<ctime>
using namespace std;
signed main() {
ios::sync_with_stdio(false);
freopen("same0.in","w",stdout);
int n=100000,m=1000000;
cout<<n<<' '<<m<<'\n';
for(int i=1;i<=n;i++) cout<<1<<' ';
cout<<'\n';
for(int i=1;i<m;i++) cout<<"1 1\n";
cout<<"4 1\n";
}输出应是 1。
by StayAlone @ 2023-09-22 09:34:38
代码
这份代码可以通过原数据和这个数据，但是常数变大了。
更改部分只有 _insert 函数。注意有两处更改，有一处是大于号改成小于号。
当全部元素相同时，原来的代码会无论如何将新节点插入右子树，形成长度为
@robinyqc @toaru
by StayAlone @ 2023-09-22 09:40:42
现在随机 WA 了，，，，晚点再看看，
by YamadaRyou @ 2023-09-22 18:25:15
@StayAlone 我这个插入方法对于有重复的情况应该确实是有问题的，我记着我最开始挂的原因就是因为堆权值重复了，保证高度的话应该还需要保证bst权值也不重复，所以正确的写法或许应该是把一样的放一起……
by StayAlone @ 2023-09-22 18:59:06
@toaru 我当时也想到这个方法，但是写起来就麻烦许多……我在魔改您的代码就是在 insert 的时候把直接赋左右儿子改成通过 merge 的随机保持平衡，但是现在 WA 了，，，，只能后面再调一下。
by Maxmilite @ 2023-09-24 20:57:10
@robinyqc Added, thx.
by MeteorFlower @ 2023-10-20 08:50:26
@robinyqc 已解决。修改一个符号即可。@StayAlone 应该会更新他的博客说明具体原因。