2023NOIP A层联测30 A. 草莓列车

联测30 A. 草莓列车"/>

2023NOIP A层联测30 A. 草莓列车

2023NOIP A层联测30 A. 草莓列车

文章目录

• 2023NOIP A层联测30 A. 草莓列车
• • 题目大意
  • 思路
  • code

题目大意

给定一个序列 a a a ，有 m m m 次操作，将 [ l , r ] [l , r] [l,r] 的每个 a i a_i ai​ 变为 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

思路

对于每个数，只用用它本身和每个涉及到它的查询里面的最大值比较就好了。

我们要找到一种操作，可以 O ( 1 ) O(1) O(1) 修改， O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2​n) 查询。

考虑用 s t st st 表，设 s t i , j st_{i , j} sti,j​ 表示在 [ i , i + 2 j − 1 ] [i , i +2^j - 1] [i,i+2j−1] 里的最大值

每次询问 l , r , v l , r , v l,r,v ，设 l g = log ⁡ 2 ( r − l + 1 ) lg = \log_2(r - l + 1) lg=log2​(r−l+1)

每次修改：
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) \newline 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)
最后由上往下更新：
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}) \newline 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" , &x0 , &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" , &n , &m , &typ);fu (i , 1 , n) scanf ("%lld" , &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 << "\n";// 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;
}