DNA Evolution

题目描述

Everyone knows that DNA strands consist of nucleotides. There are four types of nucleotides: “A”, “T”, “G”, “C”. A DNA strand is a sequence of nucleotides. Scientists decided to track evolution of a rare species, which DNA strand was string $s$ initially.

Evolution of the species is described as a sequence of changes in the DNA. Every change is a change of some nucleotide, for example, the following change can happen in DNA strand “AAGC”: the second nucleotide can change to “T” so that the resulting DNA strand is “ATGC”.

Scientists know that some segments of the DNA strand can be affected by some unknown infections. They can represent an infection as a sequence of nucleotides. Scientists are interested if there are any changes caused by some infections. Thus they sometimes want to know the value of impact of some infection to some segment of the DNA. This value is computed as follows:

• Let the infection be represented as a string $e$, and let scientists be interested in DNA strand segment starting from position $l$ to position $r$, inclusive.
• Prefix of the string $eee$… (i.e. the string that consists of infinitely many repeats of string $e$) is written under the string $s$ from position $l$ to position $r$, inclusive.
• The value of impact is the number of positions where letter of string $s$ coincided with the letter written under it.

Being a developer, Innokenty is interested in bioinformatics also, so the scientists asked him for help. Innokenty is busy preparing VK Cup, so he decided to delegate the problem to the competitors. Help the scientists!

题意概述

给定一个只包含 ATGC 四种字符的字符串$s$。有两种操作：① 修改$s$某一位的字符；② 求以字符串$e$为循环节的无限长循环串与$s$中$[l, r]$这个区间的字符串有几个对应位置的字符相等。操作有$q$次。

数据范围：$1 \le |s|, q \le 10^5, \ 1 \le |e| \le 10$。

算法分析

由于$e$的长度最多是$10$，因此可以考虑在模$|e|$意义下的字符数。令$f_{i, j, k}$表示在模$i$意义下，模$i$余$j$的字符$k$个数的前缀和。这可以用树状数组维护。修改和查询时只需在对应的树状数组上进行操作。

代码

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
struct binary_indexed_tree {
  int n;
  vector<int> a;
  void init(int t) { n = t + 10, a.clear(), a.resize(n); }
  void add(int p, int t) { for (int i = p; i < n; i += i & -i) a[i] += t; }
  int sum(int p) {
    int ret = 0; if (p <= 0) return 0;
    for (int i = p; i; i -= i & -i) ret += a[i];
    return ret;
  }
} tree[11][10][4];
int get_type(char c) {
  if (c == 'A') return 0;
  else if (c == 'T') return 1;
  else if (c == 'G') return 2;
  else if (c == 'C') return 3;
  return -1;
}
int n, c, l, r, len, oper, ans;
string s, t;
int main()
{
  cin >> s; len = s.length();
  for (int i = 0; i <= 10; ++i)
    for (int j = 0; j < 10; ++j)
      for (int k = 0; k < 4; ++k)
        tree[i][j][k].init(len);
  for (int i = 0; i < len; ++i)
    for (int j = 1; j <= 10; ++j)
      tree[j][(i + 1) % j][get_type(s[i])].add(i + 1, 1);
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &oper);
    if (oper == 1) {
      scanf("%d", &c); cin >> t;
      for (int i = 1; i <= 10; ++i) {
        tree[i][c % i][get_type(s[c - 1])].add(c, -1);
        tree[i][c % i][get_type(t[0])].add(c, 1);
      }
      s[c - 1] = t[0];
    } else {
      scanf("%d%d", &l, &r); cin >> t;
      len = t.length(), ans = 0;
      for (int i = 0; i < len; ++i) {
        ans += tree[len][(l + i) % len][get_type(t[i])].sum(r) - tree[len][(l + i) % len][get_type(t[i])].sum(l - 1);
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}