球帮DeBug/kel 一天了 40pts
查看原帖
球帮DeBug/kel 一天了 40pts
61932
Cantor楼主2021/8/1 14:14
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define OO 0x7fffffff
#define LL long long
#define sz(x) int(x.size())
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define STP system("pause")
using namespace std;
const int N = 3e5;
LL l[4 * N + 5], r[4 * N + 5], b[3][N + 5];
LL val[3][4 * N + 5], flg[4 * N + 5];
LL lc(LL x)
{
    return x << 1;
}
LL rc(LL x)
{
    return x << 1 | 1;
}
void Build(LL x, LL L, LL R)
{
    l[x] = L, r[x] = R;
    if (L == R)
        return;
    LL mid = (L + R) >> 1;
    Build(lc(x), L, mid);
    Build(rc(x), mid + 1, R);
    return;
}
void Pushdown(LL x)
{
    if (flg[x])
    {
        flg[lc(x)] += flg[x];
        flg[rc(x)] += flg[x];
        rep(kd, 0, 2)
            val[kd][lc(x)] += flg[x] * (b[kd][r[lc(x)]] - b[kd][l[lc(x)] - 1]),
            val[kd][rc(x)] += flg[x] * (b[kd][r[rc(x)]] - b[kd][l[rc(x)] - 1]);
        flg[x] = 0;
    }
    return;
}
void Add(LL x, LL L, LL R, LL w)
{
    if (L <= l[x] && R >= r[x])
    {
        flg[x] += w;
        rep(kd, 0, 2)
            val[kd][x] += w * (b[kd][r[x]] - b[kd][l[x] - 1]);
        return;
    }
    Pushdown(x);
    LL mid = r[lc(x)];
    if (L <= mid)
        Add(lc(x), L, R, w);
    if (R > mid)
        Add(rc(x), L, R, w);
    rep(kd, 0, 2)
        val[kd][x] = val[kd][lc(x)] + val[kd][rc(x)];
    return;
}
LL s[3];
void Ask(LL x, LL L, LL R)
{
    if (L <= l[x] && R >= r[x])
    {
        rep(kd, 0, 2)
            s[kd] += val[kd][x];
        return;
    }
    Pushdown(x);
    LL mid = r[lc(x)];
    if (L <= mid)
        Ask(lc(x), L, R);
    if (R > mid)
        Ask(rc(x), L, R);
    return;
}
LL GCD(LL x, LL y)
{
    if (y == 0)
        return x;
    else
        return GCD(y, x % y);
}
int main()
{
    LL n, m;
    scanf("%lld%lld", &n, &m);
    rep(i, 1, n)
    {
        b[0][i] = b[0][i - 1] + 1;
        b[1][i] = b[1][i - 1] + i;
        b[2][i] = b[2][i - 1] + i * i;
    }
    Build(1,1,n);
    rep(i, 1, m)
    {
        char ch;
        cin >> ch;
        if (ch == 'C')
        {
            LL l, r, w;
            scanf("%lld%lld%lld", &l, &r, &w);
            --r;
            Add(1, l, r, w);
        }
        else
        {
            LL l, r;
            scanf("%lld%lld", &l, &r);
            --r;
            s[0] = s[1] = s[2] = 0;
            Ask(1, l, r);
            LL fz = (r-l-r*l+1)*s[0] + s[1] * (r + l) - s[2];
            LL fm = (LL)(r - l + 2) * (r - l + 1) / 2;
            if (fz == 0)
            {
                cout << "0/1" << '\n';
                continue;
            }
            LL gcd = GCD(max(fz, fm), min(fz, fm));
            if (gcd)
                fz /= gcd, fm /= gcd;
            printf("%lld/%lld\n", fz, fm);
        }
    }
    return 0;
}
2021/8/1 14:14
加载中...