D. Sum of Differences time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Let's consider a sequence of integers of length N . A "window" of length K moves along the sequence with a step of 1. In other words, initially, the window shows the first K numbers; on the next step, the window will contain K numbers starting from the second one, and so on until the end of the sequence. It is required to determine F(A) for each position of the window.
The function F(A) − sorts the given sequence of integers in non-decreasing order of elements. In other words, the sequence of integers in the given range will become Ai≤Ai+1 . Then it calculates the sum of the differences between adjacent elements and returns it. Formally, it returns ∑i=2i+k|Ai−Ai−1| .
Example 1 For example: when N=5,K=3,A=[5,2,3,1,4].
First K numbers are [5,2,3] . Then F([5,2,3]) will sort the given range it will be like [2,3,5] . Then sum of differences of the array [2,3,5] will be |3−2|+|5−3|=1+2=3 . Input The first line contains the integer T (1≤T≤100) − the number of test cases.
The first line of each test case contains two integers, N and K (1≤N≤150000,1≤K≤10000,K≤N) – the lengths of the sequence and the "window," respectively. The next line contains N numbers − the sequence itself (1≤Ai≤109) .
It is guaranteed that the sum of N over all test cases does not exceed 150000 .
Output For each testcase, the output should contain N−K+1 integers separated by spaces, representing the F(A) for each position of the "window".
I can't think of any other solution other than brute force and treeset,treemap(which is not built into the collections library), which of course will get stuck.
There is linear algorithm for finding smallest (and largest) value in each segment of constant size: https://usaco.guide/gold/sliding-window?lang=cpp