玄学求助,分块 70 分求调
查看原帖
玄学求助,分块 70 分求调
707513
LBYYSM_123楼主2023/10/4 15:31
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m,q;
int a[100001];
int st[317],ed[317],bel[100001];
int sums[317],fang[317],mark[317];
inline void work(int &x,int &y){
	int lin=__gcd(x,y);
	x/=lin,y/=lin;
}
void add(int l,int r,int k){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++){
			fang[bel[i]]-=a[i]*a[i];
			a[i]+=k;
			sums[bel[i]]+=k;
			fang[bel[i]]+=a[i]*a[i];
		}
	}
	else{
		for(int i=l;i<=ed[bel[l]];i++){
			fang[bel[i]]-=a[i]*a[i];
			a[i]+=k;
			sums[bel[i]]+=k;
			fang[bel[i]]+=a[i]*a[i];
		}
		for(int i=st[bel[r]];i<=r;i++){
			fang[bel[i]]-=a[i]*a[i];
			a[i]+=k;
			sums[bel[i]]+=k;
			fang[bel[i]]+=a[i]*a[i];
		}
		for(int i=bel[l]+1;i<bel[r];i++)
			mark[i]+=k; 
	}
}
void ave(int l,int r){
	int ans=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++)
			ans+=a[i]+mark[bel[i]];
	}
	else{
		for(int i=l;i<=ed[bel[l]];i++)
			ans+=a[i]+mark[bel[i]];
		for(int i=st[bel[r]];i<=r;i++)
			ans+=a[i]+mark[bel[i]];
		for(int i=bel[l]+1;i<bel[r];i++)
			ans+=sums[i]+mark[i]*(ed[i]-st[i]+1);
	}
	pair<int,int> op={ans,r-l+1};
	if(op.first==0){
		cout<<"0/1\n";
	} 
	else{
		work(op.first,op.second);
		cout<<op.first<<"/"<<op.second<<'\n';
	}
}
pair<int,int> sub(pair<int,int> a,pair<int,int> b){
	return {a.first*b.second-b.first*a.second,a.second*b.second};
}
void fan(int l,int r){
	int fans=0,ans=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++)
			ans+=a[i]+mark[bel[i]],fans+=(a[i]+mark[bel[i]])*(a[i]+mark[bel[i]]);
	}
	else{
		for(int i=l;i<=ed[bel[l]];i++)
			ans+=a[i]+mark[bel[i]],fans+=(a[i]+mark[bel[i]])*(a[i]+mark[bel[i]]);
		for(int i=st[bel[r]];i<=r;i++)
			ans+=a[i]+mark[bel[i]],fans+=(a[i]+mark[bel[i]])*(a[i]+mark[bel[i]]);
		for(int i=bel[l]+1;i<bel[r];i++)
			ans+=sums[i]+mark[i]*(ed[i]-st[i]+1),fans+=fang[i]+2*sums[i]*mark[i]+(ed[i]-st[i]+1)*mark[i]*mark[i];
	}
	pair<int,int> ans1={fans,r-l+1},ans2={ans*ans,(r-l+1)*(r-l+1)};
	pair<int,int> op=sub(ans1,ans2);
	if(op.first==0){
		cout<<"0/1\n";
	} 
	else{
		work(op.first,op.second);
		cout<<op.first<<"/"<<op.second<<'\n';
	}
}
signed main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;q=sqrt(n);
	for(int i=1;i<=n;i++)	
		cin>>a[i];
	for(int i=1;i<=q;i++)
		st[i]=n/q*(i-1)+1,ed[i]=n/q*i;ed[q]=n;
	for(int i=1;i<=q;i++)
		for(int j=st[i];j<=ed[i];j++)
			bel[j]=i,sums[i]+=a[j],fang[i]+=a[j]*a[j];
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int x,y,k;
			cin>>x>>y>>k;
			add(x,y,k);
		}
		else if(opt==2){
			int x,y;
			cin>>x>>y;
			ave(x,y);
		}
		else{
			int x,y;
			cin>>x>>y;
			fan(x,y);
		}
	}
	return 0;
} 
2023/10/4 15:31
加载中...