#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second
const int maxn = 3e5 + 10;
struct Seg{
ll ans, x, y;
int l, r, sz;
Seg(){};
Seg(ll x, ll y, int l, int r, int sz, ll ans){
this->l = l;
this->r = r;
this->x = x;
this->y = y;
this->sz = sz;
this->ans = ans;
}
};
Seg operator +(Seg a, Seg b){
Seg res;
if (a.sz == 0) return b;
if (b.sz == 0) return a;
res.ans = a.ans + b.ans;
res.sz = a.sz + b.sz;
res.x = a.x;
res.y = b.y;
res.l = a.l;
res.r = b.r;
if (a.y > b.x){
res.ans += 1ll * (max(0, -a.r) + 1) * (max(0, b.l) + 1);
if (a.l == 0 && a.sz == 1){
res.l = -max(b.l, 0) - 1;
}
else if (abs(a.l) == -a.r && abs(a.l) == a.sz - 1){
if (a.l < 0) res.l = a.l - max(0, b.l) - 1;
else res.l = a.l + max(0, b.l) + 1;
}
if (b.r == 0 && b.sz == 1){
res.r = max(-a.r, 0) + 1;
}
else if (b.l == abs(b.r) && abs(b.r) == b.sz - 1){
if (b.r < 0) res.r = b.r - max(0, -a.r) - 1;
else res.r = b.r + max(0, -a.r) + 1;
}
}
else if (a.y < b.x){
res.ans += 1ll * (max(0, a.r) + 1) * (max(0, -b.l) + 1);
if (a.l == 0 && a.sz == 1){
res.l = max(-b.l, 0) + 1;
}
else if (abs(a.l) == a.r && abs(a.l) == a.sz - 1){
if (a.l < 0) res.l = a.l - max(0, -b.l) - 1;
else res.l = a.l + max(0, -b.l) + 1;
}
if (b.r == 0 && b.sz == 1){
res.r = -max(a.r, 0) - 1;
}
else if (-b.l == abs(b.r) && abs(b.r) == b.sz - 1){
if (b.r < 0) res.r = b.r - max(0, a.r) - 1;
else res.r = b.r + max(0, a.r) + 1;
}
}
return res;
}
int n, q, a[maxn];
pll lazy[maxn << 2];
Seg seg[maxn << 2];
void build(int v, int l, int r){
if (l + 1 == r){
seg[v] = Seg(a[l], a[l], 0, 0, 1, 1);
return;
}
int mid = (l + r) >> 1;
build(v << 1, l, mid);
build(v << 1 | 1, mid, r);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
// debug(l, r, seg[v].x, seg[v].y, seg[v].l, seg[v].r, seg[v].sz, seg[v].ans);
}
void shift(int v, int l, int r);
void add(int v, int l, int r, int ql, int qr, int val){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v].x += val;
seg[v].y += val;
lazy[v].F += val;
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
add(v << 1, l, mid, ql, qr, val);
add(v << 1 | 1, mid, r, ql, qr, val);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
void reverse(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v].x = -seg[v].x;
seg[v].y = -seg[v].y;
seg[v].l = -seg[v].l;
seg[v].r = -seg[v].r;
lazy[v].S++;
lazy[v].F = -lazy[v].F;
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
reverse(v << 1, l, mid, ql, qr);
reverse(v << 1 | 1, mid, r, ql, qr);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
Seg get(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return Seg(0, 0, 0, 0, 0, 0);
if (ql <= l && r <= qr) return seg[v];
shift(v, l, r);
int mid = (l + r) >> 1;
return get(v << 1, l, mid, ql, qr)
+ get(v << 1 | 1, mid, r, ql, qr);
}
void shift(int v, int l, int r){
if (lazy[v].S & 1){
int mid = (l + r) >> 1;
reverse(v << 1, l, mid, l, mid);
reverse(v << 1 | 1, mid, r, mid, r);
lazy[v].S = 0;
}
if (lazy[v].F == 0) return;
int mid = (l + r) >> 1;
add(v << 1, l, mid, l, mid, lazy[v].F);
add(v << 1 | 1, mid, r, mid, r, lazy[v].F);
lazy[v].F = 0;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
build(1, 1, n+1);
while(q--){
char t; int l, r; cin >> t >> l >> r;
if (t == '*') reverse(1, 1, n+1, l, r+1);
else if (t == '+'){
int x; cin >> x;
add(1, 1, n+1, l, r+1, x);
}
else{
cout << get(1, 1, n+1, l, r+1).ans << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
610 ms |
59640 KB |
Output is correct |
| 2 |
Correct |
52 ms |
2468 KB |
Output is correct |
| 3 |
Incorrect |
530 ms |
62856 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
