Rip Van Winkle's Code (UVa 12436 World Finals Warmup 2012 1)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3867

問題

問題分に書いてあるようなクエリ(ある区間に1次関数を足す、ある区間の値をxにする、ある区間のsumを取る)がq個来る。全て捌け。
q<=4*10^5
1<=区間<=250000

x

<=10^5

解法

SegmentTreeで解く。SegmentTreeの各ノードにはinc,dec,base,sum,updateを記憶させる。inc,decはその区間に何回1次関数が足されたかを示す。baseは1次関数の切片である。sumはその区間の和で、updateはその区間がxに設定されたため子の区間が無効になったことを示す。ある区間を処理しようとするときは、常に自分の区間の値を子に伝播させ、子の区間から自分のsumを再計算した後にクエリを処理すること。
あとは上記のSegmentTreeを適切に実装すれば各クエリに対してO(logn)で計算可能。