Python:

We have continous temperature generated and need to find sum of median for K last terms for given numbers.

The array of temperature can be generated with help of pseudocode,

t0 = seed
tk+1 = (tk * mul + add) mod 65536

So given, seed, mul, add factor we can generate temperature for next set where for given K we need to find
median and return the sum of median for all K windows.

I have tried with generating number and keeping them in deque but as median needed sorted order used binary sort on separate list and whenever I got the length of list is equal to K i am calculating median by lst[(k-1)//2] and adding to result. This does the job in time complexity of O(N*k).

def medians(seed, mul, add, n, k):
de = deque([seed])
lst = [seed]
res = 0
for i in range(1, n):
num = (de[-1] * mul + add ) % 65536
lst.insert(bisect_right(lst, num), num). # binary search for checking insertion position.
de.append(num)

if len(lst) == k :
res += lst[(k-1)//2]
lst.remove(de.popleft()). # This remove is causing time complexity to go O(N*k)
return res



I want to know if there is more efficient way than this? there is leetcode problem on sliding windows which does the same with help of heapq.
https://leetcode.com/problems/sliding-window-median/solutions/262689/python-small-large-heaps/?q=python&orderBy=most_relevant
Can this be implemented in O(nlogn)?