이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int ll
using ll = long long;
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 3e5+5;
struct Node {
ll ans, L, R;
int sz, LD, LU, RD, RU;
} seg[MXN<<2];
struct Lazy {
ll sum;
bool mul;
Lazy() {sum=0, mul=0;}
Lazy(ll a, bool b) {sum=a, mul=b;}
} lz[MXN<<2];
Node Merge(Node x, Node y) {
Node res;
res.L = x.L; res.R = y.R;
res.sz = x.sz+y.sz;
if(x.R<y.L) {
res.ans = (x.ans + y.ans + (ll)x.RU*y.LD);
res.LD = x.LD + (x.LD == x.sz && x.sz%2 == 0 ? y.LD : 0);
res.LU = x.LU + (x.LU == x.sz && x.sz%2 ? y.LD : 0);
res.RD = y.RD + (y.RD == y.sz && y.sz%2 ? x.RU : 0);
res.RU = y.RU + (y.RU == y.sz && y.sz%2 == 0 ? x.RU : 0);
}
else if(x.R>y.L) {
res.ans = (x.ans + y.ans + (ll)x.RD*y.LU);
res.LD = x.LD + (x.LD == x.sz && x.sz%2 ? y.LU : 0);
res.LU = x.LU + (x.LU == x.sz && x.sz%2 == 0 ? y.LU : 0);
res.RD = y.RD + (y.RD == y.sz && y.sz%2 == 0 ? x.RD : 0);
res.RU = y.RU + (y.RU == y.sz && y.sz%2 ? x.RD : 0);
}
else {
res.ans = (x.ans+y.ans);
res.LD = x.LD;
res.LU = x.LU;
res.RD = y.RD;
res.RU = y.RU;
}
return res;
}
int n, a[MXN];
void Build(int l=1, int r=n+1, int id=1) {
lz[id].sum = 0;
lz[id].mul = 0;
if(r-l == 1) {
seg[id].ans = 1;
seg[id].L = seg[id].R = a[l];
seg[id].sz = 1;
seg[id].LD = seg[id].LU = seg[id].RD = seg[id].RU = 1;
return;
}
Build(l, mid, lc);
Build(mid, r, rc);
seg[id] = Merge(seg[lc], seg[rc]);
}
void Apply(Lazy dat, int id) {
if(dat.mul) {
swap(seg[id].LD, seg[id].LU);
swap(seg[id].RD, seg[id].RU);
seg[id].L *= -1;
seg[id].R *= -1;
lz[id].mul ^= 1;
lz[id].sum *= -1;
}
seg[id].L += dat.sum;
seg[id].R += dat.sum;
lz[id].sum += dat.sum;
}
void Shift(int l, int r, int id) {
if(r-l>1) {
Apply(lz[id], lc);
Apply(lz[id], rc);
}
lz[id].sum = 0;
lz[id].mul = 0;
}
void Upd(int s, int e, Lazy x, int l=1, int r=n+1, int id=1) {
Shift(l, r, id);
if(s<=l && r<=e) {
Apply(x, id);
return;
}
if(s<mid) Upd(s,e,x, l, mid, lc);
if(e>mid) Upd(s,e,x, mid, r, rc);
seg[id] = Merge(seg[lc], seg[rc]);
}
Node Get(int s, int e, int l=1, int r=n+1, int id=1) {
Shift(l, r, id);
if(s<=l && r<=e) return seg[id];
if(e<=mid) return Get(s, e, l, mid, lc);
if(s>=mid) return Get(s, e, mid, r, rc);
return Merge(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}
int q;
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> q;
for(int i=1; i<=n; i++) cin >> a[i];
Build();
while(q--) {
char tp;
int l, r;
cin >> tp >> l >> r; r++;
if(tp == '+') {
int x;
cin >> x;
Upd(l, r, Lazy(x, 0));
}
else if(tp == '*') Upd(l, r, Lazy(0, 1));
else if(tp == '?') cout << Get(l, r).ans << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |