P2221 [HAOI2012] 高速公路

,

怎么这种吊题都要想很久。果然是要退役了/kk

考虑算每条道路的贡献，先把边的数值放到前一个点上，然后默认 $r\gets r-1$ ，要求的就是：
$$
\sum_{i=l}^r a_i(r-i+1)(i-l+1)
$$
整理后，有：
$$
(r-l+1-rl)\sum a_i+(r+l)\sum a_i\times i-\sum a_i\times 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int s[3][maxn];
struct yyy{
	int sum[3],lazy;
	void clear(void) {for (int i=0;i<3;i++) sum[i]=0;}
}f[maxn<<2];
void pushup(int rt) {
	for (int i=0;i<3;i++) f[rt].sum[i]=f[rt<<1].sum[i]+f[rt<<1|1].sum[i];
} 
void cover(int rt,int k,int l,int r) {
	for (int i=0;i<3;i++) f[rt].sum[i]+=k*(s[i][r]-s[i][l-1]);
	f[rt].lazy+=k;
}
void pushdown(int l,int r,int rt) {
	if (f[rt].lazy) {
		int mid=l+r>>1;
		cover(rt<<1,f[rt].lazy,l,mid);
		cover(rt<<1|1,f[rt].lazy,mid+1,r);
		f[rt].lazy=0;
	}
}
void Update(int l,int r,int rt,int head,int tail,int k) {
	if (head<=l&&r<=tail) return cover(rt,k,l,r),void();
	int mid=l+r>>1;pushdown(l,r,rt);
	if (head<=mid) Update(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,k);
	pushup(rt);
}
yyy Query(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt];
	int mid=l+r>>1;pushdown(l,r,rt);
	yyy tmp1,tmp2;tmp1.clear();tmp2.clear();
	if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
	for (int i=0;i<3;i++) tmp1.sum[i]+=tmp2.sum[i];
	return tmp1;
}
signed main(void){
//	freopen("1.in","r",stdin);
	int i,l,r,x;char ch;
	read(n);read(m);
	for (i=1;i<=n;i++) s[0][i]=s[0][i-1]+1,s[1][i]=s[1][i-1]+i,s[2][i]=s[2][i-1]+i*i;
	while (m--) {
		ch=getchar();while (ch!='C'&&ch!='Q') ch=getchar();
		read(l);read(r);r--;
		if (ch=='C') read(x),Update(1,n,1,l,r,x);
		else {
			auto tmp=Query(1,n,1,l,r);
			int ans=tmp.sum[0]*(r-l+1-r*l)+tmp.sum[1]*(r+l)-tmp.sum[2];
//			gdb(tmp.sum[0],tmp.sum[1],tmp.sum[2],ans);
			int pus=(r-l+2)*(r-l+1)/2,g=__gcd(ans,pus);
			if (!ans) puts("0/1");
			else printf("%lld/%lld\n",ans/g,pus/g);
		}
	}
	return 0;
}