样例不过求调
查看原帖
样例不过求调
530180
KingPowers楼主2022/7/29 20:09

RT,瞎打的线段树,感觉写得还算清晰,希望有dl能帮蒟蒻调一调QAQ

#include<bits/stdc++.h>
#define int long long
#define inf 0x7fffffff
#define maxn 100005<<2
#define ls(k) k<<1
#define rs(k) k<<1|1
using namespace std;
struct node{
	int sum1,sum2,sum3,sum4,sum5,lazy;
}v[maxn];
int n,m;
char opt;
inline int read(){
	int ans=0,flag=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flag=-1;ch=getchar();}
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans*flag;
}
inline int gcd(int a,int b){
	return b==0?(a):gcd(b,a%b);
}
inline void pushup(int k){
	v[k].sum1=v[ls(k)].sum1+v[rs(k)].sum1;
	v[k].sum2=v[ls(k)].sum2+v[rs(k)].sum2;
	v[k].sum3=v[ls(k)].sum3+v[rs(k)].sum3;
}
inline void build(int l,int r,int k){
	if(l==r){
		v[k].sum4=l;
		v[k].sum5=l*l;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls(k));build(mid+1,r,rs(k));
	v[k].sum4=v[ls(k)].sum4+v[rs(k)].sum4;
	v[k].sum5=v[ls(k)].sum5+v[rs(k)].sum5;
}
inline void pushdown(int l,int r,int k){
	if(v[k].lazy){
		int mid=(l+r)>>1,w=v[k].lazy;
		v[k].lazy=0;
		v[ls(k)].lazy+=w;v[rs(k)].lazy+=w;
		v[ls(k)].sum1+=w*(mid-l+1);v[rs(k)].sum1=w*(r-mid);
		v[ls(k)].sum2+=w*v[ls(k)].sum4;v[rs(k)].sum2+=w*v[rs(k)].sum4;
		v[ls(k)].sum3+=w*v[ls(k)].sum5;v[rs(l)].sum3+=w*v[rs(k)].sum5;
	}
}
inline void add(int l,int r,int now_l,int now_r,int k,int w){
	//printf("now_l:%lld now_r:%lld\n",now_l,now_r);
	if(now_l>r||now_r<l){
		return;
	}
	if(now_l>=l&&now_r<=r){
		v[k].sum1+=w*(now_r-now_l+1);
		v[k].sum2+=w*v[k].sum4;
		v[k].sum3+=w*v[k].sum5;
		v[k].lazy+=w;
		return;
	}
	pushdown(now_l,now_r,k);
	int mid=(now_l+now_r)>>1;
	add(l,r,now_l,mid,ls(k),w);
	add(l,r,mid+1,now_r,rs(k),w);
	pushup(k);
}
inline void query(int l,int r,int now_l,int now_r,int k,int& sum1,int& sum2,int& sum3){
	if(now_l>r||now_r<l){
		return;
	}
	if(now_l>=l&&now_r<=r){
		sum1+=v[k].sum1;
		sum2+=v[k].sum2;
		sum3+=v[k].sum3;
		return;
	}
	pushdown(now_l,now_r,k);
	int mid=(now_l+now_r)>>1;
	query(l,r,now_l,mid,ls(k),sum1,sum2,sum3);
	query(l,r,mid+1,now_r,rs(k ),sum1,sum2,sum3);
}
signed main(){
	int n=read(),m=read();
	build(1,n,1);
	for(int i=1,l,r,c;i<=m;i++){
		cin>>opt;
		if(opt=='C'){
			l=read(),r=read()-1,c=read();
			add(l,r,1,n,1,c);
		} else{
			l=read(),r=read()-1;
			int s1=0,s2=0,s3=0;
			query(l,r,1,n,1,s1,s2,s3);
			int a=(r-l+1-r*l)*s1+(r+l)*s2-s3,b=(r-l+2)*(r-l+1)/2,g=gcd(a,b);
            printf("%lld/%lld\n",a/g,b/g);
		}
	}
	return 0;
}

2022/7/29 20:09
加载中...