线段树维护单调栈

例题：给定一个排列 a，每个数有权值 f[i]，维护一个单调递减栈的 f 之和，支持动态 swap 两个元素。

原理：

image-20241030210621422

image-20241030210700541

“push_up 的时候只更新右区间的 res，而不更新父亲的 res” 是最核心的思想！！！

constexpr int inf = 1e9;
template<class Info>
struct SegmentTree {
  vector<Info> info;
  int n;
  SegmentTree() : n(0) { }
  SegmentTree(int n_) {
    n = n_;
    info.assign(4 << __lg(n), Info());
  }
  Z query(int p, int l, int r, int mi) {
    if (info[p].mi > mi) return {};
    if (l == r) {
      return info[p].val;
    }
    int mid = l + r >> 1;
    if (info[p << 1].mi < mi) {
      return query(p << 1, l, mid, mi) + info[p << 1 | 1].res;
    } else {
      return query(p << 1 | 1, mid + 1, r, mi);
    }
  }
  void push_up(int p, int l, int r) {
    int mid = l + r >> 1;
    info[p].mi = min(info[p << 1].mi, info[p << 1 | 1].mi);
    info[p << 1 | 1].res = query(p << 1 | 1, mid + 1, r, info[p << 1].mi);
  }
  void modify(int p, int l, int r, int x, const Info &v) {
    if (l == r) {
      info[p] = v;
      return;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
      modify(p << 1, l, mid, x, v);
    } else {
      modify(p << 1 | 1, mid + 1, r, x, v);
    }
    push_up(p, l, r);
  }
  void modify(int x, const Info &v) {
    modify(1, 1, n, x, v);
  }
  Z Getans() {
    return query(1, 1, n, inf);
  }
};


struct Info {
  int mi = inf;
  Z res = 0;
  Z val = 0;
    // 这里非常重要！res 是考虑当前节点的左边兄弟的 min 时的答案，val 是每个叶子的原始 f 值，必须记录每个叶子原始的 f 值，才能在其再次出现在单调栈中的时候被统计上！
};


void solve() {
  int n, q;
  cin >> n >> q;
  vector<Z> f(n + 1);
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1] * i + i;
  }
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  Z tot = 0;
  for (int i = 1; i <= n; i++) {
    tot += f[i];
  }
  SegmentTree<Info> seg(n);
  for (int i = 1; i <= n; i++) {
    seg.modify(i, {a[i], a[i], f[i], f[i]});
  }
  cout << tot - seg.Getans() + n << "\n";
  while (q--) {
    int x, y;
    cin >> x >> y;
    swap(a[x], a[y]);
    seg.modify(x, {a[x], a[x], f[x], f[x]});
    seg.modify(y, {a[y], a[y], f[y], f[y]});
    cout << tot - seg.Getans() + n << "\n";
  }
}