BZOJ2752 [HAOI2012]高速公路(road)

题面在这里

首先把题目转化为对长度为\(n-1\)的序列的操作

考虑询问区间\([L,R]\)\(i\in [L,R]\),则\(w_i\)的贡献为: \[ w_i(i-L+1)(R-i+1) \] 整理得 \[ -w_i\cdot i^2+(L+R)w_i\cdot i-(LR+L-R-1)w_i \] 那么线段树维护\(i,i^2,w_i,w_i\cdot i,w_i\cdot i^2\)的和就好了

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
typedef long long ll;

const int maxn=100005,maxs=400005;
int n,q; char s[10];
ll w[maxs],wi[maxs],wii[maxs],i[maxs],ii[maxs],ad[maxs];
#define ls x<<1
#define rs x<<1|1
inline void pushup(int x){
w[x]=w[ls]+w[rs];
wi[x]=wi[ls]+wi[rs];
wii[x]=wii[ls]+wii[rs];
i[x]=i[ls]+i[rs];
ii[x]=ii[ls]+ii[rs];
}
inline void addad(int x,ll v,int l,int r){
w[x]+=v*(r-l+1);
wi[x]+=v*i[x];
wii[x]+=v*ii[x];
ad[x]+=v;
}
inline void pushdown(int x,int l,int mid,int r){
if (ad[x]) addad(ls,ad[x],l,mid),addad(rs,ad[x],mid+1,r),ad[x]=0;
}
void build(int x,int l,int r){
if (l==r) {i[x]=l;ii[x]=(ll)l*l;return;}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(x);
}
void ist(int x,int l,int r,int ql,int qr,int v){
if (ql<=l&&r<=qr) {addad(x,v,l,r);return;}
if (qr<l||r<ql) return;
int mid=l+r>>1; pushdown(x,l,mid,r);
ist(ls,l,mid,ql,qr,v);ist(rs,mid+1,r,ql,qr,v);
pushup(x);
}
ll qry(int x,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return (ql+qr)*wi[x]-wii[x]-w[x]*((ll)ql*qr+ql-qr-1);
if (qr<l||r<ql) return 0;
int mid=l+r>>1; pushdown(x,l,mid,r);
return qry(ls,l,mid,ql,qr)+qry(rs,mid+1,r,ql,qr);
}
ll gcd(ll x,ll y) {return y==0?x:gcd(y,x%y);}
int main(){
scanf("%d%d",&n,&q);
build(1,1,n);
while (q--){
scanf("%s",s);
if (s[0]=='C'){
int l,r,v;scanf("%d%d%d",&l,&r,&v);r--;
ist(1,1,n,l,r,v);
}else{
int l,r;scanf("%d%d",&l,&r);r--;
ll k=r-l+1,a=qry(1,1,n,l,r),b=k*(k+1)/2;
ll t=gcd(a,b); a/=t;b/=t;
printf("%lld/%lld\n",a,b);
}
}
return 0;
}