#include <bits/stdc++.h>
#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)
#define WTF cout << "WTF" << endl
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define U(x) (x < 0 ? -1 : (x == 0 ? 0 : 1))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
#define lc now << 1
#define rc now << 1 | 1
const int N = 5e5 + 2;
LL n, q;
LL ns[N];
struct NumTree {
PLL lz[N << 2];
void build() {
F0R(i, (N << 2)) lz[i].F = 1;
return;
}
void addLz(int now, PII v) {
lz[now].F *= v.F;
lz[now].S *= v.F;
lz[now].S += v.S;
return;
}
void shift(int now) {
addLz(lc, lz[now]);
addLz(rc, lz[now]);
lz[now].F = 1; lz[now].S = 0;
}
void upd(int lq, int rq, PLL val, int now = 1, int ls = 0, int rs = n - 1) {
if (rq < lq || rq < ls || rs < lq) return;
if (lq <= ls && rs <= rq) return addLz(now, val);
int mid = (ls + rs) >> 1;
shift(now);
upd(lq, rq, val, lc, ls, mid); upd(lq, rq, val, rc, mid + 1, rs);
return;
}
LL get(int id, int now = 1, int ls = 0, int rs = n - 1) {
if (ls == rs) return ns[ls] * lz[now].F + lz[now].S;
int mid = (ls + rs) >> 1;
shift(now);
if (id <= mid) return get(id, lc, ls, mid);
return get(id, rc, mid + 1, rs);
}
} num;
struct Node {
LL lft, rgt;
LL pref, suff, len;
LL ans;
};
inline Node operator + (const Node &a, const Node &b) {
if (!a.len) return b;
if (!b.len) return a;
Node c;
c.lft = a.lft;
c.rgt = b.rgt;
c.len = a.len + b.len;
c.pref = a.pref + (a.pref == a.len && (!!U(a.rgt) && !!U(b.lft)) ? b.pref : 0);
c.suff = b.suff + (b.suff == b.len && (!!U(a.rgt) && !!U(b.lft)) ? a.suff : 0);
c.ans = a.ans + b.ans + ((!!U(a.rgt) && !!U(b.lft))? (LL)a.suff * b.pref : 0LL);
return c;
}
struct ZigZagTree {
Node tree[N << 2];
bool lz[N];
void addLz(int now) {
lz[now] ^= 1;
tree[now].lft *= -1;
tree[now].rgt *= -1;
return;
}
inline void shift(int now) {
if (!lz[now]) return;
addLz(lc);
addLz(rc);
lz[now] = 0;
return;
}
void build(int now = 1, int ls = 0, int rs = n - 2) {
if (ls == rs) {
tree[now].lft = tree[now].rgt = ns[ls + 1] - ns[ls];
tree[now].len = 1;
tree[now].suff = tree[now].pref = tree[now].ans = (!!U(ns[ls + 1] - ns[ls]));
return;
}
int mid = (ls + rs) >> 1;
build(lc, ls, mid); build(rc, mid + 1, rs);
tree[now] = tree[lc] + tree[rc];
return;
}
void change(int id, LL val, int now = 1, int ls = 0, int rs = n - 2) {
if (ls == rs) {
tree[now].lft = tree[now].rgt = val;
tree[now].pref = tree[now].suff = tree[now].ans = !!val;
return;
}
int mid = (ls + rs) >> 1;
shift(now);
if (id <= mid) change(id, val, lc, ls, mid);
else change(id, val, rc, mid + 1, rs);
tree[now] = tree[lc] + tree[rc];
return;
}
void mult(int lq, int rq, int now = 1, int ls = 0, int rs = n - 2) {
if (rq < lq || rq < ls || rs < lq) return;
if (lq <= ls && rs <= rq) return addLz(now);
shift(now);
int mid = (ls + rs) >> 1;
mult(lq, rq, lc, ls, mid); mult(lq, rq, rc, mid + 1, rs);
tree[now] = tree[lc] + tree[rc];
return;
}
Node get(int lq, int rq, int now = 1, int ls = 0, int rs = n - 2) {
if (rq < lq || rq < ls || rs < lq) return tree[0];
if (lq <= ls && rs <= rq) return tree[now];
int mid = (ls + rs) >> 1;
shift(now);
return get(lq, rq, lc, ls, mid) + get(lq, rq, rc, mid + 1, rs);
}
} zig;
void init() {
cin >> n >> q;
F0R(i, n) cin >> ns[i];
num.build();
zig.build();
return;
}
void cross() {
int l, r;
cin >> l >> r;
l--; r--;
num.upd(l, r, {-1, 0});
zig.mult(l, r - 1);
if (l) {
LL p1 = num.get(l - 1);
LL p2 = num.get(l);
zig.change(l - 1, p2 - p1);
}
if (r != n - 1) {
LL p1 = num.get(r);
LL p2 = num.get(r + 1);
zig.change(r, p2 - p1);
}
return;
}
void pls() {
int l, r, v;
cin >> l >> r >> v;
l--; r--;
num.upd(l, r, {1, v});
if (l) {
LL p1 = num.get(l - 1);
LL p2 = num.get(l);
zig.change(l - 1, p2 - p1);
}
if (r != n - 1) {
LL p1 = num.get(r);
LL p2 = num.get(r + 1);
zig.change(r, p2 - p1);
}
}
void query() {
int l, r;
cin >> l >> r;
l--; r--;
//cout << l << ", " << r - 1 << endl;
cout << zig.get(l, r - 1).ans + (r - l + 1) << endl;
return;
}
int main() {
IOS;
init();
while(q--) {
char tp; cin >> tp;
if (tp == '*') cross();
if (tp == '+') pls();
if (tp == '?') query();
//F0R(i, n) cout << num.get(i) << ' '; cout << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
32468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
888 ms |
84440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
32468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
32468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
