結果

問題 No.1441 MErGe
ユーザー nikkukunnikkukun
提出日時 2021-03-26 22:12:56
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 388 ms / 1,000 ms
コード長 1,817 bytes
コンパイル時間 1,814 ms
コンパイル使用メモリ 168,100 KB
実行使用メモリ 12,528 KB
最終ジャッジ日時 2023-08-19 08:37:47
合計ジャッジ時間 10,553 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge10
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,432 KB
testcase_01 AC 2 ms
5,488 KB
testcase_02 AC 2 ms
5,420 KB
testcase_03 AC 4 ms
5,704 KB
testcase_04 AC 4 ms
5,636 KB
testcase_05 AC 12 ms
5,568 KB
testcase_06 AC 12 ms
5,596 KB
testcase_07 AC 12 ms
5,576 KB
testcase_08 AC 109 ms
6,696 KB
testcase_09 AC 108 ms
6,836 KB
testcase_10 AC 180 ms
6,684 KB
testcase_11 AC 171 ms
6,068 KB
testcase_12 AC 179 ms
6,620 KB
testcase_13 AC 279 ms
12,484 KB
testcase_14 AC 287 ms
12,432 KB
testcase_15 AC 305 ms
12,400 KB
testcase_16 AC 285 ms
12,412 KB
testcase_17 AC 276 ms
12,468 KB
testcase_18 AC 319 ms
12,316 KB
testcase_19 AC 353 ms
12,352 KB
testcase_20 AC 281 ms
12,196 KB
testcase_21 AC 264 ms
9,184 KB
testcase_22 AC 388 ms
9,160 KB
testcase_23 AC 385 ms
12,528 KB
testcase_24 AC 381 ms
12,476 KB
testcase_25 AC 379 ms
12,472 KB
testcase_26 AC 385 ms
12,460 KB
testcase_27 AC 373 ms
12,468 KB
testcase_28 AC 147 ms
12,476 KB
testcase_29 AC 149 ms
12,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;

const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;

struct SegTree {
	static const int M = 4 * N;

	ll t[M];
	int s[M];

	void maintain(int o) {
		t[o] = t[lch] + t[rch];
		s[o] = s[lch] + s[rch];
	}

	void build(int o, int L, int R, int a[]) {
		if (L == R) {
			t[o] = a[L];
			s[o] = 1;
			return;
		}
		int M = (L + R) / 2;
		build(lch, L, M, a);
		build(rch, M + 1, R, a);
		maintain(o);
	}

	void modify(int o, int L, int R, int rnk, ll val, int sum) {
		if (L == R) {
			t[o] = val;
			s[o] = sum;
			return;
		}
		int M = (L + R) / 2;
		if (rnk <= s[lch])
			modify(lch, L, M, rnk, val, sum);
		else
			modify(rch, M + 1, R, rnk - s[lch], val, sum);
		maintain(o);
	}

	// 返回前缀和
	ll query(int o, int L, int R, int rnk) {
		if (rnk == 0) return 0LL;
		if (L == R) {
			return t[o];
		}
		int M = (L + R) / 2;
		if (rnk <= s[lch])
			return query(lch, L, M, rnk);
		else
			return t[lch] + query(rch, M + 1, R, rnk - s[lch]);
	}
};
SegTree seg;

int a[N];

int main() {
	ios::sync_with_stdio(0);

	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	seg.build(1, 1, n, a);

	while (q--) {
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1) {
			ll sum = seg.query(1, 1, n, r) - seg.query(1, 1, n, l - 1);
			seg.modify(1, 1, n, l, sum, 1);
			for (int i = l + 1; i <= r; i++)
				seg.modify(1, 1, n, l + 1, 0, 0);
		}
		if (op == 2) {
			ll sum = seg.query(1, 1, n, r) - seg.query(1, 1, n, l - 1);
			cout << sum << endl;
		}
	}

	return 0;
}
0