結果

問題 No.876 Range Compress Query
ユーザー Arumakan1727Arumakan1727
提出日時 2019-09-06 22:11:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,011 bytes
コンパイル時間 1,914 ms
コンパイル使用メモリ 179,784 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2023-09-07 00:15:44
合計ジャッジ時間 4,984 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 WA -
testcase_02 AC 1 ms
4,380 KB
testcase_03 WA -
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 WA -
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 249 ms
8,244 KB
testcase_12 WA -
testcase_13 AC 202 ms
8,284 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 240 ms
8,496 KB
testcase_17 AC 236 ms
8,512 KB
testcase_18 AC 253 ms
8,468 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
// Begin Header {{{
#define let             const auto
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#define lowerBound(...)                 lowerBound_(__VA_ARGS__)
#define upperBound(...)                 upperBound_(__VA_ARGS__)
#define lowerBound_(begin, end, ...)    (lower_bound((begin), (end), __VA_ARGS__) - (begin))
#define upperBound_(begin, end, ...)    (upper_bound((begin), (end), __VA_ARGS__) - (begin))

#ifdef DBG
#define trace(...) trace_g(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...)
#endif

using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);}
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
inline bool   isRangeIn(i64 a, i64 low, i64 high) { return (low <= a && a <= high); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
vector<T> makeVec(size_t sz) { return vector<T>(sz); }

template<class T, class... Args>
auto makeVec(size_t sz, Args... args) {
    return vector<decltype(makeVec<T>(args...))>(sz, makeVec<T>(args...));
}

template<class T>
inline void input(T &x) { cin >> x; }

template<class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }

inline void print() { cout << "\n"; }

template<class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template<class T>
ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}

template<class T>
ostream& operator<< (ostream &out, const vector<vector<T>> &mat) {
    static constexpr const char *tail[] = { "\n", "" };
    for (const auto &row : mat) out << row << tail[&row == &mat.back()];
    return out;
}

template <class T>
void trace_g(const char *s, T&& x) {
    clog << '{';
    while(*s != '\0') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void trace_g(const char *s, Head&& head, Tail&&... tail) {
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    trace_g(s, std::forward<Tail>(tail)...);
}
// }}} End Header

template<typename Monoid, typename Laz>
struct LazySegmentTree { // {{{

    const function<Monoid(Monoid, Monoid)> mergeMonoid;
    const function<Monoid(Monoid, Laz, int)> applyLaz;
    const function<Laz(Laz, Laz)> mergeLaz;

    const Monoid e; // neutral element

    vector<Monoid> seg;
    vector<Laz> lazy;
    vector<bool> isUpdated;

    int size;

    LazySegmentTree(int nmemb, const Monoid &e,
                    function<Monoid(Monoid, Monoid)> f,
                    function<Monoid(Monoid, Laz, int)> g,
                    function<Laz(Laz, Laz)> h):
        e(e), mergeMonoid(f), applyLaz(g), mergeLaz(h)
    {
        size = 1;
        while (size < nmemb) {
            size *= 2;
        }

        seg.assign(2 * size - 1, e);
        isUpdated.assign(2 * size - 1, true);
        lazy.resize(2 * size - 1);
    }

    inline void propagation(int k, int len) {
        if (!isUpdated[k]) {
            seg[k] = applyLaz(seg[k], lazy[k], len);
            if (len > 1) {
                if (isUpdated[2 * k + 1])
                    lazy[2 * k + 1] = lazy[k], isUpdated[2 * k + 1] = false;
                else
                    lazy[2 * k + 1] = mergeLaz(lazy[2 * k + 1], lazy[k]);

                if (isUpdated[2 * k + 2])
                    lazy[2 * k + 2] = lazy[k], isUpdated[2 * k + 2] = false;
                else
                    lazy[2 * k + 2] = mergeLaz(lazy[2 * k + 2], lazy[k]);
            }
            isUpdated[k] = true;
        }
    }

    Monoid update(int k, int nl, int nr, int ql, int qr, Laz dat) {
        propagation(k, nr - nl);

        if (nr <= ql || qr <= nl) return seg[k];

        if (ql <= nl && nr <= qr) {
            lazy[k] = dat;
            isUpdated[k] = false;
            propagation(k, nr - nl);
            return seg[k];
        }
        else {
            seg[k] = mergeMonoid(update(2 * k + 1, nl, (nl + nr) / 2, ql, qr, dat),
                                 update(2 * k + 2, (nl + nr) / 2, nr, ql, qr, dat));
            return seg[k];
        }
    }

    // [l, r) <= dat
    void update(int l, int r, Laz dat) {
        update(0, 0, size, l, r, dat);
    }

    Monoid query(int k, int nl, int nr, int ql, int qr) {

        propagation(k, nr - nl);

        if (nr <= ql || qr <= nl) return e;

        if (ql <= nl && nr <= qr) return seg[k];
        else return mergeMonoid(query(2 * k + 1, nl, (nl + nr) / 2, ql, qr),
                                query(2 * k + 2, (nl + nr) / 2, nr, ql, qr));
    }

    // [l, r)
    Monoid query(int l, int r) { return query(0, 0, size, l, r); }

    Monoid operator [](const int &k) { return query(k, k + 1); }
}; // }}}

template <class T> struct FenwickTree { // {{{
    vector<T> dat;
    const size_t SIZE_POW2;

    explicit FenwickTree(int size): dat(size+5, 0), SIZE_POW2(1 << (__lg(size+5)+1)) {}

    inline void add(int i, const T &v){
        for (++i; i < dat.size(); i += i & -i) dat[i]+=v;
    }

    inline T sum(int i) const {
        T s = 0;
        for (++i; i > 0; i -= i & -i) s += dat[i];
        return s;;
    }

    inline T sum(int s, int t) const {
        if (s > t) swap(s, t);
        return sum(t) - sum(s - 1);
    }

    inline T operator[](int i) const {
        return sum(i, i);
    }

    inline int lower_bound(T v) const {
        if (v <= 0) return 0;
        int i = 0;
        for (int w = SIZE_POW2; w > 0; w >>= 1) {
            if (i + w < dat.size() && dat[i + w] < v) {
                v -= dat[i + w];
                i += w;
            }
        }
        return i;
    }
}; // }}}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    var(int, N, Q);

    FenwickTree<i64> diffCum(N);

    vector<i64> a(N);

    rep(i, N) {
        input(a[i]);
    }
    rep(i, N - 1) {
        if (a[i] != a[i+1]) {
            diffCum.add(i, 1);
        }
    }

    LazySegmentTree<i64, i64> seg(N, 0,
            [](i64 l, i64 r) { return l + r; },
            [](i64 l, i64 r, int len) { return l + (r * len); },
            [](i64 l, i64 r) { return l + r; }
    );

    while (Q--) {
        var(int, com, l, r);
        --l, --r;
        if (com == 1) {
            var(i64, x);
            seg.update(l, r + 1, x);

            if (l > 0) {
                let n = a[l] + seg[l];
                let m = a[l - 1] + seg[l - 1];
                if (n != m && diffCum[l - 1] == 0) {
                    diffCum.add(l - 1, 1);
                } else if (n == m && diffCum[l - 1] == 1) {
                    diffCum.add(l - 1, -1);
                }
            }
            if (r < N - 1) {
                let n = a[r] + seg[r];
                let m = a[r + 1] + seg[r + 1];
                if (n != m && diffCum[r] == 0) {
                    diffCum.add(r, 1);
                } else if (n == m && diffCum[r] == 1) {
                    diffCum.add(r, -1);
                }
            }

        } else {
            print(diffCum.sum(l, r - 1) + 1);
        }
    }


    return 0;
}
0