Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int INF = 2e18;
- struct node {
- int left, right, real_val = -INF;
- node *left_child, *right_child;
- };
- node *build(vector<int> &a, int left, int right) {
- node *cur = new node;
- if (left == right) {
- cur->left = left;
- cur->right = right;
- cur->real_val = a[left];
- return cur;
- }
- int mid = (right + left) / 2;
- cur->left_child = build(a, left, mid);
- cur->right_child = build(a, mid + 1, right);
- cur->left = left;
- cur->right = right;
- return cur;
- }
- int get_val(node* root, int ind) {
- //cout << root->left << " " << root->right << " " << ind << '\n';
- if (root->left > ind || root->right < ind) {
- return -INF;
- }
- if (root->left == ind && root->right == ind)
- return root->real_val;
- if (root->left <= ind && ind <= root->right) {
- if (root->real_val != -INF) {
- int ans = root->real_val;
- root->real_val = -INF;
- root->left_child->real_val = ans;
- root->right_child->real_val = ans;
- return ans;
- } else {
- return max(get_val(root->left_child, ind), get_val(root->right_child, ind));
- }
- }
- }
- void set_val(node* root, int left, int right, int val) {
- if (root->left > right || root->right < left) {
- return;
- }
- if (left <= root->left && root->right <= right) {
- root->real_val = val;
- return;
- }
- set_val(root->left_child, left, right, val);
- set_val(root->right_child, left, right, val);
- }
- signed main() {
- int n;
- cin >> n;
- vector<int> a(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- int m;
- cin >> m;
- node *root = build(a, 0, n - 1);
- for (int i = 0; i < m; i++) {
- char t;
- cin >> t;
- if (t == 'g') {
- int ind;
- cin >> ind;
- ind--;
- cout << get_val(root, ind) << ' ';
- } else {
- int l, r, x;
- cin >> l >> r >> x;
- l--, r--;
- set_val(root, l, r, x);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement