Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 50005;
- int st[maxn << 2], lz[maxn << 2];
- void update(int id, int l, int r, int u, int v, int val) {
- if (v < l || r < u) return;
- if (u <= l && r <= v) {
- lz[id] += val;
- return;
- }
- int mid = (l + r) >> 1;
- update(id << 1, l, mid, u, v, val);
- update(id << 1 | 1, mid + 1, r, u, v, val);
- st[id] = max(st[id << 1] + lz[id << 1], st[id << 1 | 1] + lz[id << 1 | 1]);
- }
- int get(int id, int l, int r, int u, int v) {
- if (v < l || r < u) return -1e9;
- if (u <= l && r <= v)
- return st[id] + lz[id];
- int mid = (l + r) >> 1;
- return max(get(id << 1, l, mid, u, v),
- get(id << 1 | 1, mid + 1, r, u, v)) + lz[id];
- }
- int main() {
- #ifdef LDT
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= m; ++i) {
- int typ;
- cin >> typ;
- if (typ == 0) {
- int x, y, val;
- cin >> x >> y >> val;
- update(1, 1, n, x, y, val);
- }
- else {
- int x, y;
- cin >> x >> y;
- cout << get(1, 1, n, x, y) << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement