自动搬运

查看原文

来自洛谷，原作者为

	XG_Zepto **

搬运于2025-08-24 21:57:00，当前版本为作者最后更新于2018-05-04 20:50:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首发于个人博客。

我不会支持区间开方的数据结构，所以我选择暴力单点修改，树状数组区间查询。

因为1e12的数开方6次就变成了1，所以需要修改的次数实际上很少，用并查集可以跳过小于等于1的数，然后。。。树状数组单点修改即可。没开O2，最慢的点大概就是250ms，还是比较快的。

代码

非常短。。。

树状数组两行搞定，并查集一行搞定。

修改的时候判断一下是不是小于等于1，是的话就更新一下fa数组，具体看一下注释。

#include <bits/stdc++.h>
#define maxn 100100
#define ll long long
using namespace std;
ll tree[maxn*4],a[maxn];int fa[maxn],m,n,q,l,r,t;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}//并查集，路径压缩
void add(int x,ll y){while(x<=n)tree[x]+=y,x+=(x&-x);}
ll qry(int x){ll r=0;while(x)r+=tree[x],x-=(x&-x);return r;}
int main(){
	scanf("%d",&n);for (int i=1;i<=n;i++)
	scanf("%lld",&a[i]),add(i,a[i]),fa[i]=i;scanf("%d",&m);fa[n+1]=n+1;
	while(m--){scanf("%d%d%d",&q,&l,&r);if (l>r) swap(l,r); 
		if (q==1) printf("%lld\n",qry(r)-qry(l-1));
		else for (int i=l;i<=r;add(i,(t=(int)sqrt(a[i]))-a[i]),a[i]=t,fa[i]=(a[i]<=1)?i+1:i,i=(find(i)==i)?i+1:fa[i]);
	}
    //上面这行信息量很大。。。做了单点修改的操作，a数组保存了每个点的实际值，当a[i]<=1的时候，直接跳到下一个点，结束。可以手算一下，就能很快理解了。
}