比赛 |
树形数据结构拔高 |
评测结果 |
AAAAAAAAAA |
题目名称 |
高速公路 |
最终得分 |
100 |
用户昵称 |
健康铀 |
运行时间 |
1.630 s |
代码语言 |
C++ |
内存使用 |
13.76 MiB |
提交时间 |
2025-04-17 21:31:43 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
struct Node {
int l, r;
__int128 sum_v, sum_jv, sum_j2v;
__int128 lazy;
} tree[4 * MAXN];
void push_up(int node) {
tree[node].sum_v = tree[2 * node].sum_v + tree[2 * node + 1].sum_v;
tree[node].sum_jv = tree[2 * node].sum_jv + tree[2 * node + 1].sum_jv;
tree[node].sum_j2v = tree[2 * node].sum_j2v + tree[2 * node + 1].sum_j2v;
}
void build(int node, int l, int r) {
tree[node].l = l;
tree[node].r = r;
tree[node].sum_v = 0;
tree[node].sum_jv = 0;
tree[node].sum_j2v = 0;
tree[node].lazy = 0;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
push_up(node);
}
void push_down(int node) {
if (tree[node].lazy) {
int left = 2 * node;
int right = 2 * node + 1;
__int128 val = tree[node].lazy;
int L = tree[left].l;
int R = tree[left].r;
__int128 len = R - L + 1;
tree[left].sum_v += val * len;
tree[left].sum_jv += val * (L + R) * len / 2;
__int128 sum_j2 = ((__int128)R * (R + 1) * (2 * R + 1) - (__int128)(L - 1) * L * (2 * (L - 1) + 1)) / 6;
tree[left].sum_j2v += val * sum_j2;
tree[left].lazy += val;
L = tree[right].l;
R = tree[right].r;
len = R - L + 1;
tree[right].sum_v += val * len;
tree[right].sum_jv += val * (L + R) * len / 2;
sum_j2 = ((__int128)R * (R + 1) * (2 * R + 1) - (__int128)(L - 1) * L * (2 * (L - 1) + 1)) / 6;
tree[right].sum_j2v += val * sum_j2;
tree[right].lazy += val;
tree[node].lazy = 0;
}
}
void update(int node, int a, int b, __int128 val) {
if (tree[node].r < a || tree[node].l > b) {
return;
}
if (a <= tree[node].l && tree[node].r <= b) {
int L = tree[node].l;
int R = tree[node].r;
__int128 len = R - L + 1;
tree[node].sum_v += val * len;
tree[node].sum_jv += val * (L + R) * len / 2;
__int128 sum_j2 = ((__int128)R * (R + 1) * (2 * R + 1) - (__int128)(L - 1) * L * (2 * (L - 1) + 1)) / 6;
tree[node].sum_j2v += val * sum_j2;
tree[node].lazy += val;
return;
}
push_down(node);
update(2 * node, a, b, val);
update(2 * node + 1, a, b, val);
push_up(node);
}
struct QueryRes {
__int128 sum_v, sum_jv, sum_j2v;
};
QueryRes query(int node, int a, int b) {
if (tree[node].r < a || tree[node].l > b) {
return {0, 0, 0};
}
if (a <= tree[node].l && tree[node].r <= b) {
return {tree[node].sum_v, tree[node].sum_jv, tree[node].sum_j2v};
}
push_down(node);
QueryRes left = query(2 * node, a, b);
QueryRes right = query(2 * node + 1, a, b);
return {left.sum_v + right.sum_v, left.sum_jv + right.sum_jv, left.sum_j2v + right.sum_j2v};
}
__int128 gcd(__int128 a, __int128 b) {
while (b) {
a %= b;
swap(a, b);
}
return a < 0 ? -a : a;
}
void print(__int128 x) {
if (x == 0) {
putchar('0');
return;
}
if (x < 0) {
putchar('-');
x = -x;
}
char buf[50];
int len = 0;
while (x > 0) {
buf[len++] = x % 10 + '0';
x /= 10;
}
while (len--) {
putchar(buf[len]);
}
}
int main() {
freopen("roadxw.in", "r", stdin);
freopen("roadxw.out", "w", stdout);
int N, M;
scanf("%d%d", &N, &M);
if (N >= 2) {
build(1, 1, N - 1);
}
while (M--) {
char op[2];
scanf("%s", op);
if (op[0] == 'C') {
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
int a = l;
int b = r - 1;
if (a <= b) {
update(1, a, b, v);
}
} else {
int l, r;
scanf("%d%d", &l, &r);
int a = l;
int b = r - 1;
QueryRes res = query(1, a, b);
__int128 S = -res.sum_j2v + (__int128)(r + l - 1) * res.sum_jv - (__int128)(l - 1) * r * res.sum_v;
__int128 k = r - l + 1;
__int128 D = k * (k - 1) / 2;
if (S == 0) {
printf("0/1\n");
continue;
}
__int128 s_abs = S >= 0 ? S : -S;
__int128 g = gcd(s_abs, D);
__int128 numerator = S / g;
__int128 denominator = D / g;
print(numerator);
putchar('/');
print(denominator);
putchar('\n');
}
}
return 0;
}