Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define PRINT for(int i = 0; i < 10; i++){ relax(i); cout << v[i] << " ";} cout << endl;
- #define PRINT_S for(int i = 0; i < 10; i++){ cout << v_s[i] << " ";} cout << endl;
- #define int long long
- using namespace std;
- using ll = unsigned long long;
- const int max_n = 200500;
- const int d = 500;
- vector<int> v(max_n, LONG_LONG_MAX), all(max_n / d), w(max_n / d), p(max_n / d), all1(max_n / d), all2(max_n / d), sum(max_n / d), mins(max_n / d);
- void relax(int l)
- {
- if(all[l / d])
- {
- for(int i = (l / d) * d; i < (l / d) * d + d; i++)
- {
- if(v[i] == LONG_LONG_MAX) continue;
- if(all1[i / d]) v[i] = w[i / d];
- if(all2[i / d]) v[i] += p[i / d];
- }
- all[l / d] = 0;
- all1[l / d] = 0;
- all2[l / d] = 0;
- p[l / d] = 0;
- }
- }
- void relax_min(int l)
- {
- mins[l / d] = LONG_LONG_MAX;
- for(int i = (l / d) * d; i < (l / d) * d + d; i++)
- {
- mins[i / d] = min(mins[i / d], v[i]);
- }
- }
- int get(int i)
- {
- relax(i);
- return v[i];
- }
- void update(int l, int r, int x)
- {
- relax(l);
- if(l / d == r / d)
- {
- for(int i = l; i <= r; i++)
- {
- sum[i / d] -= v[i];
- v[i] = x;
- sum[i / d] += x;
- }
- relax_min(l);
- return;
- }
- for(int i = l; i < (l / d) * d + d; i++)
- {
- sum[i / d] -= v[i];
- v[i] = x;
- sum[i / d] += x;
- }
- relax_min(l);
- for(int i = (l / d) + 1; i < r / d; i++)
- {
- all[i] = 1;
- sum[i] = x * d;
- w[i] = x;
- mins[i] = x;
- p[i] = 0;
- all1[i] = 1;
- all2[i] = 0;
- }
- relax(r);
- for(int i = (r / d) * d; i <= r; i++)
- {
- sum[i / d] -= v[i];
- v[i] = x;
- sum[i / d] += x;
- }
- relax_min(r);
- }
- void add(int l, int r, int x)
- {
- relax(l);
- if(l / d == r / d)
- {
- for(int i = l; i <= r; i++)
- {
- v[i] += x;
- sum[i / d] += x;
- }
- relax_min(l);
- return;
- }
- for(int i = l; i < (l / d) * d + d; i++)
- {
- v[i] += x;
- sum[i / d] += x;
- }
- relax_min(l);
- for(int i = (l / d) + 1; i < r / d; i++)
- {
- all[i] = 1;
- all2[i] = 1;
- p[i] += x;
- sum[i] += x * d;
- mins[i] += x;
- }
- relax(r);
- for(int i = (r / d) * d; i <= r; i++)
- {
- v[i] += x;
- sum[i / d] += x;
- }
- relax_min(r);
- }
- int rsq(int l, int r)
- {
- relax(l);
- int ans = 0;
- if(l / d == r / d)
- {
- for(int i = l; i <= r; i++) ans += v[i];
- return ans;
- }
- for(int i = l; i < (l / d) * d + d; i++) ans += v[i];
- for(int i = (l / d) + 1; i < r / d; i++)
- {
- ans += sum[i];
- }
- relax(r);
- for(int i = (r / d) * d; i <= r; i++) ans += v[i];
- return ans;
- }
- int rmq(int l, int r)
- {
- int ans = LONG_LONG_MAX;
- relax(l);
- if(l / d == r / d)
- {
- for(int i = l; i <= r; i++) ans = min(ans, v[i]);
- return ans;
- }
- for(int i = l; i < (l / d) * d + d; i++) ans = min(ans, v[i]);
- for(int i = (l / d) + 1; i < r / d; i++)
- {
- ans = min(ans, mins[i]);
- }
- relax(r);
- for(int i = (r / d) * d; i <= r; i++) ans = min(ans, v[i]);
- return ans;
- }
- main()
- {
- int n;
- cin >> n;
- for(int i = 0; i < n; i++) cin >> v[i];
- for(int i = 0; i < n; i++) sum[i / d] += v[i];
- for(int i = 0; i < n; i++) relax_min(i);
- int q;
- cin >> q;
- for(int i = 0; i < q; i++)
- {
- string s;
- cin >> s;
- if(s == "add")
- {
- int l, r, x;
- cin >> l >> r >> x;
- l--; r--;
- add(l, r, x);
- }
- if(s == "update")
- {
- int l, r, x;
- cin >> l >> r >> x;
- l--; r--;
- update(l, r, x);
- }
- if(s == "get")
- {
- int x;
- cin >> x;
- x--;
- cout << get(x) << "\n";
- }
- if(s == "rsq")
- {
- int l, r;
- cin >> l >> r;
- l--; r--;
- cout << rsq(l, r) << "\n";
- }
- if(s == "rmq")
- {
- int l, r;
- cin >> l >> r;
- l--; r--;
- cout << rmq(l, r) << "\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement