某岛

… : "…アッカリ～ン . .. . " .. .
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

Posted by xiaodao
Category: SPOJ

« | »

  • Archives

    open all | close all