codeforces#223

真不该错过Sereja的CF!——superpear

感人的Sereja的场
赛后看了一下……
感人肺腑……

A

傻×题……第二种操作只对前10^5个元素有效……我们暴力存前的10^5个元素然后暴力就可以了的样子……

B

没看题意……

C

简单的线段树……发现有好多人交了离线乱搞……但是线段树也是很好写的?
其实就是GSS的翻版……

D

语文题无误……
看了好久题意……
发现原来它是这个意思啊!
然后就会做了

E

Sereja的场的E,一定要先点开来做!
首先注意到那个增加变量值x的操作……一定是从小到大来选元素使得x增加的……证明可以用反证法……
那么最大的元素对x的贡献为其一半
次大的元素对其贡献为其四分之一
次次大的元素对其贡献为八分之一
.....
依此类推就明白了什么……
注意到1/2^L,当L略大的时候……对答案的贡献就可以忽略不计了……
实践证明L取40就够了……更低大概不要太离谱的话……也可以

那么接下来是愉快的算贡献时间……

我们要算一个元素,有多少个区间包含它,并且它作为区间内第一大元素出现……
然后算有多少个区间包含它……并且它作为区间第二大元素出现……
一直算到第L大……
然后贡献加到答案里就可以完事了……
怎么算就很简单了……
可以用链表来搞一搞……
官方题解说用并查集……没怎么看懂……懒得学了……说不定和链表搞法本质是一样的……
就这样了……

upd

其实也可以用线段树……太naive了……这样就不用卡L的大小了大概?

Comments

comments powered by Disqus