比赛 树形数据结构拔高 评测结果 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;
}