【题解】 P2221 [HAOI2012]高速公路

标签：rs int 题解 sum mid times ls HAOI2012 P2221

传送门

输入时将 \(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;
} 

标签：rs,int,题解,sum,mid,times,ls,HAOI2012,P2221
From： https://www.cnblogs.com/jiangchen4122/p/17465261.html