去年新星赛的题 赛时一直想着线段树 但连线段树的一些基本操作都没有搞懂 还是先不用线段树写了吧(虽然赛后提交正确是用线段树的)
两种操作

  1. 将小于k的所有能力值提升至k
  2. 将某一项能力值设定为b

每次遍历修改时间复杂度为n² 肯定不现实 此时转换思路 没必要每次都去修改 只需要按照操作先后顺序 记录此时的操作 所以在询问时肯定是使用for从1到q循环
对于操作1 只需要多开一个数组d 记录这个i下的设定的值
对于操作2 需要记录修改的值以及操作的时间 那如何进行呢？ 多开一维就好了 所以一开始就用二维数组记录初始能力值 在操作2时对值进行修改 并且记录操作时间
然后从尾到头 开数组f记录d的最大值 此处从末尾遍历 确保在当前时间下的d数组的最大值
最后遍历整个数组 对比在这个时间的能力值和原先的能力值 输出较大值就结束了
PS:感觉有点混乱 其实就是根据操作时间记录了这个能力最后能到达的最大值 和原始值(或者修改值)之间的大小关系

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 2e5 + 5;
ll tag[MAX][2], a[MAX];
ll d[MAX], f[MAX];

int n, m;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    tag[i][1] = a[i];
  }

  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int op;
    cin >> op;
    if (op == 1) {
      cin >> d[i];
    }
    else {
      int x, y;
      cin >> x >> y;
      tag[x][0] = i, tag[x][1] = y;
    }
  }

  f[m] = d[m];
  for (int i = m - 1; i >= 0; --i)
    f[i] = max(f[i + 1], d[i]);

  for (int i = 1; i <= n; ++i) {
    cout << max(tag[i][1], f[tag[i][0]]) << " ";
  }
}

把我第一次AC的线段树代码附上吧

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
ll a[N], tag[N << 2], t[N << 2];
int n, q;

void pushup(int o){
  t[o] = min(t[o << 1], t[o << 1 | 1]);
}

void build(int s = 1, int e = n, int o = 1){
  if(s == e){
    t[o] = a[s];
    return;
  }
  int mid = (s + e) >> 1;
  build(s, mid, o << 1);
  build(mid + 1, e, o << 1 | 1);
  pushup(o);
}

void pushdown(int o){
  if(t[o << 1] < tag[o] && tag[o] > tag[o << 1]){
    t[o << 1] = tag[o];
    tag[o << 1] = tag[o];
  }
  if(t[o << 1 | 1] < tag[o] && tag[o] > tag[o << 1 | 1]){
    t[o << 1 | 1] = tag[o];
    tag[o << 1 | 1] = tag[o];
  }
  tag[o] = 0;
}

void c_tag(ll x){
  tag[1] = max(x, tag[1]);
}

void change(int s, int e, int o, int pos, int val){
  if(s > pos || pos > e)return;
  if(s == pos && pos == e){
    t[o] = val;
    tag[o] = 0;
    return;
  }
  pushdown(o);
  int mid = (s + e) >> 1;
  change(s, mid, o << 1, pos, val);
  change(mid + 1, e, o << 1 | 1, pos, val);
  pushup(o);
}

//单点查询
ll quire(int pos, int s = 1, int e = n, int o = 1){
  if(s > pos || pos > e)return 0;
  if(s == e)return t[o];
  pushdown(o);
  int mid = (s + e) >> 1;
  return quire(pos, s, mid, o << 1) + quire(pos, mid + 1, e, o << 1 | 1);
}

int main (){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1;i <= n; ++ i)cin >> a[i];
  build();
  cin >> q;
  while(q--){
    int op;cin >> op;
    if(op == 1){
      ll x;cin >> x;
      c_tag(x);
    }else{
      int pos, val;cin >> pos >> val;
      change(1, n, 1, pos, val);
    }
  }
  for(int i = 1;i <= n; ++ i){
    cout << quire(i) << ' ';
  }
  return 0;
}