这题我用了一个二阶差分的树状数组做的,思路肯定是没问题的,最后也AC了。但是我在调代码的时候发现有个地方非常诡异。
看这段代码的注释,如果不加(long long)只能过前3个点,我猜测是val * p超出int范围了
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n, m;
long long f1[MAXN] = {0}, f2[MAXN] = {0};
int lowbit(int x)
{
return x & -x;
}
void add(int p, int val)
{
for (int i = p; i <= n; i += lowbit(i))
{
f1[i] += (long long) val;
f2[i] += val * p; // 这行不加类型转换,只能过前3个点
}
}
void op1(int l, int r, int k, int d)
{
add(l, k);
add(l + 1, d - k);
add(r + 1, -k - (r - l + 1) * d);
add(r + 2, k + (r - l) * d);
}
void op2(int p)
{
long long ret = 0;
for (int i = p; i > 0; i -= lowbit(i))
{
ret += (p + 1) * (long long) f1[i] - f2[i];
}
printf("%lld\n", ret);
}
int main()
{
scanf("%d %d", &n, &m);
int a1, a2, a3;
scanf("%d", &a1);
add(1, a1);
scanf("%d", &a2);
add(2, a2 - 2 * a1);
for (int i = 3; i <= n; i++)
{
scanf("%d", &a3);
add(i, a3 - 2 * a2 + a1);
a1 = a2;
a2 = a3;
}
int op, l, r, k, d;
for (int i = 0; i < m; i++)
{
scanf("%d", &op);
switch(op)
{
case 1:
scanf("%d %d %d %d", &l, &r, &k, &d);
op1(l, r, k, d);
break;
case 2:
scanf("%d", &a1);
op2(a1);
break;
}
}
}
问题在于,如果我全都用int都不开long long那么除了第一个点之外所有测试点均可通过。
如果说是val * p超出了int范围的话那么不应该能通过这些测试点才对。有没有大佬能告诉我这究竟是什么原因导致的?