尺取法などでも解けるが、以下、優先度付きキューを使った解法。
連続した整数列の部分列なので、区間のように考えてよく、左右端の数字 $L,R$ を決めれば数列は一意に決まる。
そこで、$R$ を固定して $R$ ごとに考える。
その時の $L$ の取り得る値は?というと、
R i\ 1 2 3 4 5 6 7 8 9 10 11 12 ... 1 A B 2 A B 3 A B
なので、上例の場合は、$i=1,3$ は $A$(それぞれ $4,3$)、$i=2$ は $B$($5$)を取ってきて、 その中の最小値である $3$ が、$R=7$ の時に $L$ として設定できる最大値となる。
今回は、数列の長さ毎に個数を数える必要があるので、 imos法などを使って、最小の長さ $5$~最大の長さ $7$ に一律 $1$ を加算してやればよい。
では、$R=1,2,...,M$ と走査していく中で、その時々の $A_i$ または $B_i$ の最小値を求めるにはどうしたらよいか。
優先度付きキューを使えばよい。
$R$ が $B_i$ を超えたら $A_i$ は無効になるので、 「各 $i$ につき、今、何の値が有効か」を管理する配列 $S$ も用意しておく。
一番最後に $ans$ の累積和を取ったら、それが答え。
$2N$ 個の要素が1回ずつ優先度付きキューに出したり入れたりされるので、
優先度付きキューを使う部分の計算量は $O(N \log N)$。
imos法の部分は $O(M)$ で、まとめて $O(M + N \log N)$ となる。
全てを列挙するのは難しいが、1つ見つけるだけなら高速な方法があるということ。
そして $T$ のサイズが小さいことを利用するのだろう、ということが読み取れる。
グループをそれぞれ $A,B$ とおくと、ある $A$ 側の2頂点 $u,v$ から繋がる $B$ 側の頂点に、 同じペア $(w,x)$ があれば、$u-w-v-x-u$ というサイクルができるので、これを見つければよい。
$A$ 側の1頂点 $u$ を固定し、そこから繋がった $B$ 側の頂点につき、全ペアを回す。
あるペアにつき、そこから繋がる $A$ 側頂点の中に、$u$ 以外の共通項があればよい。
一見、$O(ST^2)$ となりそうだが、実際は1つ見つかったら打ち切ってよい。
$u$ から繋がった $B$ 側頂点のペアに1つも $u$ 以外の共通項がない、ということが 様々な $u$ に対して成り立つケースは結構作るのが難しく、間に合うんじゃないかなあ(希望)
と思ったが、1ケースTLEが取れなかった。
後から考えると、以下のようなケースで計算量がやばくなることがわかる。
このようなケースでイメージしやすいのが、平面上に「互いに平行でない $T$ 本の直線があり、交点に駅がある」場合である。
交点は $\dfrac{T(T-1)}{2}$ 個、実際はこれは $S$ を超えるので、それが上限となる。
路線は他のほぼ全ての路線と交わるので、2つの路線に駅は $T-1$ 個ずつあり、そこから交点駅の他に共通する1駅があるかを調べるのは工夫しても $O(T)$ かかる。
これが $S$ 個の全ての駅で行われた場合、全体で $O(ST)$ となってしまう。
(まぁ、時間ギリギリまで調べて見つからなかったら-1を出力したら通ったけど、本質じゃないね)
鳩の巣原理を用いる。
$A$ 側の頂点を $u$ とし、$u$ から繋がった全ての “$B$ 側頂点のペア $(w,x)$” に対して 「$(w,x)$ の両方に繋がってるのは $u$ でっせ」という情報を記録していく。
その時、既に $(w,x)$ の両方に繋がった他の頂点 $v$ が記録されていれば、$u,v,w,x$ が答えとなる。
新規で記録されるのはたかだか $B$ 側頂点のペア数なので、
$\dfrac{T(T-1)}{2}$ 回だめでへとへとになっても、 $\dfrac{T(T-1)}{2}+1$ 回目は何か変わるかもしれない。
もとい、必ず見つかる。
よって、グラフの入力を合わせても $O(S+M+T^2)$ で見つけるか、存在しないことを判定できる。