F题题解: 备注: 本人在这之前没写过这种类型题目, 所以我的思路应该可以帮到不会的同学

这道题刚拿到手我是有点懵的, 因为我并没有读懂题目意思!!, 后来手算了一下样例才搞明白了这题目是什么意思!!!

就是算两个字符串里子序列为 red 数量之差

我一开始觉得这道题有点难以下手, 因为想算个数就得算r, e, d的出现的次数, 并且还得满足出现顺序恰好为r, e, d

数据范围为 ,这就得要想一个复杂度为 的算法了

这能想到一个叫偏序的东西, 我就想到了cdq分治的那个计算过程

这明显就可以用一样的套路给写出来! 因为这个递归回溯的过程中, 和 合并计算 时, 满足了偏序关系!!! 在题目中就是满足出现顺序恰好为r,e,d

上线段树!!!

维护六个信息, r, e, d在区间内出现的次数, re, ed在区间内出现的次数, 以及 red 在 区间内出现的次数(维护的任何东西都是为了最终算出子序列为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";
  }
}