某岛

… : "…アッカリ~ン . .. . " .. .
December 23, 2011

SPOJ 2713. Can you answer these queries IV

Brief description:

给定一个序列,支持以下两种操作:

  • 1 a b: 询问一段区间的数字和。
  • 0 a b: 对一段区间内的每个数字开一次平方。

Analysis:

… Key Observation is “LL 范围内的数最多也就能经受的住 7 次 sqrt() 。。”。
(这样对询问操作用数据结构询问,然后修改操作依靠暴力就行了。。

树状数组 + 并查集
线段树
(。。。好像后期是线段树快一些。。。差别不大…
(。。现场生的时候 xiaodai 学长使用了一种 “七株线段树” 堆垒在一起的数据结构爆 MLE 了我会乱说。。。?。。
(嘛。。总之记录一下吧。。。

External link:

http://www.spoj.pl/problems/GSS4/
http://acm.hdu.edu.cn/showproblem.php?pid=4027