SPOJ GSS4&&hdu 4027 Can you answer these queries IV(线段树区间开方)

You are given a sequence A of N(N <= 100,000) positive integers. There sum will be less than 1018. On this sequence you have to apply M (M <= 100,000) operations:

(A) For given x,y, for each elements between the x-th and the y-th ones (inclusively, counting from 1), modify it to its positive square root (rounded down to the nearest integer).

(B) For given x,y, query the sum of all the elements between the x-th and the y-th ones (inclusively, counting from 1) in the sequence.

Input

Multiple test cases, please proceed them one by one. Input terminates by EOF.

For each test case:

The first line contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in the form “i x y”.i=0 denotes the modify operation, i=1 denotes the query operation.

Output

For each test case:

Output the case number (counting from 1) in the first line of output. Then for each query, print an integer as the problem required.

Print an blank line after each test case.

See the sample output for more details.

Example

线段树处理区间开方。首先因为题目中数字最多才2^64,也就是最多开方7次就会变成1,那么在进行开方的话是毫无意义的。那么我们可以用一个数组表示当前区间到底是不是全部为1,如果是的话,那么我们就不用再继续往下更新区间了。然后因为我们每次更新都是对区间中的每个数开方,所以每个数最多开方7次,就不用再做任何开方的操作了。所以复杂度大概就是O(7*n)这个样子了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注