本人写Treap
(赞最多的题解模板)用mt19937
导致测试点随机TLE,而普通rand()
被AC。为了防止下一个入坑者,特立此警告。
mt19937
随机出的数赋值给int
可能会出现优先级为负数的情况,因为0节点
的优先级为0
,大于优先级为负的节点
,因而0节点
会被旋上去,会导致各种错误。
解决方法:
使用algorithm
库的rand()
。
或者,优先级数组dat[]
的类型改为unsigned int
或者long long int
,千万不可以搞出来负数。
或者,给0节点
优先级赋值-2147483648
。
希望能帮到一些人,这是我调了两个半天的结果。