SPOJ 4487 GSS6

大意:NOI维护数列的简化版。。
我什么时候把维护数列也A掉就爽了。。。
4个操作
1:insert(p,x) 在第p-1个数之后插入一个数x
2:delete(p) 删除第p个数
3:max(l,r) 输出l到r之间的最大连续和
4:replace(p,x) 将第p个数换成x。。
我写了两个程序。。一个块状数组,一个splay。。
块状数组妈妈的太慢了。。。
insert直接把第p-1个数转成根,第p个数转到根下面,那么直接把这个数放到第p个数的左子树就行了。。
delete把第p个数找到。。然后一直转到没有左儿子。。再删除它。。
max只要把第l-1个数转成根,第r+1个数转到根下面。。就OK了。。
replace跟insert基本一样。。。
转好了之后,别忘了splay哦!
还有Null的参数设置,也是需要考虑的。。。
splay太NB了。。。
俄。也不是,维护数列里面没要求删除的。。不过也差不多。。
12.4s。。。感觉原来发代码太占空间了。。放到ideone上面吧。。很漂亮。。
Code:http://ideone.com/aoAEParp

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>