02221HAOI高速公路求看看哪里错了(样例过了)
查看原帖
02221HAOI高速公路求看看哪里错了(样例过了)
211960
nzynzy楼主2021/10/15 18:35
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+20;
typedef long long LL;
struct node{
	LL l,r;
	LL sum1,sum2,sum3,sum4,sum5,add;
}tr[N<<2];
LL n,m;
LL sum11,sum22,sum33,k;
LL gcd(LL a,LL b){
	return b?gcd(b,a%b):a;
}
void pushup(int x){
	tr[x].sum1=tr[x<<1].sum1+tr[x<<1|1].sum1;
	tr[x].sum2=tr[x<<1].sum2+tr[x<<1|1].sum2;
	tr[x].sum3=tr[x<<1].sum3+tr[x<<1|1].sum3;
}
void pushdown(int x){
	if(tr[x].add){
		tr[x<<1].sum1+=(tr[x<<1].r-tr[x<<1].l+1)*tr[x].add;
		tr[x<<1|1].sum1+=(tr[x<<1|1].r-tr[x<<1|1].l+1)*tr[x].add;
		tr[x<<1].sum2+=tr[x<<1].sum4*tr[x].add;
		tr[x<<1|1].sum2+=tr[x<<1|1].sum4*tr[x].add;
		tr[x<<1].sum3+=tr[x<<1].sum5*tr[x].add;
		tr[x<<1|1].sum3+=tr[x<<1|1].sum5*tr[x].add;
		tr[x<<1].add+=k;
		tr[x<<1|1].add+=k;
		tr[x].add=0;
	}
}
void build(int x,int l,int r){
	tr[x].l=l,tr[x].r=r;
	if(l==r){
		tr[x].sum4=l;
		tr[x].sum5=l*l;
		return;	
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	tr[x].sum4=tr[x<<1].sum4+tr[x<<1|1].sum4;
	tr[x].sum5=tr[x<<1].sum5+tr[x<<1|1].sum5;
}
void modify(int x,int l,int r,LL k){
	if(tr[x].l>=l&&tr[x].r<=r){
		pushdown(x);
		tr[x].add+=k;
		tr[x].sum1+=(tr[x].r-tr[x].l+1)*k;
		tr[x].sum2+=tr[x].sum4*k;
		tr[x].sum3+=tr[x].sum5*k;
		return;
	}
	pushdown(x);
	int mid=tr[x].l+tr[x].r>>1;
	if(l<=mid)modify(x<<1,l,r,k);
	if(r>mid)modify(x<<1|1,l,r,k);
	pushup(x);
	return;
}
void query(int x,int l,int r){
	if(tr[x].l>=l&&tr[x].r<=r){
		pushdown(x);
		sum11+=tr[x].sum1;
		sum22+=tr[x].sum2;
		sum33+=tr[x].sum3;
		return;
	}
	pushdown(x);
	int mid=tr[x].l+tr[x].r>>1;
	if(l<=mid)query(x<<1,l,r);
	if(r>mid)query(x<<1|1,l,r);
	return;
}
int main(){
	cin>>n>>m;
	build(1,1,n);
	while(m--){
		char op[2];
		LL l,r;
		scanf("%s%lld%lld",&op,&l,&r);
		r--;
		if(op[0]=='C'){
			scanf("%lld",&k);
			modify(1,l,r,k);
		}else{
			LL ans=0;
			sum11=sum22=sum33=0;
			query(1,l,r);
			ans=sum11*(r-l+1-l*r)+sum22*(r+l)-sum33;
			LL di=(r-l+2)*(r-l+1)/2;
			LL d=gcd(ans,di);
			printf("%lld/%lld\n",ans/d,di/d);
		}
	}
	return 0;
}
2021/10/15 18:35
加载中...