No.3814 Typical AWC Query
レベル :
/ AI推定難易度 : 2300
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 2
作問者 :
dyktr_06
/ テスター :
tyawanmusi
sepa38
タグ : / 解いたユーザー数 2
作問者 :
sepa38
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。