有一个诡异的问题
查看原帖
有一个诡异的问题
1022761
wuuk楼主2024/1/13 23:57

这题我用了一个二阶差分的树状数组做的,思路肯定是没问题的,最后也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范围的话那么不应该能通过这些测试点才对。有没有大佬能告诉我这究竟是什么原因导致的?

2024/1/13 23:57
加载中...