0pts能过样例求调
查看原帖
0pts能过样例求调
477821
toolong114514楼主2024/6/28 10:49
#include<iostream>
using namespace std;
#define int long long
const int N=1e5+10;
struct ccf{
	__int128 lsum,rsum,all,sum,lgt;
	friend ccf operator+(ccf pre,ccf nxt){
		ccf tmp;
		tmp.all=pre.rsum*nxt.lsum+pre.all+nxt.all;
		tmp.lsum=pre.lsum+pre.sum*nxt.lgt+nxt.lsum;
		tmp.rsum=pre.rsum*pre.lgt+nxt.sum+nxt.rsum;
		tmp.sum=pre.sum+nxt.sum;
		tmp.lgt=pre.lgt+nxt.lgt;
		return tmp;
	}
};
struct node{
	int l,r,laz;
	ccf zyh;
}tree[4*N];
void push_up(int pos){
	tree[pos].zyh=tree[pos*2].zyh+tree[pos*2+1].zyh;
}
void build(int pos,int lft,int rgt){
	tree[pos].l=lft;
	tree[pos].r=rgt;
	tree[pos].zyh.lgt=rgt-lft+1;
	if(lft==rgt) return;
	int mid=(lft+rgt)/2;
	build(pos*2,lft,mid);
	build(pos*2+1,mid+1,rgt);
	push_up(pos);
}
int sum_qz[N],sum[N];
void push_down(int pos){
	int llen=tree[pos*2].r-tree[pos*2].l+1,rlen=tree[pos*2+1].r-tree[pos*2+1].l+1;
	tree[pos*2].zyh.lsum+=(1+llen)*llen/2*tree[pos].laz;
	tree[pos*2].zyh.rsum+=(1+llen)*llen/2*tree[pos].laz;
	tree[pos*2].zyh.all+=sum_qz[llen]*tree[pos].laz;
	tree[pos*2].zyh.sum+=llen*tree[pos].laz;
	
	tree[pos*2+1].zyh.lsum+=(1+rlen)*rlen/2*tree[pos].laz;
	tree[pos*2+1].zyh.rsum+=(1+rlen)*rlen/2*tree[pos].laz;
	tree[pos*2+1].zyh.all+=sum_qz[rlen]*tree[pos].laz;
	tree[pos*2+1].zyh.sum+=rlen*tree[pos].laz;

	tree[pos*2].laz+=tree[pos].laz;
	tree[pos*2+1].laz+=tree[pos].laz;
	tree[pos].laz=0;
}
void upd(int pos,int lft,int rgt,int x){
	if(rgt<tree[pos].l||tree[pos].r<lft) return;
	if(lft<=tree[pos].l&&tree[pos].r<=rgt){
		int len=tree[pos].r-tree[pos].l+1;
		tree[pos].zyh.lsum+=(1+len)*len/2*x;
		tree[pos].zyh.rsum+=(1+len)*len/2*x;
		tree[pos].zyh.all+=sum_qz[len]*x;
		tree[pos].zyh.sum+=len*x;
		tree[pos].laz+=x;
		return;
	}
	push_down(pos);
	upd(pos*2,lft,rgt,x);
	upd(pos*2+1,lft,rgt,x);
	push_up(pos);
}
ccf ask(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].zyh;
	int mid=(tree[pos].l+tree[pos].r)/2;
	push_down(pos);
	if(rgt<=mid) return ask(pos*2,lft,rgt);
	else if(mid<lft) return ask(pos*2+1,lft,rgt);
	else return ask(pos*2,lft,rgt)+ask(pos*2+1,lft,rgt);
}
__int128 gcd(__int128 a,__int128 b){
	return (b==0)?(a):(gcd(b,a%b));
}
int n,m;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		sum_qz[i]=i*(i+1)*(i+2)/6;
		sum[i]=i*(i+1)/2;
		//cout<<sum[i]<<" ";
	}
	//cout<<endl;
	build(1,1,n-1);
	while(m--){
		char op;
		int ll,rr,vv;
		cin>>op>>ll>>rr;
		if(op=='C'){
			cin>>vv;
			upd(1,ll,rr-1,vv);
		}else{
			ccf ans=ask(1,ll,rr-1);
			__int128 kk=gcd(ans.all,sum[rr-ll]);
			//cout<<ans.lsum<<endl;
			cout<<(int)(ans.all/kk)<<"/"<<(int)(sum[rr-ll]/kk)<<'\n';
		}
	}
	return 0;
}
2024/6/28 10:49
加载中...