题解 | 研究red子序列的红

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int MAXN = 2e5 + 5;

#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)

struct SegTree {
  struct Seg {
    int l, r;
    int rcnt, ecnt, dcnt, recnt, edcnt, redcnt;
  } seg[MAXN << 2];

  void push_up(int p) {
    seg[p].rcnt = seg[ls(p)].rcnt + seg[rs(p)].rcnt;
    seg[p].ecnt = seg[ls(p)].ecnt + seg[rs(p)].ecnt;
    seg[p].dcnt = seg[ls(p)].dcnt + seg[rs(p)].dcnt;

    seg[p].recnt =
        seg[ls(p)].recnt + seg[rs(p)].recnt + seg[ls(p)].rcnt * seg[rs(p)].ecnt;
    seg[p].edcnt =
        seg[ls(p)].edcnt + seg[rs(p)].edcnt + seg[ls(p)].ecnt * seg[rs(p)].dcnt;
    seg[p].redcnt = seg[ls(p)].redcnt + seg[rs(p)].redcnt +
                    seg[ls(p)].recnt * seg[rs(p)].dcnt +
                    seg[ls(p)].rcnt * seg[rs(p)].edcnt;
  }

  void build(int l, int r, const string &s, int p) {
    seg[p].l = l, seg[p].r = r;
    if (l == r) {
      seg[p].rcnt = seg[p].ecnt = seg[p].dcnt = 0;
      if (s[l] == 'r')
        seg[p].rcnt++;
      else if (s[l] == 'e')
        seg[p].ecnt++;
      else if (s[l] == 'd')
        seg[p].dcnt++;
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, s, ls(p));
    build(mid + 1, r, s, rs(p));
    push_up(p);
  }

  void update(int pos, char c, int p) {
    if (seg[p].l == seg[p].r && seg[p].l == pos) {
      seg[p].rcnt = seg[p].ecnt = seg[p].dcnt = 0;
      if (c == 'r')
        seg[p].rcnt = 1;
      else if (c == 'e')
        seg[p].ecnt = 1;
      else if (c == 'd')
        seg[p].dcnt = 1;
      return;
    }
    int mid = (seg[p].l + seg[p].r) >> 1;
    if (pos <= mid)
      update(pos, c, ls(p));
    else
      update(pos, c, rs(p));
    push_up(p);
  }
} t1, t2;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;

  string s, t;
  cin >> s >> t;
  s = " " + s, t = " " + t;

  t1.build(1, n, s, 1);
  t2.build(1, n, t, 1);

  while (q--) {
    int x;
    cin >> x;
    swap(s[x], t[x]);
    t1.update(x, s[x], 1);
    t2.update(x, t[x], 1);
    cout << t1.seg[1].redcnt - t2.seg[1].redcnt << "\n";
  }
}