【算法】线段树||树状数组&&并查集
【题解】修改必须暴力单点修改，然后利用标记区间查询。
优化：一个数经过不断开方很快就会变成1，所以维护区间最大值。
修改时访问到的子树最大值<=1时，该区间就不必修改。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
struct treess{int k,l,r;long long maxs,sum;}t[maxn*];
int n,m;long long a[maxn];
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;
if(l==r)t[k].maxs=t[k].sum=a[l];
else
{
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
t[k].maxs=max(t[k<<].maxs,t[k<<|].maxs);//printf("k=%d maxs=%d",k,t[k].maxs);
t[k].sum=t[k<<].sum+t[k<<|].sum;
}
}
void update(int k,int l,int r)
{
int left=t[k].l,right=t[k].r;
if(t[k].maxs<=)return;
if(left==right)a[left]=floor(sqrt(a[left])),t[k].maxs=t[k].sum=a[left];
else
{
int mid=(left+right)>>;
if(l<=mid)update(k<<,l,r);
if(r>mid)update(k<<|,l,r);
t[k].maxs=max(t[k<<].maxs,t[k<<|].maxs);
t[k].sum=t[k<<].sum+t[k<<|].sum;
}
}
long long ask(int k,int l,int r)
{
int left=t[k].l,right=t[k].r;
if(l<=left&&right<=r)return t[k].sum;
int mid=(left+right)>>;long long ans=;
if(l<=mid)ans=ask(k<<,l,r);
if(r>mid)ans+=ask(k<<|,l,r);
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
scanf("%d",&m);
build(,,n);
for(int i=;i<=m;i++)
{
int k,l,r;
scanf("%d%d%d",&k,&l,&r);
if(l>r)swap(l,r);
if(k==)update(,l,r);
else printf("%lld\n",ask(,l,r));
}
return ;
}
并查集将ai=1的节点并起来，也就是fa[i]表示i后第一个ai≠1的节点，然后用树状数组单点修改区间维护前缀和。
带删除的寻数问题，都可以用类似的并查集套路解决。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;
const ll maxn=;
ll n,m,fa[maxn],a[maxn];
long long c[maxn]; void modify(ll x,ll k){for(ll i=x;i<=n;i+=lowbit(i))c[i]+=k;}
long long ask(ll x){long long as=;for(ll i=x;i>=;i-=lowbit(i))as+=c[i];return as;}
ll find(ll x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
scanf("%lld",&n);
for(ll i=;i<=n;i++)scanf("%lld",&a[i]),modify(i,a[i]);
for(ll i=;i<=n+;i++)fa[i]=i;
scanf("%lld",&m);
for(ll i=;i<=m;i++){
ll k,l,r;
scanf("%lld%lld%lld",&k,&l,&r);
if(l>r)swap(l,r);
if(k==)printf("%lld\n",ask(r)-ask(l-));
else{
for(ll j=l;j<=r;j++){
j=find(j);
if(j<=r){
modify(j,(ll)sqrt(a[j])-a[j]);
a[j]=(ll)sqrt(a[j]);
if(a[j]<=)fa[j]=find(j+);
}
}
}
}
return ;
}