根号大法好!
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Background
我出的题肯定水!
Description
给定一个序列\(a_0\),\(a_1\),...\(a_{n-1}\)
给定m个询问和修改操作,操作包含\(i,l,r\)
\(i=0\)为修改操作,代表将区间\([l,r]\)之间的数字开根号向下取整
\(i=1\)为查询操作,代表查询区间\([l,r]\)的数字和
数据范围\(0<n,m<=1e5,a_i>=0,0<=l<=r<n,\sum{a_i}\)在long long范围内
单个ai的值不超过int
Format
Input
第一行一个数字\(n\)
第二行\(n\)个数字,包含\(a_0...a_{n-1}\)
第三行一个数字m,代表操作个数
接下来\(m\)行,每行三个数字\(i,l,r\)。
Output
对于每个询问,输出一个答案,答案对\(1e9+7\)取模
Sample 1
Input
3
9 9 9
1
1 0 2
Output
27
Limitation
1s, 64*1024KiB for each test case.
Source
Vijos Original