#include <bits/stdc++.h>
using namespace std;
template<typename T, typename F>
struct ST {
vector<T> t;
vector<F> lz;
T def;
int n;
ST(){}
ST(int N) {
n=N;
t=vector<T>(4*n);
lz=vector<F>(4*n);
}
void build(T a[], int tl, int tr, int v) {
lz[v]=F(tl,tr);
if(tl==tr) {
t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(a,tl,tm,2*v);
build(a,tm+1,tr,2*v+1);
t[v]=merge(t[2*v],t[2*v+1]);
}
void push(int v) {
lz[2*v].compose(lz[v]);
lz[2*v+1].compose(lz[v]);
t[v]=lz[v].applyAggregate(t[v]);
int l=lz[v].l,r=lz[v].r;
lz[v]=F(l,r);
}
T query(int l, int r, int tl, int tr, int v) {
if(l>tr or r<tl)return def;
if(l<=tl and tr<=r)return lz[v].applyAggregate(t[v]);
push(v);
int tm=(tl+tr)/2;
return merge(query(l,r,tl,tm,2*v),query(l,r,tm+1,tr,2*v+1));
}
void update(int l, int r, F upd, int tl, int tr, int v) {
if(r<tl or tr<l)return;
if(l<=tl and tr<=r) {
lz[v].compose(upd);
return;
}
int tm=(tl+tr)/2;
push(v);
update(l,r,upd,tl,tm,2*v);
update(l,r,upd,tm+1,tr,2*v+1);
t[v]=merge(lz[2*v].applyAggregate(t[2*v]),lz[2*v+1].applyAggregate(t[2*v+1]));
}
void update(int at, T val, int tl, int tr, int v) {
if(tl==tr) {
t[v]=val;
lz[v]=F(tl,tr);
return;
}
int tm=(tl+tr)/2;
push(v);
if(at<=tm)update(at,val,tl,tm,2*v);
else update(at,val,tm+1,tr,2*v+1);
t[v]=merge(lz[2*v].applyAggregate(t[2*v]),lz[2*v+1].applyAggregate(t[2*v+1]));
}
T query(int l, int r){return query(l,r,0,n-1,1);}
void update(int l, int r, F upd){update(l,r,upd,0,n-1,1);}
void update(int at, T val){update(at,val,0,n-1,1);}
void build(T a[]){build(a,0,n-1,1);}
};
#define int long long
struct node {
int Lval, Rval;
int Ld=0, Li=0, Rd=0,Ri=0;
long long ans=0;
int sz=0;
node(){}
node(int val) {
sz=Ld=Li=Rd=Ri=1;
ans=1;
Lval=Rval=val;
}
};
node merge(node L, node R) {
if(L.sz == 0)return R;
else if(R.sz == 0)return L;
node res;
res.Lval = L.Lval;
res.Rval = R.Rval;
res.sz = L.sz+R.sz;
res.Ld = L.Ld;
res.Li = L.Li;
res.Rd = R.Rd;
res.Ri = R.Ri;
res.ans = L.ans+R.ans;
if(L.Rval > R.Lval) {
res.ans -= L.Rd*(L.Rd+1)/2;
res.ans -= R.Li*(R.Li+1)/2;
long long sz = L.Rd + R.Li;
res.ans += sz*(sz+1)/2;
if(R.sz == R.Li) {
if(R.sz%2 == 1) {
res.Ri = sz;
}
else {
res.Rd = sz;
}
}
if(L.sz == L.Rd) {
if(L.sz%2 == 1) {
res.Ld = sz;
}
else {
res.Li = sz;
}
}
}
else if(L.Rval < R.Lval) {
res.ans -= L.Ri*(L.Ri+1)/2;
res.ans -= R.Ld*(R.Ld+1)/2;
long long sz = L.Ri + R.Ld;
res.ans += sz*(sz+1)/2;
if(R.sz == R.Ld) {
if(R.sz%2 == 1) {
res.Rd = sz;
}
else {
res.Ri = sz;
}
}
if(L.sz == L.Ri) {
if(L.sz%2 == 1) {
res.Li = sz;
}
else {
res.Ld = sz;
}
}
}
return res;
}
struct F {
int add=0, mult=0;
int l, r;
F(){}
F(int tl, int tr){}
node applyAggregate(node T) {
if(mult%2 == 1) {
T.Rval*=-1;
T.Lval*=-1;
swap(T.Rd, T.Ri);
swap(T.Ld, T.Li);
}
T.Rval += add;
T.Lval += add;
return T;
}
void compose(F parent) {
if(parent.mult%2 == 1) {
add*=-1;
mult+=parent.mult;
}
add+=parent.add;
}
};
signed main () {
int n,q;
cin >> n >> q;
node A[n];
ST<node, F> st(n);
for(int i =0 ;i<n;i++) {
int val;
cin >> val;
A[i] = node(val);
}
st.build(A);
while(q--) {
char c;
cin >> c;
if(c=='?'){
int l, r;
cin >> l >> r;
l--,r--;
cout << st.query(l, r).ans << "\n";
}
else if(c == '*') {
int l, r;
cin >> l >> r;
l--,r--;
F upd;
upd.mult = 1;
// for(int i = l;i<=r;i++) {
// A[i]*=-1;
// update(i, upd);
// }
st.update(l, r, upd);
}
else if(c == '+') {
int l, r, val;
cin >> l >> r >> val;
l--,r--;
F upd;
upd.add = val;
st.update(l, r, upd);
//for(int i = l;i<=r;i++) {
// A[i]+=val;
// update(i, upd);
//}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
2652 KB |
Output is correct |
2 |
Correct |
11 ms |
2776 KB |
Output is correct |
3 |
Correct |
11 ms |
2652 KB |
Output is correct |
4 |
Correct |
11 ms |
2752 KB |
Output is correct |
5 |
Correct |
9 ms |
2648 KB |
Output is correct |
6 |
Correct |
4 ms |
348 KB |
Output is correct |
7 |
Correct |
10 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
830 ms |
137596 KB |
Output is correct |
2 |
Correct |
194 ms |
2608 KB |
Output is correct |
3 |
Correct |
742 ms |
141028 KB |
Output is correct |
4 |
Correct |
939 ms |
140880 KB |
Output is correct |
5 |
Correct |
822 ms |
140724 KB |
Output is correct |
6 |
Correct |
911 ms |
140736 KB |
Output is correct |
7 |
Correct |
800 ms |
137716 KB |
Output is correct |
8 |
Correct |
836 ms |
140788 KB |
Output is correct |
9 |
Correct |
752 ms |
140628 KB |
Output is correct |
10 |
Correct |
660 ms |
140872 KB |
Output is correct |
11 |
Correct |
761 ms |
140704 KB |
Output is correct |
12 |
Correct |
772 ms |
140628 KB |
Output is correct |
13 |
Correct |
562 ms |
140884 KB |
Output is correct |
14 |
Correct |
574 ms |
140808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
2652 KB |
Output is correct |
2 |
Correct |
11 ms |
2776 KB |
Output is correct |
3 |
Correct |
11 ms |
2652 KB |
Output is correct |
4 |
Correct |
11 ms |
2752 KB |
Output is correct |
5 |
Correct |
9 ms |
2648 KB |
Output is correct |
6 |
Correct |
4 ms |
348 KB |
Output is correct |
7 |
Correct |
10 ms |
2652 KB |
Output is correct |
8 |
Correct |
268 ms |
45956 KB |
Output is correct |
9 |
Correct |
254 ms |
45904 KB |
Output is correct |
10 |
Correct |
290 ms |
47196 KB |
Output is correct |
11 |
Correct |
210 ms |
46748 KB |
Output is correct |
12 |
Correct |
325 ms |
47032 KB |
Output is correct |
13 |
Correct |
261 ms |
47188 KB |
Output is correct |
14 |
Correct |
248 ms |
47200 KB |
Output is correct |
15 |
Correct |
282 ms |
45924 KB |
Output is correct |
16 |
Correct |
269 ms |
47084 KB |
Output is correct |
17 |
Correct |
284 ms |
47184 KB |
Output is correct |
18 |
Correct |
190 ms |
46944 KB |
Output is correct |
19 |
Correct |
169 ms |
46932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
2652 KB |
Output is correct |
2 |
Correct |
11 ms |
2776 KB |
Output is correct |
3 |
Correct |
11 ms |
2652 KB |
Output is correct |
4 |
Correct |
11 ms |
2752 KB |
Output is correct |
5 |
Correct |
9 ms |
2648 KB |
Output is correct |
6 |
Correct |
4 ms |
348 KB |
Output is correct |
7 |
Correct |
10 ms |
2652 KB |
Output is correct |
8 |
Correct |
830 ms |
137596 KB |
Output is correct |
9 |
Correct |
194 ms |
2608 KB |
Output is correct |
10 |
Correct |
742 ms |
141028 KB |
Output is correct |
11 |
Correct |
939 ms |
140880 KB |
Output is correct |
12 |
Correct |
822 ms |
140724 KB |
Output is correct |
13 |
Correct |
911 ms |
140736 KB |
Output is correct |
14 |
Correct |
800 ms |
137716 KB |
Output is correct |
15 |
Correct |
836 ms |
140788 KB |
Output is correct |
16 |
Correct |
752 ms |
140628 KB |
Output is correct |
17 |
Correct |
660 ms |
140872 KB |
Output is correct |
18 |
Correct |
761 ms |
140704 KB |
Output is correct |
19 |
Correct |
772 ms |
140628 KB |
Output is correct |
20 |
Correct |
562 ms |
140884 KB |
Output is correct |
21 |
Correct |
574 ms |
140808 KB |
Output is correct |
22 |
Correct |
268 ms |
45956 KB |
Output is correct |
23 |
Correct |
254 ms |
45904 KB |
Output is correct |
24 |
Correct |
290 ms |
47196 KB |
Output is correct |
25 |
Correct |
210 ms |
46748 KB |
Output is correct |
26 |
Correct |
325 ms |
47032 KB |
Output is correct |
27 |
Correct |
261 ms |
47188 KB |
Output is correct |
28 |
Correct |
248 ms |
47200 KB |
Output is correct |
29 |
Correct |
282 ms |
45924 KB |
Output is correct |
30 |
Correct |
269 ms |
47084 KB |
Output is correct |
31 |
Correct |
284 ms |
47184 KB |
Output is correct |
32 |
Correct |
190 ms |
46944 KB |
Output is correct |
33 |
Correct |
169 ms |
46932 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
1061 ms |
137840 KB |
Output is correct |
37 |
Correct |
1034 ms |
140880 KB |
Output is correct |
38 |
Correct |
682 ms |
139980 KB |
Output is correct |
39 |
Correct |
995 ms |
141008 KB |
Output is correct |
40 |
Correct |
952 ms |
137888 KB |
Output is correct |
41 |
Correct |
901 ms |
141012 KB |
Output is correct |
42 |
Correct |
857 ms |
138060 KB |
Output is correct |
43 |
Correct |
971 ms |
140864 KB |
Output is correct |
44 |
Correct |
1064 ms |
140880 KB |
Output is correct |
45 |
Correct |
1020 ms |
141140 KB |
Output is correct |
46 |
Correct |
935 ms |
140876 KB |
Output is correct |
47 |
Correct |
848 ms |
141240 KB |
Output is correct |