Luogu链接：上帝造题的七分钟 2 / 花神游历各国
$ {\scr \color {Orchid}{\text{Solution}}} $
题目大意
支持两种操作：
- 区间开方（向下取整）
- 区间求和
分析
发现线段树容易实现区间求和，考虑区间开方操作
其实并没有什么思路
我们发现了一个很显而易见神奇的事情,如果对一个数开方且下取整，最后这个数一定是$1$
然后用计算器计算一下，发现$1$~$10^{12}$里的一个数，最多开方$6$次，就能变成$1$
所以一共最多只用修改$ 6 \times n$次，发现这是可以承受的
所以就很简单啦！维护区间最大值，如果区间内所有数都小于等于$1$，就跳过这段区间
如果大于1，就把区间细分为左儿子与右儿子，重新进行上一步，一直到叶子节点，直接修改即可
时间复杂度：$O(n log n)$(常数很小)
最后放个代码啦QwQ
Code
#include<bits/stdc++.h> #define L long long using namespace std; L a[500005],summ[2000005],maxx[2000005]; void build(int o,int l,int r) { if(l==r) { summ[o]=maxx[o]=a[l]; return; } int mid=(l+r)>>1; build(o+o,l,mid); build(o+o+1,mid+1,r); summ[o]=summ[o+o]+summ[o+o+1]; maxx[o]=max(maxx[o+o],maxx[o+o+1]); } L x,y; void quxiu(int o,int l,int r) { if(l==r) { summ[o]=sqrt(summ[o]); maxx[o]=sqrt(maxx[o]); return; } int mid=(l+r)>>1; if(x<=mid && maxx[o+o]>1) quxiu(o+o,l,mid); if(y>mid && maxx[o+o+1]>1) quxiu(o+o+1,mid+1,r); summ[o]=summ[o+o]+summ[o+o+1]; maxx[o]=max(maxx[o+o],maxx[o+o+1]); } L ans; void qucha(int o,int l,int r) { if(x<=l && r<=y) { ans+=summ[o]; return; } int mid=(l+r)>>1; if(x<=mid) qucha(o+o,l,mid); if(y>mid) qucha(o+o+1,mid+1,r); } int main() { int n,m; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { int k; scanf("%d%lld%lld",&k,&x,&y); if(x>y) swap(x,y); if(k==0) quxiu(1,1,n); else { qucha(1,1,n); printf("%lld\n",ans); ans=0; } }
return 0; }