// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, m, q, L, R, id, a[N];
ll vl, b[N], vd[4 * N];
bool dv[4 * N], tp;
struct node {
ll ans;
int pr;
int sf;
ll fr;
ll ls;
int len;
bool add;
};
node v[4 * N], bs = {0, 0, 0, 0, 0, 0, 0};
node merge(node a, node b) {
node c;
c.add = 0;
c.ans = a.ans + b.ans;
c.fr = a.fr, c.ls = b.ls;
c.sf = b.sf, c.pr = a.pr;
if ((a.ls < 0 && b.fr > 0) || (a.ls > 0 && b.fr < 0)) {
if (b.sf == b.len) c.sf += a.sf;
if (a.pr == a.len) c.pr += b.pr;
c.ans += a.sf * b.pr;
}
return c;
}
void build(tree) {
if (l == r) {
v[h].len = 1;
v[h].fr = b[l];
v[h].ls = b[l];
if (v[h].fr) {
v[h].pr = v[h].sf = v[h].ans = 1;
}
return ;
}
build(left), build(right);
v[h] = merge(v[lf], v[rf]);
v[h].len = v[lf].len + v[rf].len;
}
void shift(tree) {
if (v[h].add) {
v[lf].add ^= 1, v[lf].fr *= -1; v[lf].ls *= -1;
v[rf].add ^= 1, v[rf].fr *= -1; v[rf].ls *= -1;
v[h].add = 0;
return ;
}
}
node get(tree) {
if (r < L || R < l) return bs;
if (L <= l && r <= R) return v[h];
shift(h, l, r);
return merge(get(left), get(right));
}
void upd(tree) {
if (r < id || id < l) return ;
if (l == id && id == r) {
v[h].fr += vl;
v[h].ls += vl;
if (v[h].fr) {
v[h].pr = v[h].sf = v[h].ans = 1;
}
else {
v[h].pr = v[h].sf = v[h].ans = 0;
}
return ;
}
shift(h, l, r);
upd(left), upd(right);
v[h] = merge(v[lf], v[rf]);
}
void upd_(tree) {
if (r < L || R < l) return ;
if (L <= l && r <= R) {
v[h].add ^= 1;
v[h].fr *= -1;
v[h].ls *= -1;
return ;
}
shift(h, l, r);
upd_(left), upd_(right);
v[h] = merge(v[lf], v[rf]);
}
void bld(tree) {
if (l == r) { vd[h] = a[l]; return ; }
bld(left); bld(right);
}
void shf(tree) {
if (dv[h]) {
vd[lf] = vd[lf] * -1 + vd[h];
vd[rf] = vd[rf] * -1 + vd[h];
dv[lf] ^= 1, dv[rf] ^= 1;
}
else {
vd[lf] += vd[h];
vd[rf] += vd[h];
}
vd[h] = dv[h] = 0;
return ;
}
void up(tree) {
if (r < L || R < l) return ;
if (L <= l && r <= R) {
if (tp == 0) {
vd[h] += vl;
}
else
if (tp == 1) {
vd[h] *= -1;
dv[h] ^= 1;
}
return ;
}
shf(h, l, r);
up(left), up(right);
}
int G(tree) {
if (l == r) return vd[h];
shf(h, l, r);
if (id <= mf)
return G(left);
return G(right);
}
main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (1 < i) {
b[i - 1] = a[i - 1] - a[i];
}
}
m = n - 1, build(1, 1, m), bld(1, 1, n);
for (int i = 1; i <= q; ++i) {
char c;
cin >> c;
if (c == '+') {
cin >> L >> R >> vl; tp = 0, up(1, 1, n), --L;
vl = -vl, id = L; if (1 <= L) upd(1, 1, m);
vl = -vl, id = R; if (R <= m) upd(1, 1, m);
}
else
if (c == '*') {
vl = 0;
cin >> L >> R;
if (1 < L) {
id = L;
ll Al = G(1, 1, n);
id = L - 1;
vl = 2 * Al;
upd(1, 1, m);
}
if (R < n) {
id = R;
ll Ar = G(1, 1, n);
vl = -2 * Ar;
upd(1, 1, m);
}
tp = 1, up(1, 1, n);
--R, upd_(1, 1, m);
}
else
if (c == '?') {
cin >> L >> R; --R;
cout << get(1, 1, m).ans + R - L + 2 << "\n";
}
}
}
Compilation message
Main.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
153 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
689 ms |
74256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
