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;}