這邊提供本人的作法給你參考: (強烈不建議直接觀看, 真的想不到再反白來看吧...)
首先對N的人的孤單值w[i]做後綴s[i], (O(N)建表後可以O(1)查詢任意後綴和)
接著使用爬行法對於所有左界可以找到距離剛好超過K的區間, (爬行法整體O(N), 故對於所有左界為均攤O(1) )
對於每個找到的區間 i~j 可以發現對於 i 而言 j 以後(包含)的距離都超過K,
所以累加 w[i]*w[j] + w[i]*w[j+1] + ... + w[i]*w[N] ,
提出 w[i] 後就變成 w[i]*(w[j]+w[j+1]+...+w[N]) , (後項為後綴和)
即 w[i]*s[j] 故對於每個區間都能O(1)做計算,
最後累加就是答案了~
時間複雜度: 建後綴和+爬行法*計算花費 = O(N)+O(N)*O(1) = O(N)
額外空間複雜度: 後綴和 = O(N)
以上希望有幫助到你~ OwO
這邊提供本人的作法給你參考: (強烈不建議直接觀看, 真的想不到再反白來看吧...)
感謝提供想法
首先對N的人的孤單值w[i]做後綴s[i], (O(N)建表後可以O(1)查詢任意後綴和)
接著使用爬行法對於所有左界可以找到距離剛好超過K的區間, (爬行法整體O(N), 故對於所有左界為均攤O(1) )
對於每個找到的區間 i~j 可以發現對於 i 而言 j 以後(包含)的距離都超過K,
所以累加 w[i]*w[j] + w[i]*w[j+1] + ... + w[i]*w[N] ,
提出 w[i] 後就變成 w[i]*(w[j]+w[j+1]+...+w[N]) , (後項為後綴和)
即 w[i]*s[j] 故對於每個區間都能O(1)做計算,
最後累加就是答案了~
時間複雜度: 建後綴和+爬行法*計算花費 = O(N)+O(N)*O(1) = O(N)
額外空間複雜度: 後綴和 = O(N)
以上希望有幫助到你~ OwO