hack数据即全都是询问操作,然后就爆了qwq
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long n,a[2000010],m,sqr[2000010],sum[2000010];
bool flag = false;
void build(long long k,long long l,long long r) {
if(l == r) {
sum[k] = a[l];
return;
}
long long mid = (l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
sum[k] = sum[k*2] + sum[k*2+1];
}
void pushdown(long long k,long long l,long long r,long long mid) {
if(sqr[k] == 0) return;
sqr[k*2] += sqr[k];
sqr[k*2+1] +=sqr[k];
sqr[k] = 0;
}
void Add(long long k,long long l,long long r,long long x,long long y,long long v) {
if(l > y || r < x) return;
if(l >= x && r <= y) {
sqr[k] += v;
return;
}
long long mid = (l+r)>>1;
pushdown(k,l,r,mid);
Add(k*2,l,mid,x,y,v);
Add(k*2+1,mid+1,r,x,y,v);
}
void modify(long long k,long long l,long long r,long long x,long long y) {
if(l > y || r < x) return;
long long mid = (l+r)>>1;
if(l == r && l >= x && l <= y) {
if(sum[k] == r-l+1) return;
while(sqr[k] > 0) {
a[l] = sqrt(a[l]);
sum[k] = sqrt(sum[k]);
sqr[k]--;
}
return;
}
pushdown(k,l,r,mid);
modify(k*2,l,mid,x,y);
modify(k*2+1,mid+1,r,x,y);
sum[k] = sum[k*2] + sum[k*2+1];
}
long long query(long long k,long long l,long long r,long long x,long long y) {
if(l > y || r < x) return 0;
if(l >= x && r <= y) {
if(sum[k] == r-l+1) return sum[k];
modify(k,l,r,x,y);
return sum[k];
}
long long mid = (l+r)>>1;
pushdown(k,l,r,mid);
long long res = 0;
res += query(k*2,l,mid,x,y);
res += query(k*2+1,mid+1,r,x,y);
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(long long i = 1;i <= n;i++)
cin >> a[i];
build(1,1,n);
cin >> m;
for(long long i = 1;i <= m;i++) {
long long k,x,y;
cin >> k >> x >> y;
if(x > y) swap(x,y);
if(k == 0) {
Add(1,1,n,x,y,1);
}
else {
cout << query(1,1,n,x,y) << "\n";
}
}
return 0;
}