Ai=1A_i = 1Ai=1 であるような 各 iii は、答えに j<ij < ij<i かつ Aj=2A_j = 2Aj=2 であるような jjj の個数と同じだけ寄与します。 よって、 two[i]=two[i] =two[i]= ( iii 項目までにある 222 の個数) とした数列を累積和の要領で構築することによって、 O(N)O(N)O(N) でこの問題を解くことができます。 また、この問題の答えは、 AAA から 333 を除いた数列 A′A'A′ の転倒数ですので、BITまたは分割統治により O(NlogN)O(N \log N)O(NlogN) で解けます。