Luogu链接：上帝造题的七分钟 2 / 花神游历各国

$ {\scr \color {Orchid}{\text{Solution}}} $

题目大意

支持两种操作：

分析

发现线段树容易实现区间求和 
  
  
  
  
  
  
  
 ，考虑区间开方操作

其实并没有什么思路

我们发现了一个很显而易见神奇的事情,如果对一个数开方且下取整 
  
  
  
  
  
  
  
 ，最后这个数一定是$1$

然后用计算器计算一下

 


 


 


 


 


 


 


 
，发现$1$~$10^{12}$里的一个数 
 
 
 
 
 
 
 
，最多开方$6$次 
   
   
   
   
   
   
   
  ，就能变成$1$

所以一共最多只用修改$ 6 \times n$次
 

 

 

 

 

 

 

 
，发现这是可以承受的

所以就很简单啦！维护区间最大值
 

 

 

 

 

 

 

 
，如果区间内所有数都小于等于$1$                ，就跳过这段区间

如果大于1 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
，就把区间细分为左儿子与右儿子















，重新进行上一步                        ，一直到叶子节点 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，直接修改即可

时间复杂度：$O(n log n)$(常数很小)

最后放个代码啦QwQ

Code