#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define popcount __builtin_popcount
#define lg(x) (63 - clz(x))
template <class X, class Y>
inline bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
return false;
}
template <class X, class Y>
inline bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
return false;
}
template <class X>
inline void compress(vector<X> &a) {
sort(all(a)); a.resize(unique(all(a)) - a.begin());
}
const ll oo = (ll) 1e17;
const int inf = (int) 1e9, mod = (int) 1e9 + 7;
void add(ll &x, ll y) {
x += y;
if (x >= mod) x -= mod;
}
const int mxn = (int) 2e5 + 5, lg = (int) 19;
int n, q;
ll arr[mxn];
class SegmentTree {
struct node {
ll ans;
ll l, r;
bool first_inc, last_inc;
bool first_dec, last_dec;
node() {
ans = l = r = -1;
first_inc = last_inc = 0;
first_dec = last_dec = 0;
};
node (int i) {
ans = 0;
l = r = arr[i];
first_inc = last_inc = true;
first_dec = last_dec = true;
}
bool isOne() const {
return l == r;
}
#define C(i, j) abs((i) - (j))
node operator + (const node &b) const {
node res, a = *this;
if (a.ans == -1) return b;
if (b.ans == -1) return a;
res.ans = a.ans + b.ans;
res.l = a.l; res.r = b.r;
if (a.isOne() && b.isOne()) {
res.ans += C(a.r, b.l);
if (a.r <= b.l) {
res.first_inc = true;
res.last_dec = true;
} else {
res.first_dec = true;
res.last_inc = true;
}
return res;
}
if (a.isOne()) {
if (a.r <= b.l && b.first_inc) {
res.ans += C(a.r, b.l);
res.first_inc = true;
}
else if (a.r >= b.l && b.first_dec) {
res.ans += C(a.r, b.l);
res.first_dec = true;
}
res.last_inc = b.last_inc;
res.last_dec = b.last_dec;
return res;
}
if (b.isOne()) {
if (a.r <= b.l && a.last_dec) {
res.ans += C(a.r, b.l);
res.last_dec = true;
}
else if (a.r >= b.l && a.last_inc) {
res.ans += C(a.r, b.l);
res.last_inc = true;
}
res.first_dec = a.first_dec;
res.first_inc = a.first_inc;
return res;
}
if (a.r <= b.l && a.last_dec && b.first_inc) {
res.ans += C(a.r, b.l);
}
if (a.r >= b.l && a.last_inc && b.first_dec) {
res.ans += C(a.r, b.l);
}
res.first_dec = a.first_dec;
res.first_inc = a.first_inc;
res.last_dec = b.last_dec;
res.last_inc = b.last_inc;
return res;
}
};
int n;
vector<node> st;
vector<ll> lazy;
public:
SegmentTree(int n) : n(n) {
st.resize(n << 2);
lazy.resize(n << 2, 0);
build(1, 1, n);
}
void build(int i, int l, int r) {
if (l == r) {
st[i] = node(l);
return;
}
int m = (l + r) >> 1;
build(2 * i, l, m);
build(2 * i + 1, m + 1, r);
st[i] = st[2 * i] + st[2 * i + 1];
}
void setOne(int i, ll x) {
st[i].l += x;
st[i].r += x;
lazy[i] += x;
}
void down(int i) {
if (!lazy[i]) return;
setOne(2 * i, lazy[i]);
setOne(2 * i + 1, lazy[i]);
lazy[i] = 0;
}
void update(int i, int l, int r, int u, int v, ll x) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
return setOne(i, x);
}
down(i);
int m = (l + r) >> 1;
update(2 * i, l, m, u, v, x);
update(2 * i + 1, m + 1, r, u, v, x);
st[i] = st[2 * i] + st[2 * i + 1];
}
void update(int u, int v, ll x) {
return update(1, 1, n, u, v, x);
}
ll get() {
return st[1].ans;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
int l, r, x;
SegmentTree st(n);
for (int i = 1; i <= q; ++i) {
cin >> l >> r >> x;
st.update(l, r, x);
cout << st.get() << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
