想改天把花神题都做了qwqwqwq
开根号不具有可加性。。所以我们得暴力更改。。也就是说要叶子结点一个一个修改,然后往上面合并。。。。
但是这样为什么不会T?因为对于一个数,它不需要几次开根号就会变成0或者1,又因为1开根号还是1,0开根号还是0,所以开了就跟没开一样。。。
所以我们记录一个maxx值,如果当前区间最大数都不超过1了,就放过这个区间吧。。。。
代码如下:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define MAXN 100010
using namespace std;
int n,m;
long long a[MAXN];
struct Node{int l,r;long long sum,maxx;}t[MAXN<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void push_up(int x)
{
t[x].sum=t[ls(x)].sum+t[rs(x)].sum;
t[x].maxx=max(t[ls(x)].maxx,t[rs(x)].maxx);
}
inline void build(int x,int l,int r)
{
t[x].l=l,t[x].r=r;
if(l==r) {t[x].sum=t[x].maxx=a[l];return;}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
push_up(x);
}
inline void update(int x,int ll,int rr)
{
if(t[x].maxx<=1) return;
int l=t[x].l,r=t[x].r;
if(l==r)
{
t[x].sum=t[x].maxx=sqrt(t[x].sum);
return;
}
int mid=(l+r)>>1;
if(ll<=mid) update(ls(x),ll,rr);
if(mid<rr) update(rs(x),ll,rr);
push_up(x);
}
inline long long query(int x,int ll,int rr)
{
int l=t[x].l,r=t[x].r;
if(ll<=l&&r<=rr) return t[x].sum;
int mid=(l+r)>>1;
long long cur_ans=0;
if(ll<=mid) cur_ans+=query(ls(x),ll,rr);
if(mid<rr) cur_ans+=query(rs(x),ll,rr);
return cur_ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
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 op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(l>r) swap(l,r);
if(op==2) update(1,l,r);
else printf("%lld\n",query(1,l,r));
}
return 0;
}
原文:https://www.cnblogs.com/fengxunling/p/10501974.html