結果

問題 No.1441 MErGe
コンテスト
ユーザー first_vil
提出日時 2020-11-26 17:11:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 333 ms / 1,000 ms
コード長 2,695 bytes
コンパイル時間 2,635 ms
コンパイル使用メモリ 208,880 KB
最終ジャッジ日時 2025-01-16 05:50:48
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define tp(a,i) get<i>(a)
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline T sum(const vector<T>& a, int l, int r) { return a[r] - (l == 0 ? 0 : a[l - 1]); }

template<class Op> class SegmentTree {
	using T = typename Op::T;
	int len, n;
	vector<T> dat;
	vector<pair<int, int>> range;
public:
	SegmentTree(const vector<T>& v) : n(v.size()) {
		for (len = 1; len < n; len <<= 1);
		dat.resize(len << 1, Op::unit);
		range.resize(len << 1);
		for (int i = 0; i < n; ++i)dat[i + len] = v[i];
		for (int i = 0; i < len; ++i)
			range[i + len] = make_pair(i, i + 1);
		for (int i = len - 1; 0 < i; --i) {
			dat[i] = Op::merge(dat[i << 1], dat[i << 1 | 1]);
			range[i] = make_pair(range[i << 1].first, range[i << 1 | 1].second);
		}
	}
	inline void update(int idx, const T a) {
		idx += len;
		dat[idx] = Op::update(dat[idx], a);
		for (idx >>= 1; 0 < idx; idx >>= 1)
			dat[idx] = Op::merge(dat[idx << 1], dat[idx << 1 | 1]);
	}
	inline int binary_search(const T a) {
		if (!Op::check(dat[1], a))return n;
		T cur = Op::unit;
		int idx = 2;
		for (; idx < len << 1; idx <<= 1) {
			if (!Op::check(Op::merge(cur, dat[idx]), a))
				cur = Op::merge(cur, dat[idx++]);
		}
		return min((idx >> 1) - len, n);
	}
};
template<class Type> struct node {
	using T = Type;
	inline static T unit = 0;
	inline static T merge(T vl, T vr) { return vl + vr; }
	inline static T update(T vl, T vr) { return vl + vr; }
	inline static T check(T vl, T vr) { return vl >= vr; }
};

int main() {
    init();

    int n, q; cin >> n >> q;
    VL a(n); cin >> a;
    SegmentTree<node<int>> seg(VI(n, 1));
    set<int> s;
    FOR(i, 0, n) {
        if (0 < i)a[i] += a[i - 1];
        s.emplace(i);
    }
    while (q--) {
        int t, l, r; cin >> t >> l >> r;
        if (t == 1) {
            int d = r - l;
            l = seg.binary_search(l);
            r = seg.binary_search(r);
            auto it = s.find(l);
            FOR(i, 0, d)seg.update(*++it, -1);
            FOR(i, 0, d)s.erase(s.upper_bound(l));
        }
        else cout << sum(a, seg.binary_search(l), seg.binary_search(r + 1) - 1) << "\n";
    }

    return 0;
}
0