Submission #635393

#TimeUsernameProblemLanguageResultExecution timeMemory
635393NothingXDSubtree (INOI20_subtree)C++17
0 / 100
1 ms340 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...