問題一覧 > 通常問題

No.3814 Typical AWC Query

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 2
作問者 : dyktr_06 / テスター : tyawanmusi sepa38
お気に入りにしたユーザー ProblemId : 14069 / 自分の提出
問題文最終更新日: 2026-09-21 05:21:02
yukicoder contest 524 (順位表) の他の問題:

問題文

$N$ 頂点 $M$ 辺の単純無向グラフがあります。頂点には $1$ から $N$ まで、辺には $1$ から $M$ までの番号が付けられています。

各頂点には文字が一つ書かれています。頂点 $i$ に書かれている文字は $S_i$ です。

また、辺 $i$ は頂点 $U_i$ と頂点 $V_i$ を双方向に結んでいます。

$Q$ 個のクエリが与えられます。$i$ 番目のクエリでは、頂点 $v_i$ に書かれている文字を $x_i$ に変更してください。

各クエリを処理した直後に、以下の条件をすべて満たす整数の組 $(a,b,c)$ の個数を求めてください。

  • $1 \leq a,b,c \leq N$
  • $S_a=$ A
  • $S_b=$ W
  • $S_c=$ C
  • 頂点 $a$ と頂点 $b$ が辺で直接結ばれている。
  • 頂点 $b$ と頂点 $c$ が辺で直接結ばれている。

制約

  • $1 \leq N \leq 5 \times 10^5$
  • $1 \leq M \leq 5 \times 10^5$
  • $1 \leq U_i < V_i \leq N$
  • 与えられるグラフは単純無向グラフ
  • $S$ は英大文字からなる長さ $N$ の文字列
  • $1 \leq Q \leq 20000$
  • $1 \leq v_i \leq N$
  • $x_i$ は英大文字
  • $N, M, U_i, V_i, Q, v_i$ は整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$
$S$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$
$Q$
$v_1$ $x_1$
$v_2$ $x_2$
$\vdots$
$v_Q$ $x_Q$

出力

$Q$ 行出力してください。$i$ 行目には、$i$ 番目のクエリを処理した直後の答えを出力してください。

サンプル

サンプル1
入力
3 2
AWC
1 2
2 3
3
1 C
1 A
2 X
出力
0
1
0

二つ目のクエリを処理した直後は、$(a,b,c)=(1,2,3)$ のみが条件を満たします。

サンプル2
入力
8 9
AWCAXCWW
1 2
2 3
2 4
2 5
3 6
4 6
5 7
6 8
7 8
5
5 A
2 W
4 C
1 W
6 A
出力
3
3
4
2
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。