思路
考虑每一条边的贡献,然后推式子
\[
\begin{align}&\sum_{i}V_i\times(R-i+1)\times(i-L+1)\\=&\sum_{i}V_i\left[(Ri-i^2+i)-(RL-iL+L)+(R-i+1)\right]\\=&\sum_{i}V_i\left[Ri-i^2+i-RL+Li-L+R-i+1\right]\\=&\sum_{i}Vi\left[(Ri+Li)-i^2-RL+(R-L+1)\right]\\=&\sum_{i}(Ri+Li)V_i-\sum_{i}i^2V_i-\sum_{i}RLV_i+\sum_{i}(R-L+1)V_i\\=&(R+L)\sum_{i}iVi-\sum_{i}i^2V_i-RL\sum_{i}V_i+(R-L+1)\sum_{i}V_i\\=&(R+L)\sum_iiV_i-\sum_ii^2V_i+(R-L+1-RL)\sum_{i}V_i\end{align}
\]
然后用线段树维护就好了
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MAXN = 100100;
namespace Seg1{//v_i
int seg[MAXN<<2]={},tag[MAXN<<2]={};
void pushup(int o){
seg[o]=seg[o<<1]+seg[o<<1|1];
}
void build(int l,int r,int o,int *a){
if(l==r){
seg[o]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1,a);
build(mid+1,r,o<<1|1,a);
pushup(o);
}
void pushdown(int o,int ln,int rn){
if(tag[o]){
seg[o<<1]+=tag[o]*ln;
seg[o<<1|1]+=tag[o]*rn;
tag[o<<1]+=tag[o];
tag[o<<1|1]+=tag[o];
tag[o]=0;
}
}
void add(int L,int R,int l,int r,int o,int c){
if(L<=l&&r<=R){
seg[o]+=c*(r-l+1);
tag[o]+=c;
return;
}
int mid=(l+r)>>1;
pushdown(o,mid-l+1,r-mid);
if(L<=mid)
add(L,R,l,mid,o<<1,c);
if(R>mid)
add(L,R,mid+1,r,o<<1|1,c);
pushup(o);
}
int query(int L,int R,int l,int r,int o){
if(L<=l&&r<=R){
return seg[o];
}
int mid=(l+r)>>1,ans=0;
pushdown(o,mid-l+1,r-mid);
if(L<=mid)
ans+=query(L,R,l,mid,o<<1);
if(R>mid)
ans+=query(L,R,mid+1,r,o<<1|1);
return ans;
}
};
namespace Seg2{//v_i*i
int seg[MAXN<<2]={},tag[MAXN<<2]={};
int sum(int l,int r){
return (l+r)*(r-l+1)/2;
}
void pushup(int o){
seg[o]=seg[o<<1]+seg[o<<1|1];
}
void build(int l,int r,int o,int *a){
if(l==r){
seg[o]=a[l]*l;
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1,a);
build(mid+1,r,o<<1|1,a);
pushup(o);
}
void pushdown(int o,int lx,int rx){
if(tag[o]){
int mid=(lx+rx)>>1;
seg[o<<1]+=tag[o]*sum(lx,mid);
seg[o<<1|1]+=tag[o]*sum(mid+1,rx);
tag[o<<1]+=tag[o];
tag[o<<1|1]+=tag[o];
tag[o]=0;
}
}
void add(int L,int R,int l,int r,int o,int c){
if(L<=l&&r<=R){
seg[o]+=c*sum(l,r);
tag[o]+=c;
return;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(L<=mid)
add(L,R,l,mid,o<<1,c);
if(R>mid)
add(L,R,mid+1,r,o<<1|1,c);
pushup(o);
}
int query(int L,int R,int l,int r,int o){
if(L<=l&&r<=R){
return seg[o];
}
int mid=(l+r)>>1,ans=0;
pushdown(o,l,r);
if(L<=mid)
ans+=query(L,R,l,mid,o<<1);
if(R>mid)
ans+=query(L,R,mid+1,r,o<<1|1);
return ans;
}
};
namespace Seg3{//vi*i^2
int seg[MAXN<<2]={},tag[MAXN<<2]={};
void pushup(int o){
seg[o]=seg[o<<1]+seg[o<<1|1];
}
int f(int x){
return (2*x+1)*(x+1)*x/6;
}
int sum(int l,int r){
return f(r)-f(l-1);
}
void build(int l,int r,int o,int *a){
if(l==r){
seg[o]=a[l]*l*l;
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1,a);
build(mid+1,r,o<<1|1,a);
pushup(o);
}
void pushdown(int o,int lx,int rx){
if(tag[o]){
int mid=(lx+rx)>>1;
seg[o<<1]+=tag[o]*sum(lx,mid);
seg[o<<1|1]+=tag[o]*sum(mid+1,rx);
tag[o<<1]+=tag[o];
tag[o<<1|1]+=tag[o];
tag[o]=0;
}
}
void add(int L,int R,int l,int r,int o,int c){
if(L<=l&&r<=R){
seg[o]+=c*sum(l,r);
tag[o]+=c;
return;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(L<=mid)
add(L,R,l,mid,o<<1,c);
if(R>mid)
add(L,R,mid+1,r,o<<1|1,c);
pushup(o);
}
int query(int L,int R,int l,int r,int o){
if(L<=l&&r<=R){
return seg[o];
}
int mid=(l+r)>>1,ans=0;
pushdown(o,l,r);
if(L<=mid)
ans+=query(L,R,l,mid,o<<1);
if(R>mid)
ans+=query(L,R,mid+1,r,o<<1|1);
return ans;
}
void debug(int l,int r,int o){
printf("%lld %lld %lld %lld %lld\n",l,r,o,seg[o],tag[o]);
if(l==r)
return;
int mid=(l+r)>>1;
debug(l,mid,o<<1);
debug(mid+1,r,o<<1|1);
}
};
int gcd(int a,int b){
return (b==0)?a:gcd(b,a%b);
}
int a[MAXN]={0},n,m;
using namespace Seg1;
using namespace Seg2;
using namespace Seg3;
signed main(){
scanf("%lld %lld",&n,&m);
n--;
Seg1::build(1,n,1,a);
Seg2::build(1,n,1,a);
Seg3::build(1,n,1,a);
for(int i=1;i<=m;i++){
char c=getchar();
while(c!='C'&&c!='Q')
c=getchar();
if(c=='C'){
int l,r,val;
scanf("%lld %lld %lld",&l,&r,&val);
r--;
Seg1::add(l,r,1,n,1,val);
Seg2::add(l,r,1,n,1,val);
Seg3::add(l,r,1,n,1,val);
//Seg3::debug(1,n,1);
}
else{
int l,r;
scanf("%lld %lld",&l,&r);
r--;
int sum1=Seg1::query(l,r,1,n,1);
int sum2=Seg2::query(l,r,1,n,1);
int sum3=Seg3::query(l,r,1,n,1);
//Seg3::debug(1,n,1);
int ans=sum1*(r-l+1-r*l)+(r+l)*sum2-sum3;
// printf("sum1=%lld sum2=%lld sum3=%lld %lld\n",sum1,sum2,sum3,ans);
int t=(r-l+1)*(r-l+2)/2;
int Gcd=gcd(t,ans);
printf("%lld/%lld\n",ans/Gcd,t/Gcd);
}
}
return 0;
}