search

henix / blog

some notes
0 stars 0 forks source link

poj 2823 #27

Open henix opened 10 years ago

henix commented 10 years ago

单调队列 insert O(k) remove O(1) find-min O(1) 空间 8k bytes 实际效果较好 ~700ms

treap insert O(log k) remove O(log k) find-min O(log k) 空间 16n bytes 实际效果 3s 多 优化：

  1. 改为非递归 - 没效果
  2. 不用 rand()
  3. 不记录 count

heap insert O(log k) remove O(log k) find-min O(1) 空间 8k bytes

其他： skew heap / pairing heap