結果

問題 No.1441 MErGe
ユーザー nikkukunnikkukun
提出日時 2021-03-26 22:12:56
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 342 ms / 1,000 ms
コード長 1,817 bytes
コンパイル時間 1,480 ms
コンパイル使用メモリ 171,176 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-11-28 23:32:43
合計ジャッジ時間 9,658 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 12 ms
5,248 KB
testcase_06 AC 12 ms
5,248 KB
testcase_07 AC 11 ms
5,248 KB
testcase_08 AC 102 ms
5,248 KB
testcase_09 AC 96 ms
5,248 KB
testcase_10 AC 162 ms
5,376 KB
testcase_11 AC 153 ms
5,248 KB
testcase_12 AC 158 ms
5,248 KB
testcase_13 AC 248 ms
10,368 KB
testcase_14 AC 250 ms
10,240 KB
testcase_15 AC 264 ms
10,240 KB
testcase_16 AC 243 ms
10,368 KB
testcase_17 AC 246 ms
10,368 KB
testcase_18 AC 273 ms
10,240 KB
testcase_19 AC 313 ms
10,240 KB
testcase_20 AC 250 ms
10,112 KB
testcase_21 AC 227 ms
7,040 KB
testcase_22 AC 342 ms
6,912 KB
testcase_23 AC 328 ms
10,368 KB
testcase_24 AC 329 ms
10,368 KB
testcase_25 AC 332 ms
10,240 KB
testcase_26 AC 313 ms
10,352 KB
testcase_27 AC 333 ms
10,368 KB
testcase_28 AC 143 ms
10,368 KB
testcase_29 AC 142 ms
10,368 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