結果

問題 No.1441 MErGe
コンテスト
ユーザー nikkukun
提出日時 2021-03-26 22:12:56
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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