做题网站推荐: OpenJudge VIJOS CF JOYOI 洛谷 RQNOJ POJ HDU 牛客网 计蒜客 图论工具
本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 网课签到
输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载 实名认证 卡评测举报
原题来自:BZOJ 3211
花神喜欢步行游历各国,顺便虐爆各地竞赛。花神有一条游览路线,它是线型的,也就是说,所有游历国家呈一条线的形状排列,花神对每个国家都有一个喜欢程度(当然花神并不一定喜欢所有国家)。
每一次旅行中,花神会选择一条旅游路线,它在那一串国家中是连续的一段,这次旅行带来的开心值是这些国家的喜欢度的总和,当然花神对这些国家的喜欢程序并不是恒定的,有时会突然对某些国家产生反感,使他对这些国家的喜欢度 δdeltaδ 变为 δsqrt delta√δ(可能是花神虐爆了那些国家的 OI,从而感到乏味)。
现在给出花神每次的旅行路线,以及开心度的变化,请求出花神每次旅行的开心值。
第一行是一个整数 NNN,表示有 NNN 个国家;
第二行有 NNN 个空格隔开的整数,表示每个国家的初始喜欢度 δidelta_iδi;
第三行是一个整数 MMM,表示有 MMM 条信息要处理;
第四行到最后,每行三个整数 x,l,rx,l,rx,l,r,当 x=1x=1x=1 时询问游历国家 lll 到 rrr 的开心值总和,也就是 ∑i=lrδisumlimits_{i=l}^r delta_ii=l∑rδi ,当 x=2x=2x=2 时国家 lll 到 rrr 中每个国家的喜欢度 δidelta_iδi 变为 δisqrt {delta_i}√δi 。
每次 x=1x=1x=1 时,每行一个整数。表示这次旅行的开心度。
4 1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 1 1 4
101 11 11
对于全部数据,1≤n≤105,1≤m≤2×105,1≤l≤r≤n,0≤δi≤1091le nle 10^5,1le mle 2 imes 10^5,1le lle rle n,0le delta_i le 10^91≤n≤105,1≤m≤2×105,1≤l≤r≤n,0≤δi≤109。
注:建议使用 sqrt 函数,且向下取整。
sqrt
一本通提高篇 10128 线段树