题面
很套路的拆式子然后线段树上维护区间和的题。一般都是把式子拆成区间内几个形如(sum i*a_i, sum i^2 * a_i)的式子相加减的形式。
考虑一次询问[l,r]的答案怎么算：
[ans=sum_{i=l}^{r}a_i*(i-l+1)*(r-i+1)
]
把括号拆开，就成了：
[(l+r)sum_{i=l}^{r}a_i*i-sum_{i=l}^{r}a_i*i^2-(l-1)*(r+1)sum_{i=l}^{r}a_i
]
线段树上维护区间(sum i^2*a_i)的和即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 200007
#define ll long long
struct data
{
ll s1,s2,s3;
};
data operator +(data l,data r)
{
return (data){l.s1+r.s1,l.s2+r.s2,l.s3+r.s3};
}
data operator *(data v,ll d)
{
return (data){v.s1*d,v.s2*d,v.s3*d};
}
int n;
struct Tree
{
#define lc (k<<1)
#define rc (k<<1|1)
data val[N<<2],sum[N<<2];
ll add[N<<2];
void mark(int k,ll d)
{
val[k]=val[k]+sum[k]*d;
add[k]+=d;
}
void pushdown(int k)
{
mark(lc,add[k]);
mark(rc,add[k]);
add[k]=0;
}
void build(int k,int l,int r)
{
if(l==r)
{
sum[k]={1,l,1ll*l*l};
return;
}
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
sum[k]=sum[lc]+sum[rc];
}
void modify(int k,int l,int r,int x,int y,ll d)
{
if(l>=x&&r<=y)return mark(k,d);
int mid=l+r>>1;
pushdown(k);
if(x<=mid)modify(lc,l,mid,x,y,d);
if(y>mid)modify(rc,mid+1,r,x,y,d);
val[k]=val[lc]+val[rc];
}
data query(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return val[k];
int mid=l+r>>1;
data ans={0,0,0};
pushdown(k);
if(x<=mid)ans=ans+query(lc,l,mid,x,y);
if(y>mid)ans=ans+query(rc,mid+1,r,x,y);
return ans;
}
void mdy(int l,int r,ll d)
{
modify(1,1,n,l,r,d);
}
ll ask(ll l,ll r)
{
data ans=query(1,1,n,l,r);
return (l+r)*ans.s2-ans.s3-(l-1)*(r+1)*ans.s1;
}
}T;
ll gcd(ll x,ll y)
{
return y?gcd(y,x%y):x;
}
int main()
{
int m;
scanf("%d%d",&n,&m),n--;
int l,r;
ll d;
char s[10];
T.build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%s%d%d",s,&l,&r);r--;
if(s[0]=='C')
{
scanf("%lld",&d);
T.mdy(l,r,d);
}
else
{
ll x=T.ask(l,r),len=r-l+1,y=1ll*len*(len+1)/2;
ll gd=gcd(x,y);
printf("%lld/%lld
",x/gd,y/gd);
}
}
return 0;
}