提交记录

本地对拍小数据能过，但是一交就 WA + TLE ，有无大佬能帮忙调一下代码qwq

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int maxlen=4e2+5;
int n,m,tot,len,bel[maxn],bl[maxlen],br[maxlen],tag0[maxlen],tag1[maxlen];
ll sum[maxlen],a[maxn];
inline void cover(int l,int r){
	for (int i=l;i<=r;i++){
		sum[bel[i]]-=a[i];
		if (a[i]==1) tag1[i]--;
		a[i]=(ll)sqrt(a[i]);
		sum[bel[i]]+=a[i];
		if (a[i]==1) tag1[i]++;
	}
}
inline void update(int l,int r){
	int nl=bel[l],nr=bel[r];
	if (nl==nr){
		cover(l,r);
		return ;
	}
	if (l!=bl[nl]) nl++;
	if (r!=br[nr]) nr--;
	for (int i=nl;i<=nr;i++){
		if (tag0[i]+tag1[i]==br[i]-bl[i]+1) continue;
		cover(bl[i],br[i]);
	}
	if (l!=bl[nl]) cover(l,bl[nl]-1);
	if (r!=br[nr]) cover(br[nr]+1,r);
}
inline ll query(int l,int r){
	int nl=bel[l],nr=bel[r];
	if (nl==nr){
		ll res=0;
		for (int i=l;i<=r;i++) res+=a[i];
		return res;
	}
	if (l!=bl[nl]) nl++;
	if (r!=br[nr]) nr--;
	ll ans=0;
	for (int i=nl;i<=nr;i++) ans+=sum[i];
	if (l!=bl[nl]) for (int i=l;i<bl[nl];i++) ans+=a[i];
	if (r!=br[nr]) for (int i=r;i>br[nr];i--) ans+=a[i];
	return ans; 
}
int main(){
	//freopen("data-P4145.txt","r",stdin);
	//freopen("P4145.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	len=sqrt(n);
	tot=(n-1)/len+1;
	for (int i=1;i<=tot;i++){
		bl[i]=(i-1)*len+1;
		br[i]=i*len;
		for (int j=bl[i];j<=br[i];j++){
			bel[j]=i;
			sum[i]+=a[j];			
			if (!a[j]) tag0[i]++;
			if (a[j]==1) tag1[i]++;
		} 
	}
	scanf("%d",&m);
	for (int i=1,opt,x,y;i<=m;i++){
		scanf("%d%d%d",&opt,&x,&y);
		if (x>y) swap(x,y);
		if (!opt) update(x,y);
		else printf("%lld\n",query(x,y));
	}
	return 0;
}