結果

問題 No.876 Range Compress Query
コンテスト
ユーザー nu50218
提出日時 2019-09-08 23:32:41
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 5,203 bytes
記録
コンパイル時間 1,795 ms
コンパイル使用メモリ 180,844 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-06-27 15:18:03
合計ジャッジ時間 4,141 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
    }
} fast;

/* define */
#define FOR(I, X, Y) for (long long(I) = (X); (I) < (Y); (I)++)
#define REP(I, X, Y) for (long long(I) = (Y)-1; (I) >= (X); (I)--)
#define ALL(X) (X).begin(), (X).end()
#define pb push_back
#define COUNT(V, X)                           \
    (upper_bound((V).begin(), (V).end(), X) - \
     lower_bound((V).begin(), (V).end(), X))
#define debug(x) cerr << #x << ':' << x << endl;
#define DEBUG(v)                             \
    {                                        \
        cerr << #v << ':';                   \
        for (auto xv : v) cerr << xv << ' '; \
        cerr << endl;                        \
    }
#define Yes(X) cout << (X ? "Yes" : "No") << endl;
#define YES(X) cout << (X ? "YES" : "NO") << endl;
#define ctoi(C) (C - '0')
#define pow2(x) ((long long)((long long)1 << x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1, 0, -1, 0};
const long long dy[] = {0, 1, 0, -1};
const long long dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
const long long dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long dx9[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
const long long dy9[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T1, typename T2>
inline bool chmin(T1& a, const T2& b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T1, typename T2>
inline bool chmax(T1& a, const T2& b) {
    if (a < b) a = b;
    return a < b;
}
long long max(long long x, int y) {
    return max(x, (long long)y);
}
long long max(int x, long long y) {
    return max((long long)x, y);
}
long long min(long long x, int y) {
    return min(x, (long long)y);
}
long long min(int x, long long y) {
    return min((long long)x, y);
}

/* library */

template <typename T>
class SegmentTree {
   private:
    size_t length;
    vector<T> data;
    T e;
    function<T(T, T)> f;
    //data[i]の区間 = [l[i],r[i])
    vector<int> l;
    vector<int> r;

   public:
    void
    change(int i, T val) {
        data[i + length - 1] = val;
        for (int k = (i + length) / 2 - 1; k >= 0; k = (k - 1) / 2) {
            data[k] = f(data[2 * k + 1], data[2 * k + 2]);
            if (!k) break;
        }
    }

    //[i,j)
    T query(const int& i, const int& j) {
        T ans = e;
        queue<int> que;
        que.push(0);
        int k;
        while (que.size()) {
            k = que.front();
            que.pop();
            if (r[k] <= i || j <= l[k]) {
                continue;
            }
            if (i <= l[k] && r[k] <= j) {
                ans = f(ans, data[k]);
                continue;
            }
            que.push(2 * k + 1);
            que.push(2 * k + 2);
        }
        return ans;
    }

    T operator[](const size_t& i) {
        return data[i + length - 1];
    }

    SegmentTree(const vector<T>& v, const function<T(T, T)>& f, const T& e) : length(1), f(f), e(e) {
        while (!(length >= v.size())) length *= 2;
        data = vector<T>(length * 2 - 1, e);
        for (int i = 0; i < v.size(); i++) {
            data[i + length - 1] = v[i];
        }
        for (int i = length - 2; 0 <= i; i--) {
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
        }
        l.resize(length * 2 - 1);
        r.resize(length * 2 - 1);
        for (int i = length - 1; i < length * 2 - 1; i++) {
            l[i] = i - length + 1;
            r[i] = min(i - length + 2, v.size());
        }
        for (int i = length - 2; 0 <= i; i--) {
            l[i] = l[i * 2 + 1];
            r[i] = r[i * 2 + 2];
        }
    };
};

/* main */

signed main() {
    int N, Q;
    cin >> N >> Q;
    vi a(N);
    for (auto& x : a) cin >> x;
    vector<pl> b(N - 1);
    FOR(i, 0, N - 1) {
        b[i].first = a[i + 1] - a[i];
        b[i].second = (b[i].first ? 0 : 1);
    }
    auto f = [](pl a, pl b) {
        return make_pair(0, a.second + b.second);
    };
    SegmentTree<pl> st(b, f, make_pair(1, 0));
    FOR(i, 0, Q) {
        int query, l, r, x;
        cin >> query;
        if (query == 1) {
            cin >> l >> r >> x;
            l--;
            r--;
            if (l != 0) {
                auto prev_value = st[l - 1];
                st.change(l - 1, make_pair(prev_value.first + x, (prev_value.first + x ? 0 : 1)));
            }
            if (r != N - 1) {
                auto prev_value = st[r];
                st.change(r, make_pair(prev_value.first - x, (prev_value.first - x ? 0 : 1)));
            }
        }
        if (query == 2) {
            cin >> l >> r;
            l--;
            r--;
            cout << r - l + 1 - st.query(l, r).second << endl;
        }
    }
}
0