Description
给定 n (n≤105) 个数,已知 n∑i=1ai≤1018。
m (m≤105) 个操作(操作有 2 种):
0 x y
:将区间 [x,y] (1≤x,y≤n) 内的每一个数开 平方根(下取整) 。
1 x y
:询问区间 [x,y] (1≤x,y≤n) 所有数的和(不保证 x≤y,若 x>y,则交换 x,y)。
Source
Solution
前置知识:
线段树
因为要维护区间和,所以我们想到用线段树来维护。
但是会发现懒惰标记不能打,那该怎么办呢?
考虑暴力修改:
a[i] 最大为 1018。
⌊√√√√√√1018⌋=1换言之,
⌊26√1018⌋=1一个数最多开 6 次平方根就会变成 1 。
因为 √1=1,√0=0,
我们只需要维护 区间和 与 区间最大值 即可,
当一个区间的最大值 ≤1 时,我们对这个区间的修改就是无用的,因为无论怎么修改这个数仍是它本身。
而我们对一个数的开平方操作不会超过 6 次,所以时间复杂度仍是 O(nlogn) 。
Code
1 |
|
Be the first person to leave a comment!