比赛 树形数据结构拔高 评测结果 WWTTTTTTTT
题目名称 高速公路 最终得分 0
用户昵称 wdsjl 运行时间 32.000 s
代码语言 C++ 内存使用 3.57 MiB
提交时间 2025-04-17 20:01:49
显示代码纯文本
#include <iostream>
#include <vector>
using namespace std;
#define int long long

int gcd(int a, int b) {
    return b == 0? a : gcd(b, a % b);
}

pair<int, int> wk(const vector<int>& costs, int l, int r) {
    int totalCost = 0;
    int pairNum = (r - l) * (r - l + 1) / 2;
    for (int i = l - 1; i < r - 1; ++i) {
        for (int j = i + 1; j < r; ++j) {
            int cost = 0;
            for (int k = i; k < j; ++k) {
                cost += costs[k];
            }
            totalCost += cost;
        }
    }
    int d = gcd(totalCost, pairNum);
    return {totalCost / d, pairNum / d};
}

signed main() {
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
    int n, m;
    cin >> n >> m;
    vector<int> costs(n - 1, 0); 
    for (int i = 0; i < m; ++i) {
        char op;
        cin >> op;
        if (op == 'C') {
            int l, r, v;
            cin >> l >> r >> v;
            for (int j = l - 1; j < r - 1; ++j) {
                costs[j] += v;
            }
        } else {
            int l, r;
            cin >> l >> r;
            pair<int, int> res = wk(costs, l, r);
            int num = res.first;
            int den = res.second;
            cout << num << "/" << den << endl;
        }
        cout<<i<<endl; 
    }
    return 0;
}