容易想到将询问离线下来，按 \(v\) 从大到小排序，这样后面的修改一定不会对前面的修改造成影响。然后可以用并查集把已修改过的点缩起来。注意到 \(m\) 会到 \(2\times 10^7\)，应该使用基数排序，复杂度为 \(\mathcal O(\frac{m \max{v_i}}{base} + m\alpha(n))\)。常数较大，卡卡常才能过。
（我天然小常数，比 xuany 小多了，才不需要卡呢???）
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
using ui=unsigned int;
ui x0,seed;
ui getnum(){x0=(x0<<3)^x0;x0=((x0>>5)+seed)^x0;return x0;}
ui n,m,typ;
ui a[100005],fa[100005];
struct offline{ui l,r,v;};
ui getfa(ui x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
ui cnt[65536];
void rsort(offline a[],offline b[],int byte){
memset(cnt,0,sizeof cnt);
for(ui i=m;i;--i)cnt[(a[i].v>>byte)&65535]++;
for(ui i=65534;~i;--i)cnt[i]+=cnt[i+1];
for(ui i=m;i;--i)b[cnt[(a[i].v>>byte)&65535]--]=a[i];
}
int main(){
freopen("train.in","r",stdin);
freopen("train.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n>>m>>typ;
for(ui i=1;i<=n;++i)std::cin>>a[i];
std::cin>>x0>>seed;
offline* tmp=new offline[m+1];
offline* q=new offline[m+1];
for(ui i=1;i<=m;++i){
ui l=getnum()%n+1,r=getnum()%n+1,v=getnum();
(l>r)&&(l^=r^=l^=r);
(typ==1)&&(l=1);
q[i]={l,r,v};
}
std::iota(fa+1,fa+1+n,1);
rsort(q,tmp,0),rsort(tmp,q,16);
delete[] tmp;
for(ui i=1;i<=m;++i){
ui fy=getfa(q[i].r),now;
for(ui j=q[i].l;j<=q[i].r;j=now+1){
a[j]=std::max(a[j],q[i].v);
now=getfa(j);
if(now!=fy)fa[now]=fy;
}
}
for(ui i=1;i<=n;++i)std::cout<<a[i]<<' ';
return 0;
}