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
| #include <cstdio>
#include <algorithm>
struct segment_tree
{
int lmax, rmax, sum;
void operator()(const int x) { lmax = rmax = sum = x; }
void operator()(const int l, const int r, const int m)
{ lmax = l, rmax = r, sum = m; }
} s[50001*4];
int n, m, len, st, ed;
void build(const int p, const int lef, const int rig)
{
s[p](rig-lef+1);
if (lef == rig) return;
const int mid((lef+rig)>>1);
build(p*2, lef, mid);
build(p*2+1, mid+1, rig);
}
void update_child(const int p, const int lef, const int rig)
{
if (p*2 >= 50001*4)
return;
if (s[p].sum == 0)
s[p*2](0), s[p*2+1](0);
else if (s[p].sum == rig-lef+1)
{
const int mid((lef+rig)>>1);
s[p*2](mid-lef+1);
s[p*2+1](rig-mid);
}
}
void update_self(const int p, const int lef, const int rig)
{
if (p*2 >= 50001*4)
{
s[p](0, 0, 0);
return;
}
s[p](s[p*2].lmax, s[p*2+1].rmax, s[p*2].sum+s[p*2+1].sum);
const int mid((lef+rig)>>1);
if (s[p*2].lmax == mid-lef+1)
s[p].lmax += s[p*2+1].lmax;
if (s[p*2+1].rmax == rig-mid)
s[p].rmax += s[p*2].rmax;
}
void remove(const int p, const int lef, const int rig, const int st, const int ed)
{
update_child(p, lef, rig);
if (lef == st && ed == rig)
s[p](rig-lef+1);
else
{
const int mid((lef+rig)>>1);
if (st <= mid) remove(p*2, lef, mid, st, std::min(mid, ed));
if (mid+1 <= ed) remove(p*2+1, mid+1, rig, std::max(st, mid+1), ed);
update_self(p, lef, rig);
}
}
void insert(const int p, const int lef, const int rig, const int st, const int ed)
{
update_child(p, lef, rig);
if (lef == st && ed == rig)
s[p](0);
else
{
const int mid((lef+rig)>>1);
if (st <= mid) insert(p*2, lef, mid, st, std::min(mid, ed));
if (mid+1 <= ed) insert(p*2+1, mid+1, rig, std::max(st, mid+1), ed);
update_self(p, lef, rig);
}
}
bool query(const int p, const int lef, const int rig)
{
update_child(p, lef, rig);
if (s[p].sum < len) return false;
if (s[p].sum == rig-lef+1)
{
insert(p, lef, rig, lef, lef+len-1);
update_self(p, lef, rig);
printf("%dn", lef);
return true;
}
const int mid((lef+rig)>>1);
//From Left:
if (query(p*2, lef, mid))
{
update_self(p, lef, rig);
return true;
}
//Left + Right:
if (s[p*2].rmax+s[p*2+1].lmax >= len)
{
const int rmax = s[p*2].rmax;
printf("%dn", mid-rmax+1);
insert(p*2, lef, mid, mid-rmax+1, mid);
insert(p*2+1, mid+1, rig, mid+1, mid+len-rmax);
update_self(p, lef, rig);
return true;
}
//From Right:
if (query(p*2+1, mid+1, rig))
{
update_self(p, lef, rig);
return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
build(1, 1, n);
for (int i = 0, op, a; i < m; ++i)
{
scanf("%d%d", &op, &len);
if (op == 1)
{
st = 1, ed = n;
if (!query(1, 1, n))
printf("0n");
}
else
{
scanf("%d", &a);
remove(1, 1, n, len, len+a-1);
}
}
}
|
