题解 P6273 【[eJOI2017]魔法】

· · 题解

【P6273】 [eJOI2017]魔法

Solution

写了个看起来不会被卡的暴力交上去过了，然后看看官方题解发现这居然就是正解……

首先考虑子任务三，字符集大小只有 2 的情况，不妨设字符集为 \{\texttt a, \texttt b\}，不失一般性。

考虑枚举右端点，对于一个右端点 r，一个合法的左端点 l 应该满足 l 到 r 的 \texttt a 的个数等于 \texttt b 的个数。我们对 a 和 b 的个数分别求前缀和，那么即为 sa_r - sa_{l - 1} = sb_r - sb_{l - 1}，其中 sa 代表 \texttt a 的前缀和，sb 同理。

对上式移项得到 sa_r - sb_r = sa_{l - 1}- sb_{l - 1}。换句话说，对于一个合法的区间，l, r 两个位置的 \texttt a, \texttt b 前缀和的差值一定相同。由于上述推导是可逆的，所以其逆命题也成立。因此这是一个充要条件。

于是从左到右枚举 r，用一个桶维护 sa_i - sb_i 的值的个数即可通过该子任务，时间复杂度 O(n)。

对于子任务四，发现字符集扩大到了 52，但是注意到对于所有的字符 \texttt x，都可以用与子任务三相同的证明方式证明 sx_r - sa_r = sx_{l - 1}- sa_{l - 1} 成立且必要。因此对于每个字符，维护它的前缀和减去 \texttt a 的前缀即可。考虑查询合法左端点数，可以在右端点扫过的时候将这 k 个差值作为一个元素插入到 std::map 中，查询时直接查询对应元素的个数即可。时间复杂度 O(n k \log n )。看起来很大实则根本跑不满，可以通过本题。

当然，如果希望理性愉悦的话，可以用 hash 代替 std::map，再用线段树维护对前缀和差值的区间加，即可将复杂度降至 O(n \log k)。

另外说句闲话，std::multiset.count 的复杂度竟然是 O(\log size + \text{返回值大小})……

Code

const int maxn = 100005;
const int maxk = 52;

void Init();
void Calc();

int main() {
  freopen("1.in", "r", stdin);
  Init();
  Calc();
  return 0;
}

int n, t;
char s[maxn];

void Init() {
  static char tmp[maxn];
  qr(n);
  qrs(s + 1);
  for (int i = 1; i <= n; ++i) tmp[i] = s[i];
  std::sort(tmp + 1, tmp + 1 + n);
  t = std::unique(tmp + 1, tmp + 1 + n) - tmp - 1;
  for (int i = 1; i <= n; ++i) s[i] = std::lower_bound(tmp + 1, tmp + 1 + t, s[i]) - tmp - 1;
}

struct Dat {
  int d[maxk];

  bool operator<(const Dat &o) const {
    for (int i = 0; i < t; ++i) if (d[i] != o.d[i]) {
      return d[i] < o.d[i];
    }
    return false;
  }
};
Dat dat[maxn];

struct Cmp {
  inline bool operator()(const int x, const int y) const {
    return dat[x] < dat[y];
  }
};

std::map<int, int, Cmp> mp;

void Calc() {
  ll ans = 0;
  mp[0] = 1;
  for (int i = 1, di = i - 1; i <= n; di = i++) {
    for (int j = 0; j < t; ++j) {
      dat[i].d[j] = dat[di].d[j];
    }
    if (s[i]) {
      ++dat[i].d[s[i]];
    } else {
      for (int j = 1; j < t; ++j) --dat[i].d[j];
    }
    int u = mp[i];
    ans += u;
    mp[i] = u + 1;
  }
  qw(ans % 1000000007, '\n');
}