題目 2456:
信息學奧賽一本通T1550-花神游歷各國
時間限制: 2s
內(nèi)存限制: 192MB 提交: 23 解決: 10
題目描述
原題來自：BZOJ 3211
花神喜歡步行游歷各國，順便虐爆各地競賽?；ㄉ裼幸粭l游覽路線，它是線型的，也就是說，所有游歷國家呈一條線的形狀排列，花神對每個國家都有一個喜歡程度（當然花神并不一定喜歡所有國家）。
每一次旅行中，花神會選擇一條旅游路線，它在那一串國家中是連續(xù)的一段，這次旅行帶來的開心值是這些國家的喜歡度的總和，當然花神對這些國家的喜歡程序并不是恒定的，有時會突然對某些國家產(chǎn)生反感，使他對這些國家的喜歡度 δ 變?yōu)?
（可能是花神虐爆了那些國家的 OI，從而感到乏味）。
現(xiàn)在給出花神每次的旅行路線，以及開心度的變化，請求出花神每次旅行的開心值。
花神喜歡步行游歷各國，順便虐爆各地競賽?；ㄉ裼幸粭l游覽路線，它是線型的，也就是說，所有游歷國家呈一條線的形狀排列，花神對每個國家都有一個喜歡程度（當然花神并不一定喜歡所有國家）。
每一次旅行中，花神會選擇一條旅游路線，它在那一串國家中是連續(xù)的一段，這次旅行帶來的開心值是這些國家的喜歡度的總和，當然花神對這些國家的喜歡程序并不是恒定的，有時會突然對某些國家產(chǎn)生反感，使他對這些國家的喜歡度 δ 變?yōu)?
（可能是花神虐爆了那些國家的 OI，從而感到乏味）。現(xiàn)在給出花神每次的旅行路線，以及開心度的變化，請求出花神每次旅行的開心值。
輸入格式
第一行是一個整數(shù) N，表示有 N 個國家；
第二行有 N 個空格隔開的整數(shù)，表示每個國家的初始喜歡度 δi ；
第三行是一個整數(shù) M，表示有 M 條信息要處理；
第四行到最后，每行三個整數(shù) x,l,r，當 x=1 時詢問游歷國家 l 到 r 的開心值總和，就是
，當 x=2 時國家 l 到 r 中每個國家的喜歡度 δi變?yōu)?nbsp;
。
第二行有 N 個空格隔開的整數(shù)，表示每個國家的初始喜歡度 δi ；
第三行是一個整數(shù) M，表示有 M 條信息要處理；
第四行到最后，每行三個整數(shù) x,l,r，當 x=1 時詢問游歷國家 l 到 r 的開心值總和，就是
，當 x=2 時國家 l 到 r 中每個國家的喜歡度 δi變?yōu)?nbsp; 。輸出格式
每次 x=1 時，每行一個整數(shù)。表示這次旅行的開心度。
樣例輸入
4 1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 1 1 4
樣例輸出
101 11 11
提示
數(shù)據(jù)范圍與提示：
對于全部數(shù)據(jù)，1≤n≤105,1≤m≤2×105,1≤l≤r≤n,0≤δi≤109 。
注：建議使用 sqrt 函數(shù)，且向下取整。
對于全部數(shù)據(jù)，1≤n≤105,1≤m≤2×105,1≤l≤r≤n,0≤δi≤109 。
注：建議使用 sqrt 函數(shù)，且向下取整。