简单线段树求调 自行查错无果
查看原帖
简单线段树求调 自行查错无果
763398
AchorX楼主2024/7/23 09:37
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, m;
long long sum1[N], sum2[N], sum3[N], sum4[N], sum5[N];
int num, ls[N], rs[N];
void build(int &p, int l, int r) {
	if (!p) p = ++num;
	if (l == r) {
		sum4[p] = 1ll * l * l;
		sum5[p] = 1ll * l;
		return ;
	}
	int mid = (l + r) >> 1;
	build(ls[p], l, mid);
	build(rs[p], mid + 1, r);
	sum4[p] = sum4[ls[p]] + sum4[rs[p]];
	sum5[p] = sum5[ls[p]] + sum5[rs[p]];
}
int lz[N];
void pushdown(int p, int l, int r) {
	if (!lz[p]) return ;
	int mid = (l + r) >> 1;
	sum1[ls[p]] += (mid - l + 1) * lz[p];
	sum2[ls[p]] += sum5[ls[p]] * lz[p];
	sum3[ls[p]] += sum4[ls[p]] * lz[p];
	sum1[rs[p]] += (r - mid) * lz[p];
	sum2[rs[p]] += sum5[rs[p]] * lz[p];
	sum3[rs[p]] += sum4[rs[p]] * lz[p];
	lz[ls[p]] += lz[p], lz[rs[p]] += lz[p];
	lz[p] = 0;
}
void update(int p, int l, int r, int s, int t, int w) {
	if (!p) return ;
	if (l <= s && t <= r) {
		int len = t - s + 1;
		sum1[p] += len * w;
		sum2[p] += sum5[p] * w;
		sum3[p] += sum4[p] * w;
		lz[p] += w;
		return ;
	}
	pushdown(p, s, t);
	int mid = (s + t) >> 1;
	if (l <= mid) update(ls[p], l, r, s, mid, w);
	if (r > mid) update(rs[p], l, r, mid + 1, t, w);
	sum1[p] = sum1[ls[p]] + sum1[rs[p]];
	sum2[p] = sum2[ls[p]] + sum2[rs[p]];
	sum3[p] = sum3[ls[p]] + sum3[rs[p]];
}
int rt;
int s1, s2, s3;
void ask(int p, int l, int r, int s, int t) {
	if (!p) return ;
	if (l <= s && t <= r) {
		s1 += sum1[p], s2 += sum2[p], s3 += sum3[p];
		return ;
	}
	pushdown(p, s, t);
	int mid = (s + t) >> 1;
	if (l <= mid) ask(p, l, r, s, mid);
	if (r > mid) ask(p, l, r, mid + 1, t);
}
long long Gcd(long long a, long long b) {
	return (b == 0) ? a : Gcd(b, a % b);
}
void read() {
	scanf("%d%d", &n, &m);
	n--;
	build(rt, 1, n);
	int x, y, w;
	char op;
	for (int i = 1; i <= m; ++i) {
		scanf(" %c", &op);
		if (op == 'C') {
			scanf("%d%d%d", &x, &y, &w);
			update(rt, x, y - 1, 1, n, w);
		} else {
			scanf("%d%d", &x, &y);
			s1 = s2 = s3 = 0, y--;
			ask(rt, x, y, 1, n);
			long long fz = (y - x + 1 - y * x) * s1 + (x + y) * s2 - s3;
			long long fm = (y - x + 2) * (y - x + 1) / 2, g = Gcd(fz, fm);
			fz /= g, fm /= g;
			printf("%lld/%lld\n", fz, fm);
		}
	}
}
int main() {
	read();
	return 0;
}
2024/7/23 09:37
加载中...