1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
| #include <bits/stdc++.h>
using namespace std;
const static int maxn = 2e5 + 10;
int n, m, a[maxn];
struct node {
int l, r;
int c0, c1;
int lx0, rx0, mx0;
int lx1, rx1, mx1;
int tag_cover, tag_inverse;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define c0(x) tr[x].c0
#define c1(x) tr[x].c1
#define lx0(x) tr[x].lx0
#define rx0(x) tr[x].rx0
#define lx1(x) tr[x].lx1
#define rx1(x) tr[x].rx1
#define mx0(x) tr[x].mx0
#define mx1(x) tr[x].mx1
#define tag_cover(x) tr[x].tag_cover
#define tag_inverse(x) tr[x].tag_inverse
#define lc(x) x * 2
#define rc(x) x * 2 + 1
} tr[maxn << 2];
void cover(int p, int cnt, int opt) {
if (opt == 0) {
c0(p) = cnt;
lx0(p) = rx0(p) = mx0(p) = cnt;
c1(p) = 0;
lx1(p) = rx1(p) = mx1(p) = 0;
} else {
c0(p) = 0;
lx0(p) = rx0(p) = mx0(p) = 0;
c1(p) = cnt;
lx1(p) = rx1(p) = mx1(p) = cnt;
}
}
void inverse(int p) {
swap(c0(p), c1(p));
swap(lx0(p), lx1(p));
swap(rx0(p), rx1(p));
swap(mx0(p), mx1(p));
}
void down(int p, int lcnt, int rcnt) {
if (tag_cover(p) != -1) {
cover(lc(p), lcnt, tag_cover(p));
cover(rc(p), rcnt, tag_cover(p));
tag_cover(lc(p)) = tag_cover(rc(p)) = tag_cover(p);
tag_inverse(lc(p)) = tag_inverse(rc(p)) = 0;
tag_cover(p) = -1;
}
if (tag_inverse(p) == 1) {
inverse(lc(p));
inverse(rc(p));
tag_inverse(lc(p)) ^= 1;
tag_inverse(rc(p)) ^= 1;
tag_inverse(p) = 0;
}
}
void up(int p, int lcnt, int rcnt) {
c0(p) = c0(lc(p)) + c0(rc(p));
c1(p) = c1(lc(p)) + c1(rc(p));
lx0(p) = (mx0(lc(p)) == lcnt ? lcnt + lx0(rc(p)) : lx0(lc(p)));
rx0(p) = (mx0(rc(p)) == rcnt ? rcnt + rx0(lc(p)) : rx0(rc(p)));
mx0(p) = max(max(mx0(lc(p)), mx0(rc(p))), rx0(lc(p)) + lx0(rc(p)));
lx1(p) = (mx1(lc(p)) == lcnt ? lcnt + lx1(rc(p)) : lx1(lc(p)));
rx1(p) = (mx1(rc(p)) == rcnt ? rcnt + rx1(lc(p)) : rx1(rc(p)));
mx1(p) = max(max(mx1(lc(p)), mx1(rc(p))), rx1(lc(p)) + lx1(rc(p)));
}
void build(int p, int l, int r) {
l(p) = l, r(p) = r, tag_cover(p) = -1;
if (l == r) {
cover(p, 1, a[l]);
return;
}
int mid = (l + r) / 2;
int lcnt = mid - l + 1, rcnt = r - mid;
build(lc(p), l, mid), build(rc(p), mid + 1, r);
up(p, lcnt, rcnt);
}
void update(int p, int l, int r, int opt) {
int mid = (l(p) + r(p)) / 2;
int lcnt = r(lc(p)) - l(lc(p)) + 1, rcnt = r(rc(p)) - l(rc(p)) + 1;
if (l(p) >= l && r(p) <= r) {
int cnt = r(p) - l(p) + 1;
if (opt == 0) {
cover(p, cnt, 0);
tag_cover(p) = 0;
tag_inverse(p) = 0;
} else if (opt == 1) {
cover(p, cnt, 1);
tag_cover(p) = 1;
tag_inverse(p) = 0;
} else {
inverse(p);
tag_inverse(p) ^= 1;
}
return;
}
down(p, lcnt, rcnt);
if (l <= mid) update(lc(p), l, r, opt);
if (r > mid) update(rc(p), l, r, opt);
up(p, lcnt, rcnt);
}
int ask_c1(int p, int l, int r) {
int lcnt = r(lc(p)) - l(lc(p)) + 1, rcnt = r(rc(p)) - l(rc(p)) + 1, ans = 0;
if (l(p) >= l && r(p) <= r) return c1(p);
down(p, lcnt, rcnt);
int mid = (l(p) + r(p)) / 2;
if (l <= mid) ans += ask_c1(lc(p), l, r);
if (r > mid) ans += ask_c1(rc(p), l, r);
return ans;
}
node ask_mx(int p, int l, int r) {
int lcnt = r(lc(p)) - l(lc(p)) + 1, rcnt = r(rc(p)) - l(rc(p)) + 1;
if (l(p) >= l && r(p) <= r) return tr[p];
down(p, lcnt, rcnt);
int mid = (l(p) + r(p)) / 2;
if (l > mid)
return ask_mx(rc(p), l, r);
else if (r <= mid)
return ask_mx(lc(p), l, r);
else {
node ans, a = ask_mx(lc(p), l, r), b = ask_mx(rc(p), l, r);
ans.mx1 = max(max(a.mx1, b.mx1), a.rx1 + b.lx1);
ans.lx1 = a.mx1 == lcnt ? lcnt + b.lx1 : a.lx1;
ans.rx1 = b.mx1 == rcnt ? rcnt + a.rx1 : b.rx1;
return ans;
}
}
int main() {
int opt, x, y;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
while (m--) {
scanf("%d%d%d", &opt, &x, &y);
++x, ++y;
if (opt < 3) {
update(1, x, y, opt);
} else if (opt == 3) {
cout << ask_c1(1, x, y) << endl;
} else {
cout << ask_mx(1, x, y).mx1 << endl;
}
}
return 0;
}
|