有哪些算法或数据结构是ACM大牛们在比赛中创造出来的？
趁乱水一发。 以及其他一些同学说的当然没有错。SBT之类的显然不是新东西。然而有一些被创造出来的数据结构或算法并没有得到足够的注意，甚至连发现者自己也不知道是理论突破。下面举几个我知道的OI界比理论界早的例子。 1. 允许一个错误的最长公共子串 OI选手的进展：不晚于2013年在noip吧有一个帖子问到这题，之后黄嘉泰在帖子里给出了做法。之后被出到了BZOJ 3145。(我试图找那个帖子，然而没有找到。) 理论界的进展：我能找到的最早的解决这个问题的paper是这篇： 出现时间是14年9月。 2. 使用函数式数据结构解决区间k大 OI选手的进展：不晚于2012年2月出现了被称为“主席树”的数据结构，可以解决(静态，动态)的(线段上，树上)区间k大问题。 理论界的进展：05年的时候有这篇paper： 可以看到其Range Median Quey的结果均比“主席树”差。09年出现了这篇paper： 此时在线段上的区间k大已经做到静态与动态都比主席树优。对于树上的情形我并没有找到对应的paper。(即：树上的“主席树”算法是领先理论界的。) 我在2014年跟Erik Demaine提过“主席树”的算法。Demaine表示并没有听说过。 3. 动态仙人掌 OI选手的进展：吕凯风于2014年3月的几篇blog使得我们能够像维护动态森林一样维护动态仙人掌。 之后似乎也有将动态仙人掌和Top tree联系起来的尝试： 理论界的进展：我并没有找到理论界的对应进展。当然可能情况是理论界根本不关心这个问题。