Luogu链接：上帝造题的七分钟 2 / 花神游历各国$ {\scr \color {Orchid}{\text{Solution}}} $题目大意

支持两种操作：

  1. 区间开方（向下取整）
  2. 区间求和

分析

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

其实并没有什么思路

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

然后用计算器计算一下，发现$1$~$10^{12}$里的一个数，最多开方$6$次，就能变成$1$

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

所以就很简单啦！维护区间最大值，如果区间内所有数都小于等于$1$，就跳过这段区间

如果大于1，就把区间细分为左儿子与右儿子，重新进行上一步，一直到叶子节点，直接修改即可

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

最后放个代码啦QwQ

Code

#include#define L long longusing 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(x1) 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;}