Codeforces Round 576 (Div. 1) - B. Welfare State

博主： Solost
发布时间：2023 年 05 月 17 日
209 次浏览
暂无评论
1433字数
分类：题目题解

## 题目链接

[链接](https://codeforces.com/problemset/problem/1198/B)

## 题目大意

给你一个长度为n的数列，有两个操作，1操作把第c个元素改成x，2操作把数列所有小于x的数改成x

## 题解

有两种写法。

### 第一种

简单版本，每个元素只有两种情况，如果只有2情况，那他的值的大小就是本身大小和2操作最大改的数两者之间的最大值，因为比他小的都改不了它。如果有1操作，那让的值的大小就是最后一次1操作和最后一次1操作以后的最大2操作的大的那个。

```cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

int n, m;
int a[N], s[N];
vector<pii> q[N];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if(op == 1){
            int c, x;
            cin >> c >> x;
            q[c].push_back({i, x});
        }
        else{
            cin >> s[i];
        }
    }
    for(int i = m - 1; i >= 1; i--){
        s[i] = max(s[i], s[i + 1]);
    }
    for(int i = 1; i <= n; i++){
        if(q[i].empty()){
            cout << max(a[i], s[1]) << " ";
        }
        else{
            auto &t = q[i].back();
            cout << max(t.y, s[t.x]) << " ";
        }
    }
    cout << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

### 第二种

选择线段树写法，懒标记维护最小值，如果一个数都小于这段数的最小值，那它就没有必要往下传递

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

struct node {
    int l, r, val, lazy;
} tr[4 * N];
int a[N];

void pushup(int u)
{
    tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}

void pushdown(int u)
{
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    if (root.lazy) {
        l.val = max(l.val, root.lazy);
        r.val = max(r.val, root.lazy);
        l.lazy = max(l.lazy, root.lazy);
        r.lazy = max(r.lazy, root.lazy);
        root.lazy = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r) {
        tr[u] = { l, r, a[l], 0 };
    } else {
        tr[u] = { l, r };
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int val)
{
    tr[u].val = max(tr[u].val, val);
    tr[u].lazy = max(tr[u].lazy, val);
}

void modify(int u, int l, int r, int val)
{
    if (tr[u].l == tr[u].r) {//只有等于这个元素本身的时候返回
        tr[u].val = val;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        modify(u << 1, l, r, val);//注意边界l,r不变
    if (r > mid)
        modify(u << 1 | 1, l, r, val);
    pushup(u);
}

int query(int u, int l, int r)
{
    if (tr[u].l == tr[u].r) {//只有等于这个元素本身的时候返回
        return tr[u].val;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        return query(u << 1, l, r);//注意边界l,r不变
    if (r > mid)
        return query(u << 1 | 1, l, r);
}

void solve()
{
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int c, x;
            cin >> c >> x;
            modify(1, c, c, x);
        } else {
            int x;
            cin >> x;
            modify(1, x);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << query(1, i, i) << " ";
    }
    cout << endl;
}
int main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 05 月 17 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Codeforces Round 576 (Div. 1) - B. Welfare State

Solost • 2023 年 05 月 17 日

## 题目链接

[链接](https://codeforces.com/problemset/problem/1198/B)

## 题目大意

给你一个长度为n的数列，有两个操作，1操作把第c个元素改成x，2操作把数列所有小于x的数改成x

## 题解

有两种写法。

### 第一种

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

int n, m;
int a[N], s[N];
vector<pii> q[N];

### 第二种

选择线段树写法，懒标记维护最小值，如果一个数都小于这段数的最小值，那它就没有必要往下传递

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

struct node {
    int l, r, val, lazy;
} tr[4 * N];
int a[N];

void pushup(int u)
{
    tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}

void modify(int u, int val)
{
    tr[u].val = max(tr[u].val, val);
    tr[u].lazy = max(tr[u].lazy, val);
}

Codeforces Round 576 (Div. 1) - B. Welfare State

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛) -F-坐火车

树状数组

动态规划

Codeforces Round 712 (Div. 1) - B. 3-Coloring

2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers

AtCoder Beginner Contest 291 - E - Find Permutation

AtCoder Beginner Contest 290 - D - Marking

AcWing - 3485. 最大异或和

Codeforces Round 576 (Div. 1) - B. Welfare State

线性筛

Codeforces Round 576 (Div. 1) - B. Welfare State

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Codeforces Round 576 (Div. 1) - B. Welfare State

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款