檢查是否有(m+1)/2個區(qū)間的中位數(shù)>=x，其中m為區(qū)間個數(shù)?

設(shè)b為 b[i]=a[i]>=x?1:-1這樣的一個數(shù)組，則有如下的等價check?

b數(shù)組區(qū)間和>=0的區(qū)間個數(shù) >= (m+1)/2.?

下面需要用權(quán)值樹狀數(shù)組，用前綴和的值作為樹狀數(shù)組的索引.

當(dāng)掃到j(luò)的時候，在樹狀數(shù)組上查詢pre[j]，得到有多少個pre[i]是<=pre[j]的，而因為是從左向右掃，所以i<j，即[i+1,j]是滿足區(qū)間和>=0的區(qū)間。?

所以這樣掃一遍，就用n\log?n的復(fù)雜度求得了上述區(qū)間個數(shù)