题解 CF1198B 【Welfare State】

# 我会线段树!!! 显然我们只需要使用一个懒标记维护当前值即可。 后来的标记和旧标记求max就好了。 # 如果只有$1$个人不要忘记更新$1$号点哦。 ```cpp # include <bits/stdc++.h> using namespace std; const int N=2e5+10; int n; int val[N]; struct Segment_Tree{ int tag,ret; Segment_Tree() { tag=ret=-1;} }tr[N<<2]; # define ls (x<<1) # define rs (x<<1|1) # define lson x<<1,l,mid # define rson x<<1|1,mid+1,r # define mid (l+r>>1) void build(int x,int l,int r) { if (l==r) { tr[x].ret = val[l]; return; } build(lson); build(rson); } void down(int x) { if (tr[x].tag==-1) return; if (tr[ls].ret!=-1) tr[ls].ret=max(tr[ls].ret,tr[x].tag); if (tr[rs].ret!=-1) tr[rs].ret=max(tr[rs].ret,tr[x].tag); tr[ls].tag = (tr[ls].tag == -1)?tr[x].tag:max(tr[x].tag,tr[ls].tag); tr[rs].tag = (tr[rs].tag == -1)?tr[x].tag:max(tr[x].tag,tr[rs].tag); tr[x].tag=-1; } void update(int x,int l,int r,int pos,int val) { if (l==r) { tr[x].ret=val; return;} down(x); if (pos<=mid) update(lson,pos,val); else update(rson,pos,val); } int query(int x,int l,int r,int pos) { if (l==r) return tr[x].ret; down(x); if (pos<=mid) return query(lson,pos); else return query(rson,pos); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&val[i]); build(1,1,n); int q; scanf("%d",&q); while (q--) { int p,x,y; scanf("%d%d",&p,&x); if (p==1) scanf("%d",&y),update(1,1,n,x,y); else { tr[1].tag = (tr[1].tag==-1)?x:max(tr[1].tag,x); if (tr[1].ret != -1) tr[1].ret=max(tr[1].ret,tr[1].tag); } } for (int i=1;i<=n;i++) printf("%d ",query(1,1,n,i)); puts(""); return 0; } ```