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;
}