分块求助,只有50pts!
查看原帖
分块求助,只有50pts!
765376
KingGojianOfYue楼主2024/7/11 17:58
#include<bits/stdc++.h>
using namespace std;
template<typename S>inline S gcd_(S a,S b){return b?gcd_(b,a%b):a;}
int n,block,q,bl[100001],op,l,r;
long long a[100001],sum1[1001],sum2[1001],add[1001],d,num,son,mom,jc;
long long val(int x){
	return a[x]+add[bl[x]];
}
void adds(){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)sum1[bl[i]]-=a[i],sum2[bl[i]]-=a[i]*a[i],a[i]+=d,sum1[bl[i]]+=a[i],sum2[bl[i]]+=a[i]*a[i];
	}else{
		for(int i=l;bl[i]==bl[l];++i)sum1[bl[i]]-=a[i],sum2[bl[i]]-=a[i]*a[i],a[i]+=d,sum1[bl[i]]+=a[i],sum2[bl[i]]+=a[i]*a[i];
		for(int i=r;bl[i]==bl[r];--i)sum1[bl[i]]-=a[i],sum2[bl[i]]-=a[i]*a[i],a[i]+=d,sum1[bl[i]]+=a[i],sum2[bl[i]]+=a[i]*a[i];
		for(int i=-~bl[l];i<bl[r];++i)add[i]+=d;
	}
}
long long get1(){num=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)num+=val(i);
	}else{
		for(int i=l;bl[i]==bl[l];++i)num+=val(i);
		for(int i=r;bl[i]==bl[r];--i)num+=val(i);
		for(int i=-~bl[l];i<bl[r];++i)num+=sum1[i]+add[i]*block;
	}
	return num;
}
long long get2(){num=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)num+=val(i)*val(i);
	}else{
		for(int i=l;bl[i]==bl[l];++i)num+=val(i)*val(i);
		for(int i=r;bl[i]==bl[r];--i)num+=val(i)*val(i);
		for(int i=-~bl[l];i<bl[r];++i)num+=sum2[i]+2*sum1[i]*add[i]+block*add[i]*add[i];
	}
	return num;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;block=sqrt(n);
	for(int i=1;i<=n;++i){
		cin>>a[i];
		bl[i]=(~-i)/block+1;
		sum1[bl[i]]+=a[i],sum2[bl[i]]+=a[i]*a[i];
	}
	while(q--){
		cin>>op>>l>>r;
		if(op==1)cin>>d,adds();
		else if(op==2){
			son=get1(),mom=r-l+1;
			if(son==0){cout<<"0/1\n";continue;}
			jc=gcd_(son,mom);
			cout<<son/jc<<'/'<<mom/jc<<'\n';
		}else{
			son=get2()*(r-l+1)-get1()*get1(),mom=(r-l+1)*(r-l+1);
			if(son==0){cout<<"0/1\n";continue;}
			jc=gcd_(son,mom);
			cout<<son/jc<<'/'<<mom/jc<<'\n';
		}
//		for(int i=1;i<=n;i++)cout<<val(i)<<' ';cout<<endl;
//		for(int i=1;i<=n;i++)cout<<val(i)*val(i)<<' ';cout<<endl;
//		for(int i=1;i<=block;i++)cout<<sum2[i]<<' ';cout<<endl;
	}
	return 0;
}
2024/7/11 17:58
加载中...