結果

問題 No.1441 MErGe
ユーザー nikkukunnikkukun
提出日時 2021-03-26 22:12:56
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 403 ms / 1,000 ms
コード長 1,817 bytes
コンパイル時間 1,880 ms
コンパイル使用メモリ 171,000 KB
実行使用メモリ 12,624 KB
最終ジャッジ日時 2024-05-06 15:49:04
合計ジャッジ時間 11,087 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 4 ms
6,944 KB
testcase_04 AC 5 ms
7,664 KB
testcase_05 AC 12 ms
7,544 KB
testcase_06 AC 13 ms
6,944 KB
testcase_07 AC 12 ms
6,944 KB
testcase_08 AC 111 ms
7,744 KB
testcase_09 AC 110 ms
6,944 KB
testcase_10 AC 185 ms
8,392 KB
testcase_11 AC 174 ms
7,644 KB
testcase_12 AC 181 ms
7,520 KB
testcase_13 AC 299 ms
12,596 KB
testcase_14 AC 296 ms
12,488 KB
testcase_15 AC 313 ms
12,428 KB
testcase_16 AC 285 ms
12,492 KB
testcase_17 AC 287 ms
12,520 KB
testcase_18 AC 323 ms
12,492 KB
testcase_19 AC 359 ms
12,424 KB
testcase_20 AC 286 ms
12,308 KB
testcase_21 AC 265 ms
9,108 KB
testcase_22 AC 385 ms
10,500 KB
testcase_23 AC 395 ms
12,588 KB
testcase_24 AC 396 ms
10,360 KB
testcase_25 AC 390 ms
12,624 KB
testcase_26 AC 403 ms
12,308 KB
testcase_27 AC 394 ms
12,404 KB
testcase_28 AC 156 ms
12,552 KB
testcase_29 AC 156 ms
12,548 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