[codeforces 85D]【平衡树】

【题意】

n个操作

每个操作可以是

add x  把x加进set里

del x   把x从set中删除

sum  令A[1..m]按递增序表示set中的函数。求Sum{A[i] | i%5==3}

【算法】

直接弄棵平衡树。每个结点维护下面几个域。 long long Sum[5] ,offset ,delta,key。

然后标记上下传就可以了,不错的平衡树练手题目。

尝试了一下struct封装好各种操作的Splay。。。感觉还挺舒服,但是写得爆长。。。

我感觉离散化以后线段树也可以搞。

或者直接建5棵平衡树。index变的时候就裂开然后再合并就好了。

【其它】

看了一下watashi飘逸的treap。

然后再看了一下最短的那个人。。。

修改用一个vector二分了个位置(lower_bound),然后直接insert erase。

然后统计直接for (i=3;i

特么坑爹啊!!!!!yandex.algorithm的题这样被人水过啊。

又想起NOI2003文本编辑器pascal那个不能吐槽的move=_=…特么比正解什么的都跑得快…

加入对话

6条评论

留下评论

回复 中国脑筋 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注