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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
using namespace std;
const int maxn = 2e+5 + 5;
int n, m;
int s[maxn << 2], tag[maxn << 2];
inline void pushup(int cur) {
s[cur] = s[cur << 1] + s[cur << 1|1];
}
inline void pushdown(int cur, int len) {
if (~tag[cur]) {
s[cur << 1] = tag[cur] * (len - (len >> 1));
s[cur << 1|1] = tag[cur] * (len >> 1);
tag[cur << 1] = tag[cur << 1|1] = tag[cur];
tag[cur] = -1;
}
}
void build(int cur, int l, int r) {
tag[cur] = -1;
if (l == r) {
s[cur] = 1;
return;
}
int mid = (l + r) >> 1;
build(cur << 1, l, mid);
build(cur << 1|1, mid + 1, r);
pushup(cur);
}
void update(int cur, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
s[cur] = v * (r - l + 1);
tag[cur] = v;
return;
}
int mid = (l + r) >> 1; pushdown(cur, r - l + 1);
if (L <= mid) update(cur << 1, l, mid, L, R, v);
if (R > mid) update(cur << 1|1, mid + 1, r, L, R, v);
pushup(cur);
}
int querys(int cur, int l, int r, int L, int R) {
if (L <= l && r <= R) return s[cur];
int mid = (l + r) >> 1, ret = 0; pushdown(cur, r - l + 1);
if (L <= mid) ret += querys(cur << 1, l, mid, L, R);
if (R > mid) ret += querys(cur << 1|1, mid + 1, r, L, R);
return ret;
}
int query(int lb, int rb, int k) {
if (lb > rb) return -1;
int l = 0, r = rb - lb;
while (l <= r) {
int mid = (l + r) >> 1;
if (querys(1, 1, n, lb, lb + mid) == k * (mid + 1)) l = mid + 1;
else r = mid - 1;
}
return l;
}
inline int rd() {
register int x = 0, c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return x;
}
int main() {
n = rd(); m = rd();
build(1, 1, n);
int opt, l1, r1, l2, r2;
while (m--) {
opt = rd();
if (opt == 0) {
l1 = rd(); r1 = rd();
update(1, 1, n, l1, r1, 0);
} else if (opt == 1) {
l1 = rd(); r1 = rd(); l2 = rd(); r2 = rd();
int s = querys(1, 1, n, l1, r1);
update(1, 1, n, l1, r1, 0);
int s_already = querys(1, 1, n, l2, r2);
if (s > (r2 - l2 + 1) - s_already) {
update(1, 1, n, l2, r2, 1); continue;
}
if (!s) continue;
while (true) {
int hed = 0;
if (querys(1, 1, n, l2, l2) == 1) {
hed = query(l2, r2, 1); l2 += hed;
}
hed = query(l2, r2, 0);
if (hed == -1) break;
if (hed > s) {
update(1, 1, n, l2, l2 + s - 1, 1);
break;
} else {
update(1, 1, n, l2, l2 + hed - 1, 1);
l2 += hed; s -= hed;
}
}
} else {
l1 = rd(); r1 = rd();
int ans = 0;
while (true) {
int hed = 0;
if (querys(1, 1, n, l1, l1) == 1) {
hed = query(l1, r1, 1); l1 += hed;
}
hed = query(l1, r1, 0);
if (hed == -1) break;
ans = max(ans, hed);
l1 += hed;
if (l1 > r1) break;
}
printf("%d\n", ans);
}
}
return 0;
}
|
