从CF1737学习区间计数处理与开方精度丢失问题

Problem - B - Codeforces

思路出来之后，需要计算 \(l,r\) 区间的个数。

我想的是计算出 \([0,r]\) 的个数和 \([0,l]\) 的个数，然后相减。

大体上是没问题，但是我的实现麻烦而且有错误。

初始代码

void solve() {
    ll l, r;
    cin >> l >> r;
    auto calc = [&](ll x, bool opt) {
        if (x == 1) return opt ? 0LL : 1LL;
        ll SQRT = sqrtl(x);
        if (SQRT * SQRT == x) return opt ? (SQRT - 1 << 1) + SQRT - 1 : (SQRT - 1 << 1) + SQRT;
        SQRT++;
        ll cmp = SQRT * SQRT;
        if (opt) {
            if (x > cmp - 1) 
                return (SQRT - 1 << 1) + SQRT - 1;
            if (x == cmp - 1)
                return (SQRT - 1 << 1) + SQRT - 1 - 1;
            if (x > cmp - SQRT) 
                return (SQRT - 1 << 1) + SQRT - 2;
            if (x == cmp - SQRT) 
                return (SQRT - 1 << 1) + SQRT - 2 - 1;
            return (SQRT - 1 << 1) + SQRT - 3;
        }
        if (x >= cmp - 1) return (SQRT - 1 << 1) + SQRT - 1;
        if (x >= cmp - SQRT) return (SQRT - 1 << 1) + SQRT - 2;
        return (SQRT - 1 << 1) + SQRT - 3;
    };
    cout << calc(r, 0) - calc(l, 1) << endl;
}

• 万一左端点 \(l\) 是有效值，减去的时候会计算进去，从而让答案少 \(1\)，而不是有效值的话又不会影响答案，所以在 calc 上加了很麻烦特判。
  • 实际上这类问题可以求 \([0,l-1]\) 的个数，然后再用 \([0,r]\) 来减即可，完美避免了上述问题。
• sqrt 在 long long 开方会丢精度！
  • 用 sqrtl

改进代码

void solve() {
    ll l, r;
    cin >> l >> r;
    auto calc = [&](ll x) {
        if (x == 0) return 0LL;
        if (x == 1) return 1LL;
        ll SQRT = sqrtl(x);
        if (SQRT * SQRT == x) return (SQRT - 1 << 1) + SQRT;
        SQRT++;
        ll cmp = SQRT * SQRT;
        if (x >= cmp - 1) 
            return (SQRT - 1 << 1) + (SQRT - 1);
        if (x >= cmp - SQRT) 
            return (SQRT - 1 << 1) - 1 + (SQRT - 1);
        return (SQRT - 2 << 1) + SQRT - 1;
    };
    cout << calc(r) - calc(l - 1) << endl;
}