Codeforces Round #576 (Div. 1)B. Welfare State（思维/线段树）

我不是女神ヾ 2023-10-09 11:13 32阅读 0赞

### 题目：[Welfare State][] ###

#### 题意： ####

一个数组，两种操作，然后输出最终数组，两种操作是：  
**1 p x： 表示将第 p 个数改为x；  
2 x： 表示将所有小于 x 的数改成 x；**

#### 题解： ####

首先用线段树肯定可以做，就是 （区间更新 + 单点更新 ）。  
但这里我们先换个想法考虑这题：

1.  题目要求只输出最终序列，那么对于一个数来说，对他有影响的只有他的最后一次 1 操作之后的 2 操作，因为之前不管怎么操作进行 1 操作之后都会变成一个固定的数，之前的 1 操作与 2 操作就不影响它了，影响它的只有之后的 2 操作中的最大那个操作值。
2.  对于 2 操作，他只更改比它小的数，即如果之前的单点修改的值比他小的话，我们就相当于将该点改成 x。
3.  2 操作只对之前的单点操作有影响，对在他之后的操作无影响。那么我们可以把所有单点操作后，记录操作的序号，最后从头判断每个位置的最后一次1操作之后的2操作的最大值比不比他本身的值大，大就更改，不大就不更改。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int N = 2E5 + 10;
    int a[N], b[N], last[N];
    
    int main() { 
    
        int n, q;
        scanf("%d", &n);
        for ( int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);
        scanf("%d", &q);
    
        for( int i = 1; i <= q; i ++ ) { 
    
            int t, p, x;
            scanf("%d", &t);
            if( t==1 ) { 
                scanf("%d%d", &p, &x);
                a[p] = x;
                last[p] = i; //存储最后一个对进行1操作的序号
            }
            else { 
                scanf("%d", &b[i]);
            }
        }
        for ( int i = q-1; i >= 0; i -- ) {  // 存储每个操作序号之后(包括本身)的最大2操作值
            b[i] = max(b[i], b[i+1]);
        }
        for ( int i = 1; i <= n; i ++ ) {  
            if ( i==1 ) printf("%d", max(a[i], b[last[i]]));
            else printf(" %d", max(a[i], b[last[i]]));
        }
        cout << endl;
        return 0;
    }

##### 线段树解法： #####

线段树进行操作，先记录每个节点的数据，用一个懒惰标记lazy进行单点修改和区间修改标记，区间修改的话，考虑到是整个区间内数据的修改，对于每次的区间修改操作先记录下来，记录最大给出值，最后进行标记传输，输出最后结果。  
线段树代码：

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 2e5 + 10;
    
    struct node { 
    	int l, r, val, lazy;
    }tree[N<<2];
    
    void push_up ( int rt ) { // 记录左右孩子的最小值
    
    	tree[rt].val = min(tree[rt<<1].val, tree[rt<<1|1].val);
    }
    
    void push_down ( int rt ) { 
    
    	if ( tree[rt].lazy ) {  // 如果当前节点要更改的值比当前区间的最小值还小，就不需要覆盖，否则覆盖
    		int lazy = tree[rt].lazy;
    		tree[rt<<1].lazy = max(tree[rt<<1].lazy, lazy); // 标记最大值
    		tree[rt<<1|1].lazy = max(tree[rt<<1|1].lazy, lazy);
    		tree[rt<<1].val = max(tree[rt<<1].val, lazy);
    		tree[rt<<1|1].val = max(tree[rt<<1|1].val, lazy);
    		tree[rt].lazy = 0;
    	}
    }
    
    void build ( int l, int r, int rt ) { 
    
    	tree[rt].l = l;
    	tree[rt].r = r;
    	tree[rt].lazy = 0;
    	if (l == r) { 
    		scanf("%d", &tree[rt].val);
    		return ;
    	}
    	int m = (l + r) >> 1;
    	build(l, m, rt<<1);
    	build(m + 1, r, rt<<1|1);
    	push_up(rt);
    }
    
    void update1 ( int l, int r, int val, int rt ) {  // 单点修改
    
    	if (tree[rt].l == tree[rt].r) { 
    		tree[rt].val = val;
    		return ;
    	}
    	push_down(rt);
    	int m = (tree[rt].l + tree[rt].r) >> 1;
    	if (l <= m) update1(l, r, val, rt<<1);
    	if (m < r) update1(l, r, val, rt<<1|1);
    	push_up(rt);
    }
    
    void update2 ( int val, int rt ) {  // 区间修改
    
    	tree[rt].val = max(tree[rt].val, val);
    	tree[rt].lazy = max(tree[rt].lazy, val);
    	return ;
    }
    
    int query ( int l, int r, int rt ) {  // 查询
    
    	if (tree[rt].l == tree[rt].r) { 
    		return tree[rt].val;
    	}
    	push_down(rt);
    	int m = (tree[rt].l + tree[rt].r) >> 1;
    	if (l <= m) return query(l, r, rt<<1);
    	if (m < r) return query(l, r, rt<<1|1);
    }
    
    int main() { 
    
    	int n, q;
    	scanf("%d", &n);
    	build(1, n, 1);
    	scanf("%d", &q);
    	while ( q-- ) { 
    
            int t, p, x;
    		scanf("%d", &t);
    		if (t == 1) { 
    			scanf("%d%d", &p, &x);
    			update1(p, p, x, 1);
    		} else { 
    			scanf("%d", &x);
    			update2(x, 1);
    		}
    	}
    	for ( int i = 1; i <= n; i ++ ) { 
    		if(i==1) printf("%d", query(i, i, 1));
    		else printf(" %d", query(i, i, 1));
    	}
    	printf("\n");
    	return 0;
    }

[Welfare State]: http://codeforces.com/contest/1198/problem/B