哇噻!添柴重大升级!
新版添柴更名啊哈添柴,网址搬家至acoj.com 从2019年3月16日起,老版添柴的使用数据将不同 步到新版啊哈添柴。建议点击下方按钮体验新版本哦!
就算丢失数据也要留在旧版哼!
题目描述(ID:12434)
标题: 啊哈沃德游历各国
标签: 数据结构 线段树
详情:
啊哈沃德喜欢步行游历各国,顺便虐爆各地竞赛。啊哈沃德有一条游览路线,它是线型的,也就是说,所有游历国家呈一条线的形状排列,啊哈沃德对每个国家都有一个喜欢程度(当然啊哈沃德并不一定喜欢所有国家)。
每一次旅行中,啊哈沃德会选择一条旅游路线,它在那一串国家中是连续的一段,这次旅行带来的开心值是这些国家的喜欢度的总和,当然啊哈沃德对这些国家的喜欢程序并不是恒定的,有时会突然对某些国家产生反感,使他对这些国家的喜欢度 δ 变为 sqrt(δ)​(可能是啊哈沃德虐爆了那些国家的 OI,从而感到乏味)。
现在给出啊哈沃德每次的旅行路线,以及开心度的变化,请求出啊哈沃德每次旅行的开心值。
输入格式:
第一行是一个整数 N,表示有 N 个国家;
第二行有 N 个空格隔开的整数,表示每个国家的初始喜欢度 a[i];
第三行是一个整数 M,表示有 M 条信息要处理;
第四行到最后,每行三个整数 x,l,r,当 x=1 时询问游历国家 l 到 r 的开心值总和,也就是 a[l]+a[l+1]+...+a[r],当 x=2 时国家 l 到 r 中每个国家的喜欢度 a[i]变为sqrt(a[i])
​	
 
​
输出格式:
每次 x=1 时,每行一个整数。表示这次旅行的开心度。
提示: 对于全部数据,1≤n≤10^5,1≤m≤2×10^5,1≤l≤r≤n,0≤a[i]≤10^9。
注:建议使用 sqrt 函数,且向下取整。
样例:

输入

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

输出

101
11
11
登录并解答