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