Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long long INF = 1e9;
- void build(vector<long long>& start, vector<long long>& z, int l, int r, int now) {
- if (l > r) {
- return;
- }
- if (l == r) {
- z[now] = start[l];
- return;
- }
- int mid = (l + r) / 2;
- build(start, z, l, mid, now * 2);
- build(start, z, mid + 1, r, now * 2 + 1);
- z[now] = min(z[now * 2], z[now * 2 + 1]);
- }
- void push(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int now) {
- if (f[now] != -1) {
- z[now] = f[now] + ad[now];
- f[now * 2] = f[now];
- f[now * 2 + 1] = f[now];
- f[now] = -1;
- ad[now] = 0;
- } else {
- z[now] += ad[now];
- ad[now * 2] += ad[now];
- ad[now * 2 + 1] += ad[now];
- ad[now] = 0;
- }
- }
- long long query(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int l, int r, int a, int b, int now) {
- push(z, ad, f, now);
- if (r < a || l > b) {
- return INF;
- }
- if (a <= l && r <= b) {
- return z[now];
- }
- int mid = (l + r) / 2;
- return min(query(z, ad, f, l, mid, a, b, now * 2), query(z, ad, f, mid + 1, r, a, b, now * 2 + 1));
- }
- void update_add(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int l, int r, int delta, int a, int b, int now) {
- push(z, ad, f, now);
- if (r < a || l > b) {
- return;
- }
- if (a <= l && r <= b) {
- ad[now] += delta;
- push(z, ad, f, now);
- return;
- }
- int mid = (l + r) / 2;
- update_add(z, ad, f, l, mid, delta, a, b, now * 2);
- update_add(z, ad, f, mid + 1, r, delta, a, b, now * 2 + 1);
- z[now] = min(z[now * 2], z[now * 2 + 1]);
- }
- void update_res(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int l, int r, int value, int a, int b, int now) {
- push(z, ad, f, now);
- if (r < a || l > b) {
- return;
- }
- if (a <= l && r <= b) {
- f[now] = value;
- push(z, ad, f, now);
- return;
- }
- int mid = (l + r) / 2;
- update_res(z, ad, f, l, mid, value, a, b, now * 2);
- update_res(z, ad, f, mid + 1, r, value, a, b, now * 2 + 1);
- z[now] = min(z[now * 2], z[now * 2 + 1]);
- }
- int main() {
- int n;
- cin >> n;
- vector<long long> start(n);
- for (int i = 0; i < n;++i) {
- cin >> start[i];
- }
- string s;
- vector<long long> ad(n * 6, 0);
- vector<long long> z(n * 6, INF);
- vector<long long> f(n * 6, -1);
- build(start, z, 0, n - 1, 1);
- while (cin >> s) {
- int l, r;
- cin >> l >> r;
- if (s == "min") {
- cout << query(z, ad, f, 0, n - 1, l - 1, r - 1, 1) << "\n";
- } else if (s == "set") {
- int val;
- cin >> val;
- update_res(z, ad, f, 0, n - 1, val, l - 1, r - 1, 1);
- } else {
- int val;
- cin >> val;
- update_add(z, ad, f, 0, n - 1, val, l - 1, r - 1, 1);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement