比赛 |
树形数据结构拔高 |
评测结果 |
AATTTTTTTT |
题目名称 |
高速公路 |
最终得分 |
20 |
用户昵称 |
LikableP |
运行时间 |
31.858 s |
代码语言 |
C++ |
内存使用 |
1.49 MiB |
提交时间 |
2025-04-17 21:46:13 |
显示代码纯文本
#include <cstdio>
typedef long long ll;
const int MAXN = 1e5 + 10;
ll GCD(ll x, ll y) {
if (y == 0) return x;
return GCD(y, x % y);
}
int n, m;
ll a[MAXN];
void Work1() {
while (m--) {
char op[5];
int l, r, v;
scanf("%s %d %d", op, &l, &r);
if (op[0] == 'C') {
scanf("%d", &v);
for (int i = l ; i <= r - 1; ++i) {
a[i] += v;
}
} else {
ll sum = 0, cnt = 0;
for (int i = l; i <= r - 1; ++i) {
for (int j = i + 1; j <= r; ++j) {
cnt++;
for (int k = i; k <= j - 1; ++k) {
sum += a[k];
}
}
}
ll gcd = GCD(sum, cnt);
printf("%lld/%lld\n", sum / gcd, cnt / gcd);
}
}
}
int main() {
freopen("roadxw.in", "r", stdin);
freopen("roadxw.out", "w", stdout);
scanf("%d %d", &n, &m);
if (n <= 1000) {
Work1();
} else {
Work1();
}
return 0;
}