输入时将 \(r\) 先减 1。
发现收费之和为 $$ans = \sum\limits_{i = l} ^ {r} a_i \times (r - l + 1) \times (i - l + 1 )$$
化简得
\[ans = \sum\limits_{i = l} ^ {r} a_i \times (-i^2 + i \times (r + l) + (r - r \times l - l + 1))
\]
发现可以用线段树来维护:
\(sum1\) 表示 \(\sum\limits_{i = l}^{r} a_i\)
\(sum2\) 表示 \(\sum\limits_{i = l}^{r} a_i \times i\)
\(sum3\) 表示 \(\sum\limits_{i = l}^{r} a_i \times i ^ 2\)
发现区间修改时 \(sum2\) 和 \(sum3\) 不好维护。
引入 \(sum4\) 表示 \(\sum i\), \(sum5\) 表示 \(\sum i ^ 2\)
答案显然为 \(\dfrac{2 \times ans}{(r - l + 2) \times (r - l + 1)}\)。
#include<bits/stdc++.h>
#define int long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 1e5 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m;
int sum1, sum2, sum3;
int sum[6][N << 2], lazy[N << 2];
void pushdown(int u, int l, int r){
if(!lazy[u]) return ;
lazy[ls] += lazy[u], lazy[rs] += lazy[u];
int mid = (l + r) >> 1;
sum[1][ls] += (mid - l + 1) * lazy[u], sum[1][rs] += (r - mid) * lazy[u];
sum[2][ls] += sum[4][ls] * lazy[u], sum[2][rs] += sum[4][rs] * lazy[u];
sum[3][ls] += sum[5][ls] * lazy[u], sum[3][rs] += sum[5][rs] * lazy[u];
lazy[u] = 0;
}
void modify(int u, int l, int r, int L, int R, int v){
if(L <= l && r <= R) return lazy[u] += v, sum[1][u] += (r - l + 1) * v, sum[2][u] += sum[4][u] * v, sum[3][u] += sum[5][u] * v, void();
int mid = (l + r) >> 1;
pushdown(u, l, r);
if(L <= mid) modify(ls, l, mid, L, R, v);
if(R > mid) modify(rs, mid + 1, r, L, R, v);
sum[1][u] = sum[1][ls] + sum[1][rs], sum[2][u] = sum[2][ls] + sum[2][rs], sum[3][u] = sum[3][ls] + sum[3][rs];
}
void query(int u, int l, int r, int L, int R){
if(L <= l && r <= R) return sum1 += sum[1][u], sum2 += sum[2][u], sum3 += sum[3][u], void();
int mid = (l + r) >> 1;
pushdown(u, l, r);
if(L <= mid) query(ls, l, mid, L, R);
if(R > mid) query(rs, mid + 1, r, L, R);
}
void build(int u, int l, int r){
if(l == r) return sum[4][u] = l, sum[5][u] = l * l, void();
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
sum[4][u] = sum[4][ls] + sum[4][rs], sum[5][u] = sum[5][ls] + sum[5][rs];
}
int gcd(int a, int b){
if(!b) return a;
return gcd(b, a % b);
}
signed main(){
n = read(), m = read();
build(1, 1, n);
while(m--){
char opt[5]; scanf("%s", opt + 1);
int l = read(), r = read() - 1;
if(opt[1] == 'C'){
int v = read();
modify(1, 1, n, l, r, v);
}else{
if(l > r){
printf("0/1\n");
continue;
}
sum1 = sum2 = sum3 = 0;
query(1, 1, n, l, r);
int r1 = (r - r * l - l + 1) * sum1 + (r + l) * sum2 - sum3;
int r2 = (r - l + 2) * (r - l + 1) / 2;
int t = gcd(r1, r2);
printf("%lld/%lld\n", r1 / t, r2 / t);
}
}
return 0;
}