比赛 |
树形数据结构拔高 |
评测结果 |
AAAAAAAAAA |
题目名称 |
高速公路 |
最终得分 |
100 |
用户昵称 |
flyfree |
运行时间 |
1.195 s |
代码语言 |
C++ |
内存使用 |
11.33 MiB |
提交时间 |
2025-04-17 20:02:55 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define dpir pair <ll, pir>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 100010
#define qmod(x) (x>mod?x-mod:x)
inline ll read(){
ll x = 0,f = 1;
char c = getchar();
while(c < '0'||c > '9'){
if(c == '-')f = -1;
c = getchar();
}
while(c >= '0'&&c <= '9'){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
ll pre[MAXN];
// struct node_inter{
// ll l,r,suml,sumr.sum;
// }
ll n,m;
struct node_sgt{
ll suml[MAXN * 4],sumr[MAXN * 4],sum[MAXN * 4],ans[MAXN * 4];
ll tag[MAXN * 4];
ll l[MAXN * 4],r[MAXN * 4];
ll qs_ans,qs_pre;
void update(ll now, ll v){
tag[now] += v;
suml[now] += v * (r[now] - l[now] + 2) * (r[now] - l[now] + 1) / 2;
sumr[now] += v * (r[now] - l[now] + 2) * (r[now] - l[now] + 1) / 2;
ans[now] += v * pre[r[now] - l[now] + 1];
sum[now] += v * (r[now] - l[now] + 1);
}
void push_down(ll now){
if(!tag[now])return;
update(now << 1, tag[now]);
update(now << 1 | 1, tag[now]);
tag[now] = 0;
}
void build(ll lz = 1, ll rz = n - 1, ll now = 1){
l[now] = lz,r[now] = rz;
if(lz == rz)return;
ll mid = (lz + rz) >> 1;
build(lz, mid, now << 1);
build(mid + 1, rz, now << 1 | 1);
}
void push_up(ll now){
suml[now] = suml[now << 1] + suml[now << 1 | 1] + sum[now << 1 | 1] * (r[now << 1] - l[now << 1] + 1);
sumr[now] = sumr[now << 1] + sumr[now << 1 | 1] + sum[now << 1] * (r[now << 1 | 1] - l[now << 1 | 1] + 1);
sum[now] = sum[now << 1] + sum[now << 1 | 1];
ans[now] = ans[now << 1] + ans[now << 1 | 1];
ans[now] += sumr[now << 1 | 1] * (r[now << 1] - l[now << 1] + 1);
ans[now] += suml[now << 1] * (r[now << 1 | 1] - l[now << 1 | 1] + 1);
}
void Query(ll lz, ll rz, ll now = 1){
if(l[now] >= lz && r[now] <= rz){
qs_ans += ans[now];
qs_ans += qs_pre * (r[now] - l[now] + 1);
qs_ans += sumr[now] * (l[now] - lz);
qs_pre += suml[now] + sum[now] * (l[now] - lz);
// cout << "Query : " << l[now] << " " << r[now] << " " <<qs_ans << " " << qs_pre << " " << endl;
return;
}
push_down(now);
ll mid = (l[now] + r[now]) >> 1;
if(lz <= mid)Query(lz, rz, now << 1);
if(rz > mid)Query(lz, rz, now << 1 | 1);
return;
}
ll write(){
ll res = qs_ans;
qs_ans = qs_pre = 0;
return res;
}
void modify(ll lz, ll rz, ll v, ll now = 1){
if(l[now] >= lz && r[now] <= rz){
update(now, v);
return;
}
push_down(now);
ll mid = (l[now] + r[now]) >> 1;
if(lz <= mid)modify(lz, rz, v, now << 1);
if(rz > mid)modify(lz, rz, v, now << 1 | 1);
push_up(now);
}
}sgt;
ll get_gcd(ll x, ll y){
if(y == 0)return x;
else return get_gcd(y, x % y);
}
void write(ll fz, ll fm){
ll g = get_gcd(fm, fz);
cout << fz / g << "/" << fm / g << endl;
return;
}
int main(){
freopen("roadxw.in", "r", stdin);
freopen("roadxw.out", "w", stdout);
n = read(),m = read();
sgt.build();
pre[1] = 1;
for(int i = 2;i <= 100000; ++i)pre[i] = pre[i - 1] + (i + 1) * i / 2;
for(int i = 1;i <= m; ++i){
char c;
cin >> c;
if(c == 'C'){
ll l = read(),r = read() - 1,v = read();
sgt.modify(l, r, v);
}else{
ll l = read(),r = read() - 1;
ll fm = (r - l + 1) * (r - l + 2) / 2;
sgt.Query(l, r);
ll fz = sgt.write();
// cout << fz << " " << fm << endl;
write(fz, fm);
}
}
return 0;
}