分块60pts WA on#3 #5 #8 #9 悬关求调

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
using namespace std;
const int cxk=1e5+5;
int klt[cxk],krt[cxk],beto[cxk],n,a[cxk],tree[cxk],m;
bool vis[cxk];
inline void split()
{
	int len=sqrt(n),k=n/len+bool(n%len);
	for(int i=1;i<=k;i++)
		klt[i]=len*(i-1)+1,krt[i]=len*i;
	krt[k]=n;
	for(int i=1;i<=k;i++)
		for(int j=klt[i];j<=krt[i];j++)
			beto[j]=i;
}
void update2(int x,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tree[i]+=val;
}
int query(int x)
{
	int sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum+=tree[i];
	return sum;
}
void update(int lt,int rt)
{
	for(int i=beto[lt]+1;i<beto[rt];i++)
	{
		if(vis[i])
			continue;
		bool flag=1;
		for(int j=klt[i];j<=krt[i];j++)
		{
			int lst=a[j];
			a[j]=sqrt(a[j]),flag&=(a[j]==1);
			update2(j,a[j]-lst);
		}
		vis[i]=flag;
	}
	for(int i=lt;i<=krt[beto[lt]];i++)
	{
		int lst=a[i];
		a[i]=sqrt(a[i]);
		update2(i,a[i]-lst);
	}
	for(int i=rt;i>=klt[beto[rt]];i--)
	{
		int lst=a[i];
		a[i]=sqrt(a[i]);
		update2(i,a[i]-lst);
	}
}
signed main()
{
	freopen("114.txt","r",stdin);
	freopen("114.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,x;i<=n;i++)
		cin>>a[i],update2(i,a[i]);
	cin>>m;
	split();
	for(int opt,x,y;m--;)
	{
		cin>>opt>>x>>y;
		if(x>y)
			swap(x,y);
		if(opt==0)
			update(x,y);
		else
			if(query(y)-query(x-1)==0)
				cout<<m<<"\n";
			else 
				cout<<query(y)-query(x-1)<<"\n";
	}
	return 0;
}