2023NOIP A layer joint test 30 A. Strawberry Train
Article directory
- 2023NOIP A layer joint test 30 A. Strawberry Train
-
- The general idea of the topic
- Ideas
- code
The main idea of the title
Given a sequence
a
a
a, there is
m
m
m operations, the
[
l
,
r
]
[l , r]
Each of [l,r]
a
i
a_i
ai? becomes
m
a
x
(
a
i
,
v
)
max (a_i, v)
max(ai?,v)
n
≤
1
0
5
,
m
≤
1
0
7
n \le 10 ^5 , m \le 10^7
n≤105,m≤107
Ideas
For each number, just compare it with the maximum value in each query that involves it.
We need to find an operation that can
O
(
1
)
O(1)
O(1) modification,
O
(
n
log
?
2
n
)
O(n\log_2n)
O(nlog2?n) query.
Consider using
s
t
st
st table, assuming
s
t
i
,
j
st_{i , j}
sti,j? means in
[
i
,
i
+
2
j
?
1
]
[i , i + 2^j – 1]
The maximum value in [i,i + 2j?1]
Ask every time
l
,
r
,
v
l , r , v
l,r,v , suppose
l
g
=
log
?
2
(
r
?
l
+
1
)
lg = \log_2(r – l + 1)
lg=log2?(r?l + 1)
Each modification:
s
t
l
,
l
g
=
max
?
(
s
t
l
,
l
g
,
v
)
s
t
r
?
2
l
g
+
1
,
l
g
=
max
?
(
s
t
r
?
2
l
g
+
1
,
l
g
,
v
)
st_{l , lg} = \max (st_{l , lg} , v) \
ewline st_{r – 2^{lg} + 1 , lg} = \max (st_{r – 2 ^{lg} + 1 , lg} , v)
stl,lg?=max(stl,lg?,v)str?2lg + 1,lg?=max(str?2lg + 1,lg?,v)
Finally updated from top to bottom:
s
t
i
,
j
=
max
?
(
s
t
i
,
j
,
s
t
i
,
j
+
1
)
s
t
i
+
2
j
,
j
=
max
?
(
s
t
i
+
2
j
,
j
,
s
t
i
,
j
+
1
)
st_{i , j} = \max (st_{i , j} , st_{i , j + 1}) \
ewline st_{i + 2^j , j} = \max (st_{i + 2^j , j} , st_{i , j + 1})
sti,j?=max(sti,j?,sti,j + 1?)sti + 2j,j?=max(sti + 2j,j?,sti,j + 1?)
code
#include <bits/stdc + + .h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x + + )
#define fd(x, y, z) for(int x = y; x >= z; x --)
using namespace std;
const int N = 1e5 + 5;
LL a[N] , st[N][25];
namespace Maker{<!-- -->
unsigned int x0, seed;
void init() {<!-- --> scanf ("%u%u" , & amp;x0 , & amp;seed); }
inline unsigned int getnum(){<!-- -->
x0 = (x0 << 3) ^ x0;
x0 = ((x0 >> 5) + seed) ^ x0;
return x0;
}
}
int n,m,typ;
int main () {<!-- -->
freopen ("train.in" , "r" , stdin);
freopen ("train.out" , "w" , stdout);
scanf ("%d%d%d" , & amp;n , & amp;m , & amp;typ);
fu (i , 1 , n) scanf ("%lld" , & amp;a[i]);
Maker::init();
fu (i , 1 , m) {<!-- -->
int l = Maker::getnum() % n + 1 , r = Maker::getnum() % n + 1;
LL v = Maker::getnum();
if (l > r) swap (l , r);
if(typ == 1) l = 1;
int lg = log2 (r - l + 1);
st[l][lg] = max (st[l][lg] , v);
st[r - (1 << lg) + 1][lg] = max (st[r - (1 << lg) + 1][lg] , v);
// cout << l << " " << r << " " << v << "\
";
// cout << lg << " ";
}
fd (j , 20 , 0) {<!-- -->
for (int i = 1 ; i + (1 << j) <= n ; i + + ) {<!-- -->
st[i][j] = max (st[i][j] , st[i][j + 1]);
st[i + (1 << j)][j] = max (st[i + (1 << j)][j] , st[i][j + 1]);
}
}
fu (i , 1 , n) printf ("%lld " , max (a[i] , st[i][0]));
return 0;
}