Submission #689583

#	Time	Username	Problem	Language	Result	Execution time	Memory
689583		Cyanmond	Fish 2 (JOI22_fish2)	C++17	100 / 100	1740 ms	21444 KiB

fish2

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf64 = 1ll << 50;
constexpr int inf = 1000000000;

template <class M>
class segTree {
    int n, size;
    using T = typename M::T;
    std::vector<T> data;

    void update(int i) {
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }

  public:
    segTree(int n_) : n(n_) {
        size = 1;
        while (size < n) {
            size *= 2;
        }
        data.assign(2 * size, M::id());
    }

    void set(int i, T v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    T fold(int l, int r) {
        T pl = M::id(), pr = M::id();
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) {
                pl = M::op(pl, data[l++]);
            }
            if (r % 2 == 1) {
                pr = M::op(data[--r], pr);
            }
        }
        return M::op(pl, pr);
    }

    template <class F>
    int maxRight(int l, F f) {
        assert(f(M::id()));
        if (l == n) {
            return n;
        }

        l += size;
        T p = M::id();
        do {
            while (l % 2 == 0) {
                l /= 2;
            }
            if (not f(M::op(p, data[l]))) {
                while (l < size) {
                    l *= 2;
                    if (f(M::op(p, data[l]))) {
                        p = M::op(p, data[l]);
                        ++l;
                    }
                }
                return l - size;
            }
            p = M::op(p, data[l]);
            ++l;
        } while ((l & (-l)) != l);

        return n;
    }

    template <class F>
    int minLeft(int r, F f) {
        assert(f(M::id()));
        if (r == 0) {
            return 0;
        }

        r += size;
        T p = M::id();
        do {
            --r;
            while (r > 1 and (r % 2 == 1)) {
                r /= 2;
            }
            if (not f(M::op(data[r], p))) {
                while (r < size) {
                    r = 2 * r + 1;
                    if (f(M::op(data[r], p))) {
                        p = M::op(data[r], p);
                        --r;
                    }
                }
                return r + 1 - size;
            }
        } while ((r & (-r)) != r);

        return 0;
    }
};

constexpr int B = 1000;

struct rangeSum64 {
    using T = i64;

    static T op(T a, T b) {
        return a + b;
    }

    static T id() {
        return 0;
    }
};

struct rangeMax64 {
    using T = i64;

    static T op(T a, T b) {
        return std::max(a, b);
    }

    static T id() {
        return -inf64;
    }
};

struct rangeMaxWithIndex32 {
    using T = std::pair<int, int>;

    static T op(T a, T b) {
        return std::max(a, b);
    }

    static T id() {
        return {-inf, 0};
    }
};

struct rangeSum32 {
    using T = int;

    static T op(T a, T b) {
        return a + b;
    }

    static T id() {
        return 0;
    }
};

struct rangeMax32 {
    using T = int;

    static T op(T a, T b) {
        return std::max(a, b);
    }

    static T id() {
        return -inf;
    }
};

int main() {
    // input
    int N;
    std::cin >> N;
    std::vector<i64> A(N);
    for (auto &e : A) {
        std::cin >> e;
    }

    segTree<rangeSum64> sumA(N);
    segTree<rangeMax64> maxA(N);
    for (int i = 0; i < N; ++i) {
        sumA.set(i, A[i]);
        maxA.set(i, A[i]);
    }

    segTree<rangeMaxWithIndex32> maxR(N);

    auto expandRange = [&](int &l, int &r) {
        while (true) {
            const auto sum = sumA.fold(l, r);
            const auto limitL = maxA.minLeft(l, [&](const auto v) { return v <= sum; });
            const auto limitR = maxA.maxRight(r, [&](const auto v) { return v <= sum; });
            const auto newL = limitL, newR = limitR;
            if (l == newL and r == newR) {
                break;
            }
            l = newL;
            r = newR;
        }
    };

    auto findRanges = [&](const int m, auto f) {
        int l = m, r = m + 1;

        while (true) {
            expandRange(l, r);
            if (l == 0 and r == N) {
                break;
            }

            f(l, r);
            if (l == 0) {
                ++r;
                continue;
            }
            if (r == N) {
                --l;
                continue;
            }
            if (A[l - 1] < A[r]) {
                --l;
            } else {
                ++r;
            }
        }
    };

    auto eraseRanges = [&](const int m, auto f) {
        while (true) {
            const auto [ma, i] = maxR.fold(0, m + 1);
            if (ma <= m) {
                break;
            }
            f(i, ma);
        }
    };

    std::vector<std::set<int>> rangesEachL(N);
    std::vector<int> countShortRanges(N);
    segTree<rangeSum32> sumPoints(N);
    segTree<rangeMax32> maxLargeRangesR(N);

    for (int i = 0; i < N; ++i) {
        sumPoints.set(i, 1);
    }

    auto addPoint = [&](const int i, const int d) {
        assert(d == 1 or d == -1);
        if (countShortRanges[i] == 0 and d == 1) {
            sumPoints.set(i, 0);
        }
        if (countShortRanges[i] == 1 and d == -1) {
            sumPoints.set(i, 1);
        }
        countShortRanges[i] += d;
        assert(0 <= countShortRanges[i]);
    };

    auto applyAddRange = [&](int l, int r) {
        if (rangesEachL[l].find(r) != rangesEachL[l].end()) {
            return;
        }
        rangesEachL[l].insert(r);
        maxR.set(l, {rangesEachL[l].empty() ? -inf : *rangesEachL[l].rbegin(), l});

        if (r - l < B) {
            for (int i = l; i < r; ++i) {
                addPoint(i, 1);
            }
        } else {
            maxLargeRangesR.set(l, *rangesEachL[l].rbegin());
        }
    };

    auto applyEraseRange = [&](int l, int r) {
        assert(rangesEachL[l].find(r) != rangesEachL[l].end());
        rangesEachL[l].erase(r);
        maxR.set(l, {rangesEachL[l].empty() ? -inf : *rangesEachL[l].rbegin(), l});

        if (r - l < B) {
            for (int i = l; i < r; ++i) {
                addPoint(i, -1);
            }
        } else {
            if (not rangesEachL[l].empty()) {
                const auto v = *rangesEachL[l].rbegin();
                if (v - l >= B) {
                    maxLargeRangesR.set(l, v);
                } else {
                    maxLargeRangesR.set(l, -inf);
                }
            } else {
                maxLargeRangesR.set(l, -inf);
            }
        }
    };

    for (int i = 0; i < N; ++i) {
        findRanges(i, applyAddRange);
    }

    // answer queries
    int Q;
    std::cin >> Q;
    while (Q--) {
        int t;
        std::cin >> t;
        
        if (t == 1) {
            int x;
            i64 y;
            std::cin >> x >> y;
            --x;
            A[x] = y;
            sumA.set(x, y);
            maxA.set(x, y);
            eraseRanges(x, applyEraseRange);
            if (x != 0) {
                eraseRanges(x - 1, applyEraseRange);
            }
            if (x != N - 1) {
                eraseRanges(x + 1, applyEraseRange);
            }
            findRanges(x, applyAddRange);
            if (x != 0) {
                findRanges(x - 1, applyAddRange);
            }
            if (x != N - 1) {
                findRanges(x + 1, applyAddRange);
            }
        }

        if (t == 2) {
            int l, r;
            std::cin >> l >> r;
            --l;

            // find true l and r
            i64 memo = -1;
            int realL = l;
            if (l != 0) {
                memo = A[l - 1];
                A[l - 1] = inf64;
                sumA.set(l - 1, A[l - 1]);
                maxA.set(l - 1, A[l - 1]);
            }
            findRanges(l, [&](int a, int b) {
                assert(a == l);
                if (b < r) {
                    realL = b;
                }
            });
            if (l != 0) {
                A[l - 1] = memo;
                sumA.set(l - 1, A[l - 1]);
                maxA.set(l - 1, A[l - 1]);
            }

            int realR = r;
            if (r != N) {
                memo = A[r];
                A[r] = inf64;
                sumA.set(r, A[r]);
                maxA.set(r, A[r]);
            }
            findRanges(r - 1, [&](int a, int b) {
                assert(b == r);
                if (a > l) {
                    realR = a;
                }
            });
            if (r != N) {
                A[r] = memo;
                sumA.set(r, A[r]);
                maxA.set(r, A[r]);
            }

            assert(realL < realR);

            if (r - l < B) {
                std::vector<int> imos(r - l + 1);
                auto itr = rangesEachL[l].lower_bound(r);
                if (itr != rangesEachL[l].begin()) {
                    --itr;
                    ++imos[0];
                    --imos[*itr - l];
                }
                for (int i = l + 1; i < r; ++i) {
                    if (rangesEachL[i].empty()) {
                        continue;
                    }
                    auto avalR = rangesEachL[i].rbegin();
                    ++imos[i - l];
                    --imos[std::min(r, *avalR) - l];
                }

                int answer = 0;
                for (int i = 0; i < r - l; ++i) {
                    if (realL <= i + l and i + l < realR and imos[i] == 0) {
                        ++answer;
                    }
                    imos[i + 1] += imos[i];
                }

                std::cout << answer << std::endl;
                continue;
            }

            int answer = 0;
            auto itr = rangesEachL[l].lower_bound(r);
            int nowR = realL;
            if (realL == l) {
                if (countShortRanges[l] == 0) {
                    ++answer;
                }
                ++nowR;
            }
            while (nowR < realR) {
                const auto nextR = maxLargeRangesR.fold(l + 1, nowR + 1);
                if (nextR > nowR) {
                    nowR = nextR;
                } else {
                    // problem...
                    const auto nextStep = maxLargeRangesR.maxRight(nowR, [&](const auto v) {
                        return v <= nowR;
                    });
                    answer += sumPoints.fold(nowR, std::min(realR, nextStep));
                    nowR = nextStep;
                }
            }

            std::cout << answer << std::endl;
        }
    }
}

Compilation message (stderr)

fish2.cpp: In function 'int main()':
fish2.cpp:410:18: warning: variable 'itr' set but not used [-Wunused-but-set-variable]
  410 |             auto itr = rangesEachL[l].lower_bound(r);
      |                  ^~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17