結果

問題 No.1441 MErGe
ユーザー nok0nok0
提出日時 2021-03-27 10:56:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 814 ms / 1,000 ms
コード長 4,166 bytes
コンパイル時間 2,124 ms
コンパイル使用メモリ 213,448 KB
実行使用メモリ 20,480 KB
最終ジャッジ日時 2024-05-06 21:51:39
合計ジャッジ時間 16,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 5 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 13 ms
5,376 KB
testcase_06 AC 14 ms
5,376 KB
testcase_07 AC 14 ms
5,376 KB
testcase_08 AC 139 ms
7,296 KB
testcase_09 AC 149 ms
6,912 KB
testcase_10 AC 250 ms
6,784 KB
testcase_11 AC 233 ms
6,108 KB
testcase_12 AC 267 ms
7,044 KB
testcase_13 AC 729 ms
19,584 KB
testcase_14 AC 727 ms
19,584 KB
testcase_15 AC 692 ms
18,816 KB
testcase_16 AC 653 ms
19,328 KB
testcase_17 AC 673 ms
18,944 KB
testcase_18 AC 375 ms
15,488 KB
testcase_19 AC 428 ms
17,664 KB
testcase_20 AC 338 ms
14,848 KB
testcase_21 AC 290 ms
13,056 KB
testcase_22 AC 406 ms
12,416 KB
testcase_23 AC 795 ms
20,480 KB
testcase_24 AC 814 ms
20,480 KB
testcase_25 AC 789 ms
20,480 KB
testcase_26 AC 768 ms
20,480 KB
testcase_27 AC 773 ms
20,480 KB
testcase_28 AC 659 ms
20,480 KB
testcase_29 AC 648 ms
20,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

struct fast_io {
	fast_io() {
		std::ios::sync_with_stdio(false);
		std::cin.tie(nullptr);
		std::cout << std::fixed << std::setprecision(15);
	}
} fast_io_;

template <class S,
          S (*op)(S, S),
          S (*e)()>
struct implicit_treap {
public:
	implicit_treap() : implicit_treap(0) {}
	implicit_treap(const int n) : implicit_treap(std::vector(n, e())) {}
	implicit_treap(const int n, S x) : implicit_treap(std::vector(n, x)) {}
	implicit_treap(const std::vector<S> &v) {
		for(int i = v.size() - 1; i >= 0; i--) insert(0, v[i]);
	}

	void insert(const int p, const S x) {
		assert(0 <= p and p <= size());
		insert(root, p, std::make_shared<node>(x, rnd()));
	}

	void erase(const int l, const int r) {
		assert(0 <= l and l <= r and r <= size());
		erase(root, l, r);
	}
	void erase(const int p) {
		erase(root, p, p + 1);
	}

	void set(const int p, const S x) {
		assert(0 <= p and p < size());
		set(root, p, x);
	}

	S get(const int p) {
		assert(0 <= p and p < size());
		return prod(p, p + 1);
	}

	S prod(const int l, const int r) {
		assert(0 <= l and l <= r and r <= size());
		return prod(root, l, r);
	}

	S all_prod() { return root != nullptr ? root->acc : e(); }

	S front() { return get(0); }

	S back() { return get(size() - 1); }

	void push_front(const S x) { insert(0, x); }

	void push_back(const S x) { insert(size(), x); }

	void pop_front() {
		assert(size());
		erase(0);
	}

	void pop_back() {
		assert(size());
		erase(size() - 1);
	}

	int size() const noexcept { return cnt(root); }

	bool empty() const noexcept { return cnt(root) == 0; }

private:
	struct xorshift {
		uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
		xorshift(uint32_t seed = 0) { z ^= seed; }
		uint32_t operator()() {
			uint32_t t = x ^ (x << 11);
			x = y;
			y = z;
			z = w;
			return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		}
	};

	xorshift rnd;

	struct node;
	using node_ptr = std::shared_ptr<node>;

	struct node {
		S val, acc;
		uint32_t pri;
		int cnt;
		node_ptr l, r;
		node(S val, uint32_t pri) : val(val), acc(e()), pri(pri), cnt(1), l(nullptr), r(nullptr) {}
	};

	node_ptr root = nullptr;

	int cnt(const node_ptr &t) const { return t != nullptr ? t->cnt : 0; }
	S acc(const node_ptr &t) const { return t != nullptr ? t->acc : e(); }

	void update(node_ptr &t) {
		if(t != nullptr) {
			t->cnt = cnt(t->l) + 1 + cnt(t->r);
			t->acc = op(acc(t->l), op(t->val, acc(t->r)));
		}
	}

	void split(node_ptr t, int key, node_ptr &l, node_ptr &r) {
		if(t == nullptr) {
			l = r = nullptr;
			return;
		}
		int implicit_key = cnt(t->l) + 1;
		if(key < implicit_key)
			split(t->l, key, l, t->l), r = t;
		else
			split(t->r, key - implicit_key, t->r, r), l = t;
		update(t);
	}

	void merge(node_ptr &t, node_ptr l, node_ptr r) {
		if(l == nullptr or r == nullptr)
			t = (l != nullptr ? l : r);
		else if(l->pri > r->pri)
			merge(l->r, l->r, r), t = l;
		else
			merge(r->l, l, r->l), t = r;
		update(t);
	}

	void insert(node_ptr &t, int key, node_ptr x) {
		node_ptr t1(nullptr), t2(nullptr);
		split(t, key, t1, t2);
		merge(t1, t1, x);
		merge(t, t1, t2);
	}

	void erase(node_ptr &t, int l, int r) {
		node_ptr t1(nullptr), t2(nullptr), t3(nullptr);
		split(t, r, t1, t2);
		split(t1, l, t1, t3);
		merge(t, t1, t2);
	}

	S prod(node_ptr &t, int l, int r) {
		node_ptr t1 = nullptr, t2 = nullptr, t3 = nullptr;
		split(t, l, t1, t2);
		split(t2, r - l, t2, t3);
		S ret = t2->acc;
		merge(t2, t2, t3);
		merge(t, t1, t2);
		return ret;
	}

	void set(node_ptr &t, const int p, const S x) {
		node_ptr t1 = nullptr, t2 = nullptr, t3 = nullptr;
		split(t, p, t1, t2);
		split(t2, 1, t2, t3);
		t2->val = x;
		merge(t2, t2, t3);
		merge(t, t1, t2);
	}
};

using S = long long;

S op(S x, S y) { return x + y; }

S e() { return 0ll; }

int main() {
	int n, q;
	std::cin >> n >> q;
	std::vector a(n, 0ll);
	for(auto &v : a) std::cin >> v;

	implicit_treap<S, op, e> seg(a);

	while(q--) {
		int t, l, r;
		std::cin >> t >> l >> r;
		--l;
		if(t == 1) {
			long long sum = seg.prod(l, r);
			seg.erase(l, r);
			seg.insert(l, sum);
		} else
			std::cout << seg.prod(l, r) << '\n';
	}

    return 0;
}
0