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