保卫战(3)

线段树和splay仍在对峙。

说时迟,那时快,这句话快被用烂。

线段树二话不说就是使出一个区间修改——这个招式虽然现在看来已没有多大惊异之处,但当年线段树作为仅次于树状数组的开拓者,追随树状数组开拓领地的时候,线段树这个招式可让暴力部族的那些家伙吃了不少苦头——说到暴力部族,那又是另外的故事了,我们先扯回来——线段树使出区间修改是想让splay的连接点被修改地乱七八糟使其丧失战斗力,此招式的一大特点如其名称所言,是覆盖区间广,一般人是很难不被伤到的。

但splay说来也不是盖的。splay师从大名鼎鼎的旋转大师SBT,一身轻功练的炉火纯青,线段树的区间修改使出时,splay左闪右闪,旋来转去,几乎把区间修改全躲了过去,剩下的也能接近毫发无伤的水平。

如果觉得这样就完了,那就大错特错了。一次区间修改也许没什么威力,但成百上千次就很有威力了。但即使是,一次区间修改不会耗费多大力气,但成百上千次,那所需要的巨大力量几乎没人能拥有,线段树真的不会被累垮嘛?这便是区间修改的另一大特点——每次使用都会在身上一些部位留下标记,下次再次使用区间修改时,能通过标记迅速找到需要使用的部位,便可节省下大量力气——那些暴力部族不懂这些,就是这样活脱脱被累死的。

眨眼间,线段树又使出几十次区间修改,splay使劲腾挪转移,左突右撞,终究还是受了一些伤。

线段树:小子!怎么只会躲躲闪闪?难不成是看不起老夫?

splay:哎呀,你瞧您说得这是什么话,我怎么会看不起呢?您不会是觉得斗争是我挑起的,却是您先出的手,有损您的面子吧?

线段树:哼,谁知道你这家伙会使出什么下三滥的招数!

splay:招数倒是有有一点,但并没有那么下三滥就是了。看招!

线段树从身后感受到了一股凉意。回头一看,身后居然同时有七个splay在同时盯着自己。那些splay也和之前那个一样,不停地旋转着。

线段树回头一看,之前与自己说话的那个splay已经不见。心想:不好!再回头一看,那七个splay组成的巨网越来越近,似乎要把它吞噬。线段树又使出好几个区间修改,可都被一一躲掉,居然没一个打中。

线段树:我知道你用的什么鬼把戏!你用LCT不去对付外敌,却拿来内斗?你以为这个就能吓唬住我?

splay:吓不吓得住就不知道,但比你那区间修改实用多了?你那么多年拿着这个东西,一直固步自封!

线段树:我固步自封,你那就叫创新?别以为我不知道你用LCT把树链剖分逼得无路可走,要不是我救了她,她也许真的饿死在街头!

splay:哟?我怕你不是善心大发,而是看上点分治,边分治姐妹俩了吧?她俩长得可真漂亮,是吧?

一阵咳嗽身从不远处传来,但线段树和splay虽然都已听到,但都没有转头去看,以为是对方的骗人技俩,仍然争吵不休。

splay:再废话没用,看招!access!

Leave a Reply