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
Sample Output
101
11
11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
每个数最多log(logAi)次就会变成0或1，所以每次暴力修改一个单点可行。
但我们怎么找到区间中所有不是0和1的点呢？用并查集维护每个位置下一个合法的位置，细节见代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
typedef long long ll;
inline ll read() {
ll x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,fa[maxn],A[maxn];
inline int findset(int x) {return !fa[x]||x==fa[x]?x:fa[x]=findset(fa[x]);}
ll c[maxn];
void add(int x,ll v) {for(;x<=n;x+=x&-x) c[x]+=v;}
ll sum(int x) {ll ret=;for(;x;x-=x&-x) ret+=c[x];return ret;}
int main() {
n=read();
rep(,n) {
add(i,A[i]=read());
if(A[i]<=) fa[i]=i+;
}
int q=read();
while(q--) {
int t=read(),l=read(),r=read();
if(t==) printf("%lld\n",sum(r)-sum(l-));
else {
for(int i=findset(l);i<=r;i=findset(i+)) {
int t=sqrt(A[i]);
add(i,t-A[i]);A[i]=t;
if(A[i]<=) fa[i]=findset(i+);
}
}
}
return ;
}