题解归档 - cf1198B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1198B
• 本地来源：problems/cf1198B/idea.md
• 题目链接：https://codeforces.com/contest/1198/problem/B
• 原始标题：CF1198B Welfare State

思路

CF1198B Welfare State

题意

n 个市民初始余额 a[i]。按时间顺序处理 q 个事件：

• 1 p x：第 p 人余额变为 x（收据）
• 2 x：所有余额严格小于 x 的人变为 x（扶贫，无收据）

求最终余额。

做法

倒序扫事件，维护后缀最大扶贫值 suf（当前事件之后所有 type2 的 x 的最大值）。

• type2：更新 suf = max(suf, x)
• type1 p x（每人只处理最后一次收据，即倒序首次遇到）：ans[p] = max(x, suf)

从未收到收据的人：ans[i] = max(a[i], suf)，其中最终 suf 为全局 type2 最大值。

复杂度

O(n + q)。

验证

样例 1、2 与暴力模拟一致；对拍 500 组通过。

代码

来源：problems/cf1198B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:16:30
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll a[maxn],ans[maxn],suf;
ll tp[maxn],p[maxn],x[maxn];
bool pd[maxn];
int main(){
    ll n,q,i,j,k;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    cin>>q;
    for(i=1;i<=q;i++){
        cin>>tp[i];
        if(tp[i]==1) cin>>p[i]>>x[i];
        else cin>>x[i];
    }
    suf=0;
    for(i=q;i>=1;i--){
        if(tp[i]==2) suf=max(suf,x[i]);
        else if(!pd[p[i]]){
            pd[p[i]]=1;
            ans[p[i]]=max(x[i],suf);
        }
    }
    for(i=1;i<=n;i++){
        if(!pd[i]) ans[i]=max(a[i],suf);
        cout<<ans[i]<<(i==n?'\n':' ');
    }
    return 0;
}