結果

問題 No.2809 Sort Query
コンテスト
ユーザー Akshaj Padmakar
提出日時 2024-07-12 23:19:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,198 bytes
コンパイル時間 2,274 ms
コンパイル使用メモリ 184,580 KB
実行使用メモリ 354,812 KB
最終ジャッジ日時 2024-07-12 23:19:23
合計ジャッジ時間 13,782 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 5 TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#ifndef ONLINE_JUDGE
#include "algo/debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


class MergeSortTree {
public:
	MergeSortTree(const vector<int>& data) : n(data.size()) {
		arr = data;
		tree.resize(4 * n);
		build(1, 0, n - 1);
	}

	void update(int idx, int value) {
		arr[idx] = value;
		update(1, 0, n - 1, idx);
	}

	void sortArray() {
		sort(arr.begin(), arr.end());
		build(1, 0, n - 1); // rebuild the tree
	}

	int query(int idx) {
		return arr[idx];
	}

private:
	vector<int> arr;
	vector<vector<int>> tree;
	int n;

	void build(int node, int start, int end) {
		if (start == end) {
			tree[node] = {arr[start]};
		} else {
			int mid = (start + end) / 2;
			build(2 * node, start, mid);
			build(2 * node + 1, mid + 1, end);
			merge(tree[2 * node].begin(), tree[2 * node].end(),
			      tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
			      back_inserter(tree[node]));
		}
	}

	void update(int node, int start, int end, int idx) {
		if (start == end) {
			tree[node] = {arr[start]};
		} else {
			int mid = (start + end) / 2;
			if (start <= idx && idx <= mid) {
				update(2 * node, start, mid, idx);
			} else {
				update(2 * node + 1, mid + 1, end, idx);
			}
			tree[node].clear();
			merge(tree[2 * node].begin(), tree[2 * node].end(),
			      tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
			      back_inserter(tree[node]));
		}
	}
};


void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	MergeSortTree mst(a);

	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int k, x;
			cin >> k >> x;
			k--;
			mst.update(k, x);
		} else if (type == 2) {
			mst.sortArray();
		} else if (type == 3) {
			int k;
			cin >> k;
			k--;
			cout << mst.query(k) << endl;
		}
	}
}

signed main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int t = 1;
	//cin >> t;

	while (t--) {
		solve();
	}

	// cerr << "Time elapsed: " << ((long double)clock() / CLOCKS_PER_SEC) << " s.\n";
}
0