关于UB的一些问题
查看原帖
关于UB的一些问题
215915
lOpzIth楼主2024/5/23 12:14

这份代码在luogu是0分,hydro是60分,本地下bzoj数据全过了,但是把 #define int __int128 改成 long long就过了,这是为什么?哪里ub了?

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
#define int __int128
#define i64 long long
#define ull unsigned long long
#define Arr std::vector
#define Ptn std::pair
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define popc(x) __builtin_popcount(x)
#define FILE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define TEST(x) freopen(x ".in", "r", stdin), freopen("test.out", "w", stdout)
#define debug std::cout << "Running on " << __FUNCTION__ << ' ' << __LINE__ << std::endl;
bool BeginPoint;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
int n, m;

int a[N], Sum[N];
#define lc (p << 1)
#define rc (p << 1 | 1)
struct SegmentTree1
{
    int sum[N << 2], tag[N << 2];

    void upd(int p) { sum[p] = sum[lc] + sum[rc]; }

    void Build(int p, int L, int R)
    {
        tag[p] = 0;
        if (L == R) return sum[p] = a[L], void();
        int mid = (L + R) >> 1;
        Build(lc, L, mid), Build(rc, mid + 1, R);
        upd(p);
    }

    void pushdown(int p, int L, int R)
    {
        if (tag[p])
        {
            int TAG = tag[p], mid = (L + R) >> 1; tag[p] = 0;
            tag[lc] += TAG, tag[rc] += TAG;
            sum[lc] += TAG * (mid - L + 1), sum[rc] += TAG * (R - mid);
        }
    }

    void Modify(int p, int L, int R, int l, int r, int x)
    {
        if (r < l) return ;
        if (l <= L && R <= r) return sum[p] += (R - L + 1) * x, tag[p] += x, void();
        int mid = (L + R) >> 1; pushdown(p, L, R);
        if (l <= mid) Modify(lc, L, mid, l, r, x);
        if (r >= mid + 1) Modify(rc, mid + 1, R, l, r, x);
        upd(p);
    }

    int Query(int p, int L, int R, int l, int r)
    {
        if (r < l) return 0;
        if (l <= L && R <= r) return sum[p];
        int mid = (L + R) >> 1, res = 0; pushdown(p, L, R);
        if (l <= mid) res = Query(lc, L, mid, l, r);
        if (r >= mid + 1) res += Query(rc, mid + 1, R, l, r);
        return res;
    }
} T1;
#undef lc
#undef rc

#define lc (p << 1)
#define rc (p << 1 | 1)
struct SegmentTree2
{
    int sum[N << 2], tag[N << 2];

    void upd(int p) { sum[p] = sum[lc] + sum[rc]; }

    void Build(int p, int L, int R)
    {
        tag[p] = 0;
        if (L == R) return sum[p] = a[L], void();
        int mid = (L + R) >> 1;
        Build(lc, L, mid), Build(rc, mid + 1, R);
        upd(p);
    }

    void pushdown(int p, int L, int R)
    {
        if (tag[p])
        {
            int TAG = tag[p], mid = (L + R) >> 1; tag[p] = 0;
            tag[lc] += TAG, tag[rc] += TAG;
            sum[lc] += (mid - L + 1) * (L + mid) / 2 * TAG, sum[rc] += (R - mid) * (mid + 1 + R) / 2 * TAG;
        }
    }

    void Modify(int p, int L, int R, int l, int r, int x)
    {
        if (r < l) return ;
        if (l <= L && R <= r) return sum[p] += (R - L + 1) * (L + R) / 2 * x, tag[p] += x, void();
        int mid = (L + R) >> 1; pushdown(p, L, R);
        if (l <= mid) Modify(lc, L, mid, l, r, x);
        if (r >= mid + 1) Modify(rc, mid + 1, R, l, r, x);
        upd(p);
    }

    int Query(int p, int L, int R, int l, int r)
    {
        if (r < l) return 0;
        if (l <= L && R <= r) return sum[p];
        int mid = (L + R) >> 1, res = 0; pushdown(p, L, R);
        if (l <= mid) res = Query(lc, L, mid, l, r);
        if (r >= mid + 1) res += Query(rc, mid + 1, R, l, r);
        return res;
    }
} T2;
#undef lc
#undef rc

#define lc (p << 1)
#define rc (p << 1 | 1)
struct SegmentTree3
{
    int sum[N << 2], tag[N << 2];

    void upd(int p) { sum[p] = sum[lc] + sum[rc]; }

    void Build(int p, int L, int R)
    {
        tag[p] = 0;
        if (L == R) return sum[p] = a[L], void();
        int mid = (L + R) >> 1;
        Build(lc, L, mid), Build(rc, mid + 1, R);
        upd(p);
    }

    void pushdown(int p, int L, int R)
    {
        if (tag[p])
        {
            int TAG = tag[p], mid = (L + R) >> 1; tag[p] = 0;
            tag[lc] += TAG, tag[rc] += TAG;
            sum[lc] += (Sum[mid] - Sum[L - 1]) * TAG, sum[rc] += (Sum[R] - Sum[mid]) * TAG;
        }
    }

    void Modify(int p, int L, int R, int l, int r, int x)
    {
        if (r < l) return ;
        if (l <= L && R <= r) return sum[p] += (Sum[R] - Sum[L - 1]) * x, tag[p] += x, void();
        int mid = (L + R) >> 1; pushdown(p, L, R);
        if (l <= mid) Modify(lc, L, mid, l, r, x);
        if (r >= mid + 1) Modify(rc, mid + 1, R, l, r, x);
        upd(p);
    }

    int Query(int p, int L, int R, int l, int r)
    {
        if (r < l) return 0;
        if (l <= L && R <= r) return sum[p];
        int mid = (L + R) >> 1, res = 0; pushdown(p, L, R);
        if (l <= mid) res = Query(lc, L, mid, l, r);
        if (r >= mid + 1) res += Query(rc, mid + 1, R, l, r);
        return res;
    }
} T3;
#undef lc
#undef rc

inline int read()
{
    int w = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        w = (w << 3) + (w << 1) + (ch - 48);
        ch = getchar();
    }
    return w * f;
}

void Mdy(int l, int r, int w)
{
    T1.Modify(1, 1, n - 1, l, r - 1, w);
    T2.Modify(1, 1, n - 1, l, r - 1, w);
    T3.Modify(1, 1, n - 1, l, r - 1, w);
}

int Qry(int l, int r)
{
    int val1 = T1.Query(1, 1, n - 1, l, r - 1),
    val2 = T2.Query(1, 1, n - 1, l, r - 1),
    val3 = T3.Query(1, 1, n - 1, l, r - 1),
    x = l - 1;
    
    int op2 = (val2 - x * val1) * (r - l),
    op3 = val3 - val2 * 2 * x + x * val1 + x * x * val1;
    // printf("val1 : %lld\nval2 : %lld\nval3 : %lld\nop2 : %lld\nop3 : %lld\n", val1, val2, val3, op2, op3);
    return op2 - op3;
}

void print(int x)
{
    if (x >= 10) print(x / 10);
    putchar(x % 10 + '0');
}

bool EndPoint;
signed main()
{
    std::cerr << "Memory = " << fabs(&BeginPoint - &EndPoint) / 1048576.0 << "MB" << std::endl;

    n = read(), m = read();
    for (int i = 1; i < n; i++) Sum[i] = Sum[i - 1] + i * (i - 1);
    while (m--)
    {
        char op[5]; // std::cin >> op;
        scanf("%s", op);
        if (op[0] == 'C') 
        {
            int l = read(), r = read(), w = read();
            Mdy(l, r, w);
        }
        else
        {
            int l = read(), r = read();
            int u = Qry(l, r), d = (r - l + 1) * (r - l) / 2, Gcd = std::__gcd(u, d);
            print(u / Gcd); printf("/"); print(d / Gcd); puts("");
            // printf("%lld/%lld\n", u / Gcd, d / Gcd);
        }
    }

    std::cerr << "Time = " << (double)clock() / CLOCKS_PER_SEC << "s" << std::endl;
    return 0;
}
2024/5/23 12:14
加载中...