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
|
#include<algorithm>
using namespace std;
const int N=500005;
int arr[N];
struct
{
int l,r,date,lazy;
}node[N<<2];
void pushUp(int i)
{
node[i].date=max(node[i<<1].date,node[i<<1|1].date);
}
void pushDown(int i)
{
if(node[i].lazy){
node[i<<1].lazy=max(node[i<<1].lazy,node[i].lazy);
node[i<<1|1].lazy=max(node[i<<1|1].lazy,node[i].lazy);
node[i<<1].date=max(node[i<<1].date,node[i].lazy);
node[i<<1|1].date=max(node[i<<1|1].date,node[i].lazy);
node[i].lazy=0;
}
}
void update(int i,int indexx,int val)
{
if(node[i].l==node[i].r)
{
node[i].date=val;
return ;
}
pushDown(i);
int mid=node[i].l+node[i].r>>1;
if(mid>=indexx){
update(i<<1,indexx,val);
}
else
{
update(i<<1|1,indexx,val);
}
pushUp(i);
}
int qu(int i,int l,int r)
{
if(node[i].l==l&&node[i].r==r) return node[i].date;
int mid=node[i].l+node[i].r>>1;
pushDown(i);
if(mid<l)
{
return qu(i<<1|1,l,r);
}
else return qu(i<<1,l,r);
}
void build_tree(int i,int l,int r)
{
node[i].l=l;
node[i].r=r;
node[i].lazy=0;
if(l==r)
{
node[i].date=arr[l];
return ;
}
int mid=l+r>>1;
build_tree(i<<1,l,mid);
build_tree(i<<1|1,mid+1,r);
pushUp(i);
}
void query(int i,int val)
{
node[i].date=max(node[i].date,val);
node[i].lazy=max(node[i].lazy,val);
pushDown(i);
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
int q;
build_tree(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int a,b,c;
scanf("%d",&a);
if(a==2)
{
scanf("%d",&b);
query(1,b);
}
else
{
scanf("%d%d",&b,&c);
update(1,b,c);
}
}
for(int i=1;i<=n;i++)
{
printf("%d ",qu(1,i,i));
}
cout<<endl;
}
|
近期评论