某島

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