10pts+RE+WA求调(线段树)
  • 板块P2122 还教室
  • 楼主ZZ_WYZ
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/18 16:21
  • 上次更新2024/11/18 19:09:07
查看原帖
10pts+RE+WA求调(线段树)
623089
ZZ_WYZ楼主2024/11/18 16:21
#include<bits/stdc++.h>
using namespace std;
#define int long long

int tag[1145140],pf[1145140],h[1145140],a[1145140];

void build(int l,int r,int p){
	if(l==r){
		h[p]=a[l];
		pf[p]=a[l]*a[l];
		return;
	}
	int m=(l+r)/2;
	build(l,m,p*2);
	build(m+1,r,p*2+1);
	h[p]=h[p*2]+h[p*2+1];
	pf[p]=pf[p*2]+pf[p*2+1];
}

void sp(int l,int r,int p){
	int m=(l+r)/2;
	if(tag[p]){
		tag[p*2]=tag[p];
		tag[p*2+1]=tag[p];
		pf[p*2]+=(2*h[p*2]*tag[p]*(m-l+1));
		pf[p*2]+=(m-l+1)*tag[p]*tag[p];
		pf[p*2+1]+=(2*h[p*2+1]*tag[p]*(r-m));
		pf[p*2+1]+=(r-m)*tag[p]*tag[p];
		pf[p*2]=abs(pf[p*2]);
		pf[p*2+1]=abs(pf[p*2+1]);
		h[p*2]+=(m-l+1)*tag[p];
		h[p*2+1]+=(r-m)*tag[p];
	}tag[p]=0;
	h[p]=h[p*2]+h[p*2+1];
	pf[p]=pf[p*2]+pf[p*2+1];
	return;
}

void update(int l,int r,int c,int s,int t,int p){
	int m=(s+t)/2;
	if(s>=l&&t<=r){
		tag[p]+=c;
		pf[p]+=(2*h[p]*c*(t-s+1));
		pf[p]+=(t-s+1)*c*c;
		h[p]+=(t-s+1)*c;
		return;
	}
	sp(s,t,p);
	if(l<=m)update(l,r,c,s,m,p*2);
	if(r>m)update(l,r,c,m+1,r,p*2+1);
	h[p]=h[p*2]+h[p*2+1];
	pf[p]=pf[p*2]+pf[p*2+1];
}

int getsumh(int l,int r,int s,int t,int p){
	int m=(s+t)/2;
	if(s>=l&&t<=r){
		return h[p];
	}
	sp(s,t,p);
	int sum=0;
	if(l<=m)sum+=getsumh(l,r,s,m,p*2);
	if(r>m)sum+=getsumh(l,r,m+1,t,p*2+1);
	return sum;
}

int getsumpf(int l,int r,int s,int t,int p){
	int m=(s+t)/2;
	if(s>=l&&t<=r){
		return pf[p];
	}
	sp(s,t,p);
	int sum=0;
	if(l<=m)sum+=getsumpf(l,r,s,m,p*2);
	if(r>m)sum+=getsumpf(l,r,m+1,t,p*2+1);
	return sum;
}
int n,m,op,l,r,d;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		cin>>op>>l>>r;
		if(op==1){
			cin>>d;
			update(l,r,d,1,n,1);
		}
		if(op==2){
			int sum=getsumh(l,r,1,n,1);
			cout<<sum/__gcd(sum,r-l+1)<<"/"<<(r-l+1)/__gcd(sum,r-l+1)<<endl;
		}
		if(op==3){
			int sumh=getsumh(l,r,1,n,1);
			int sumpf=getsumpf(l,r,1,n,1);
			int len=(r-l+1);
			int zuo=len*sumpf;
			int zhong=2*sumh*sumh;
			int you=sumh*sumh;
			if(zuo-zhong+you==0)cout<<"0/1"<<endl;
			else {
				int gcdd=__gcd(zuo-zhong+you,len*len);
				cout<<(zuo-zhong+you)/gcdd<<"/"<<len*len/gcdd<<endl;
			}
			
		}
	}
	return 0;
}
2024/11/18 16:21
加载中...