2023NOIP A层联测30 A. 草莓列车
题目大意
给定一个序列 \(a\) ，有 \(m\) 次操作，将 \([l , r]\) 的每个 \(a_i\) 变为 \(max (a_i , v)\)
\(n \le 10 ^5 , m \le 10^7\)
思路
对于每个数，只用用它本身和每个涉及到它的查询里面的最大值比较就好了。
我们要找到一种操作，可以 \(O(1)\) 修改， \(O(n\log_2n)\) 查询。
考虑用 \(st\) 表，设 \(st_{i , j}\) 表示在 \([i , i +2^j - 1]\) 里的最大值
每次询问 \(l , r , v\) ，设 \(lg = \log_2(r - l + 1)\)
每次修改：
\[st_{l , lg} = \max (st_{l , lg} , v) \newline
st_{r - 2^{lg} + 1 , lg} = \max (st_{r - 2 ^{lg} + 1 , lg} , v)
\]
最后由上往下更新：
\[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})
\]
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;
}