/*向下取整smg！
Popoqqq：题目大意：给定一个序列，提供下列操作：
1.将[l.r]区间内每个数a[i]变为sqrt(a[i])
2.查询[l,r]区间的和
根号是不支持区间修改的，于是我们选择单点修改区间查询的树状数组，但是这样是O(n^2)的，怎么办？
我们发现一个数x最多开loglogx次根号就会变为1 也就是一个int范围内的数只要开6次根号就会变为1 于是修改的总时间复杂度为O(nloglogn)
但是单次修改怎么办？我们维护一个并查集，一旦一个数为1或0，我们就把这个位置的father设为它右面的那个位置即可 这样可以均摊O(n)时间找到一个数后面第一个>1的数
*/
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int nmax=1e5+5;
ll sm[nmax];int fa[nmax],a[nmax];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x])
;}
ll query(int x){
ll ans=0;
for(int i=x;i;i-=(i&-i)) ans+=sm[i];
return ans;
}
void update(int x,int n,ll add){
for(int i=x;i<=n;i+=(i&-i)) sm[i]+=add;
}
int main(){
int n=read(),u,v,d;
rep(i,1,n) a[i]=read(),update(i,n,a[i]),fa[i]=i;fa[n+1]=n+1;
int m=read();
rep(i,1,m){
u=read(),v=read(),d=read();
if(u==1) printf("%lld
",query(d)-query(v-1));
else{
int j=v;ll t;
while(j<=d){
j=find(j);if(j>d) break;t=a[j];a[j]=(ll)sqrt(t);update(j,n,a[j]-t);
if(a[j]<=1) fa[j]=find(j+1);++j;
}
}
}
return 0;
}
3211: 花神游历各国
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 2489 Solved: 925
[Submit][Status][Discuss]
Description
Input
Output
每次x=1时，每行一个整数，表示这次旅行的开心度
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9