这份代码在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;
}