考虑每一段对答案的贡献
用每一段的左端点来表示当前这一段，那么区间就变成了[1,n-1]
如果询问区间[l,r]，其中一个点的位置为x，则它对答案的贡献为(x-l)*(r-x)*s[x]（s[x]为这一段的权值）
化简后得x*s[x]*(l+r-1)-s[x]*(l*r-r)-x*x*s[x]
那么我们就需要维护x*s[x]，s[x]，x*x*s[x]
其中还需要预处理出来x和x*x
然后就ok了
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 500001
#define LL long long
#define root 1, 1, n - 1
#define ls now << 1, l, mid
#define rs now << 1 | 1, mid + 1, r using namespace std; int n, m;
LL s, xs, xxs, ans1, ans2;
LL x1[N], x2[N], sum1[N], sum2[N], sum3[N], add[N];
//x1表示 x
//x2表示 x^2
//sum1表示 s[x]
//sum2表示 x * s[x]
//sum3表示 x^2 * s[x] inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void push_down(int now, int l, int r)
{
if(add[now])
{
int mid = (l + r) >> 1;
sum1[now << 1] += 1ll * add[now] * (mid - l + 1);
sum1[now << 1 | 1] += 1ll * add[now] * (r - mid);
sum2[now << 1] += add[now] * x1[now << 1];
sum2[now << 1 | 1] += add[now] * x1[now << 1 | 1];
sum3[now << 1] += add[now] * x2[now << 1];
sum3[now << 1 | 1] += add[now] * x2[now << 1 | 1];
add[now << 1] += add[now];
add[now << 1 | 1] += add[now];
add[now] = 0;
}
} inline void push_up(int now)
{
sum1[now] = sum1[now << 1] + sum1[now << 1 | 1];
sum2[now] = sum2[now << 1] + sum2[now << 1 | 1];
sum3[now] = sum3[now << 1] + sum3[now << 1 | 1];
} inline void update(int now, int l, int r, int x, int y, LL z)
{
if(x <= l && r <= y)
{
add[now] += z;
sum1[now] += 1ll * z * (r - l + 1);
sum2[now] += 1ll * z * x1[now];
sum3[now] += 1ll * z * x2[now];
return;
}
push_down(now, l, r);
int mid = (l + r) >> 1;
if(x <= mid) update(ls, x, y, z);
if(mid < y) update(rs, x, y, z);
push_up(now);
} inline void build(int now, int l, int r)
{
if(l == r)
{
x1[now] += l;
x2[now] += 1ll * l * l;
return;
}
int mid = (l + r) >> 1;
build(ls);
build(rs);
x1[now] = x1[now << 1] + x1[now << 1 | 1];
x2[now] = x2[now << 1] + x2[now << 1 | 1];
} inline void query(int now, int l, int r, int x, int y)
{
if(x <= l && r <= y)
{
s += sum1[now];
xs += sum2[now];
xxs += sum3[now];
return;
}
push_down(now, l, r);
int mid = (l + r) >> 1;
if(x <= mid) query(ls, x, y);
if(mid < y) query(rs, x, y);
} inline LL gcd(LL x, LL y)
{
return !y ? x : gcd(y, x % y);
} int main()
{
LL g, z;
int i, x, y;
char c[10];
n = read();
m = read();
build(root);
while(m--)
{
scanf("%s", c);
if(c[0] == 'C')
{
x = read();
y = read();
z = read();
update(root, x, y - 1, z);
}
else
{
x = read();
y = read();
s = xs = xxs = 0;
query(root, x, y - 1);
ans2 = 1ll * (1 + y - x) * (y - x) / 2;
ans1 = 1ll * xs * (x + y - 1) - s * (1ll * x * y - y) - xxs;
g = gcd(ans1, ans2);
printf("%lld/%lld\n", ans1 / g, ans2 / g);
}
}
return 0;
}
一个longlong调了我45min，WNM