Some of the most powerful techniques are also the simplest yet identifying when and how to apply them effectively can be challenging. Sliding window is one such method. Sliding window helps solve problems involving sequences, subarrays, or continuous segments by efficiently tracking changes as the window moves forward.
While tackling the CSES Sliding window problems, I noticed that many seemingly complex tasks like tracking the sum of elements in a dynamic segment, finding a subarray's minimum or maximum, or counting distinct elements can be simplified and optimized with this technique. Initially, one might consider brute-force methods iterating over every possible subarray or recomputing values from scratch. However, the core idea behind sliding window is smartly updating the state of the window rather than recalculating everything each time.
In my experience, the primary challenge while solving these problems came down to accurately managing the data structures supporting the window, as well as handling tricky edge cases involving modular arithmetic or negative values. Choosing the right DS such as monotonic deques for minimum or maximum queries, frequency maps for counting distinct elements, or multisets for median calculations.
We generate the first k elements and store them in a array. Their sum becomes our first window sum, and we XOR that into the result. For each next element, we generate it using the formula, subtract the element that slides out of the window, and add the new one. So the window sum gets updated in O(1) time at each step.
To avoid shifting elements, we overwrite positions in the buffer using i % k. This lets us maintain a circular buffer of the last k values efficiently.
Instead of storing any part of the window, we track just two pointers: left (the value leaving the window) and right (the new value coming in). We update both using the same recurrence relation. The total window sum is updated like:
This avoids even the window[] array. To ensure values stay within bounds (especially with mod), we sometimes adjust right = (right + c) % c this handles negative values or overflows in edge cases. This approach is tighter on memory but needs careful handling of how we regenerate left.
Input
Step 1: Generate First (k = 5) Numbers
Initial Values:
Step 2: Slide the Window (from (i = 5) to (7))
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n, k;cin >> n >> k;
long long x, a, b, c;cin >> x >> a >> b >> c;
vector<long long> window(k);
window[0] = x;
for (int i = 1; i < k; ++i) {
window[i] = (a * window[i - 1] + b) % c;
}
long long sum = 0, res = 0;
for (int i = 0; i < k; ++i) sum += window[i];
res ^= sum;
long long prev = window[k - 1];
for (int i = k; i < n; ++i) {
long long curr = (a * prev + b) % c;
sum += curr - window[i % k];
res ^= sum;
window[i % k] = curr;
prev = curr;
}
cout << res << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k; cin >> n >> k;
int x, a, b, c; cin >> x >> a >> b >> c;
int right = 0, res = 0;
right = x;
int tot = x;
for (int i = 1; i < k; ++i)
{
right = (a * right + b) % c;
tot += right;
}
int left = x;
res = tot;
for (int i = k; i < n; ++i)
{
right = ((a * right + b) % c ) % c ;
right = (right + c) % c;
tot = (tot + right - left) ;
left = (left * a + b) % c;
res = res ^ tot;
}
cout << res << endl;
}
Monotonic Deque
As we move through the stream of values, we want a data structure that tells us the minimum value in the current window in constant time. For that, we use a deque where we maintain the elements in increasing order of value. When a new element comes in, we remove all elements from the back that are greater than or equal to it since they will never be the minimum in any future window.
We also store the index of each element in the deque, so that we can check whether the element at the front is outside the current window (i.e., i $$$-$$$ k). If it is, we pop it from the front. Once we’ve processed at least k elements, the minimum of the current window is at the front of the deque, and we XOR that into our answer.
Input
Generated Sequence Using Recurrence:
Final sequence:
Sliding Window, Deque State & XOR Result :
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
long long x, a, b, c;
cin >> x >> a >> b >> c;
deque<pair<int, int>> dq;
long long ans = 0;
for (int i = 0; i < n; ++i) {
int v = x;
while (!dq.empty() && dq.back().second >= v) dq.pop_back();
dq.emplace_back(i, v);
if (dq.front().first <= i - k) dq.pop_front();
if (i >= k - 1) ans ^= dq.front().second;
x = (a * x + b) % c;
}
cout << ans;
return 0;
}
For each index i (1-based), we define its mirror distance from both ends as min(i, n $$$-$$$ i + 1). Then, we take the minimum of that and a given k. If this minimum is odd, we XOR the current value into the answer.
This effectively builds a symmetric pattern around the center of the array. For example, positions near the beginning and end get the same treatment because min(i, n $$$-$$$ i + 1) is symmetric. And then applying the additional cap of k ensures the "influence" doesn’t extend beyond a window of size k.
Input
Sequence Generation
We use:
XOR Selection Logic :
Final XOR Calculation :
Step-by-step:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
long long x, a, b, c;
cin >> x >> a >> b >> c;
deque<pair<int, int>> dq;
long long res = 0;
for (int i = 1; i <= n; ++i) {
int v = x;
int fs = i, sc = n - i + 1;
int final = min({fs, sc, k});
if (final % 2 == 1 )res = res ^ x;
x = (a * x + b) % c;
}
cout << res;
return 0;
}
In the first approach, we treat the bitwise OR in a more granular way. Instead of re-OR-ing the full window on each slide, we maintain a bit count array that keeps track of how many times each individual bit (from 0 to 31) is present in the current window. Let’s say cnt[i] represents how many elements in the current window have the i-th bit set.
When a new number enters the window, we iterate through its set bits and increment the corresponding counts. Similarly, when an old number leaves, we decrement those counts. At any moment, we can reconstruct the window’s OR value by checking which bits have a non-zero count if cnt[i] > 0, then bit i contributes to the OR.
This method ensures that we don’t fully recompute the OR every time instead, we update it incrementally. But because we still scan all 32 bits per number (both when entering and leaving the window), the TC became O(n⋅32), and gets TLE.
The second and accepted approach borrows a trick from sliding window maximum problems using two stacks to simulate a queue. Each stack stores elements along with the cumulative OR of all elements beneath them. Let’s say we push value v onto the in stack; we also store agg = (in.back().second | v), so that we can always know the OR of everything in that stack up to this point.
When it’s time to remove the oldest element (i.e., simulate a pop from the front of the window), we transfer all elements from in to out (in reverse), recomputing the OR along the way. This reversal step is only done when out is empty, so each element is moved at most once.
To compute the OR of the current window, we simply take the top agg from both in and out stacks and OR them together. The key insight here is that OR is associative and idempotent meaning the order doesn’t matter and repeating a number doesn’t affect the final OR.
Overall, this approach gives us a total time complexity of O(n).
Input
Generated Sequence
Sliding Window OR with Selected Bit Indices (0 to 4)
We track updates to the last[] array for bit positions 0–4 and the curr OR value.
Final Result:
Input
Sequence Generation
We use:
Sequence: [ 3, 0, 1, 8, 2, 4, 7, 6 ]
Sliding Window OR using Two Stacks (pairs shown) :
Final XOR Result:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, x, a, b, c;
cin >> n >> k >> x >> a >> b >> c;
int *buf = new int[k];
int cnt[32] = {0};
int curr = 0, ans = 0, v = x, t, j;
buf[0] = v;
t = v;
while (t) {
j = __builtin_ctz(t);
cnt[j]++;
curr |= 1 << j;
t &= t - 1;
}
for (int i = 2; i <= k; ++i) {
v = int((1LL * a * v + b) % c);
buf[i - 1] = v;
t = v;
while (t) {
j = __builtin_ctz(t);
cnt[j]++;
curr |= 1 << j;
t &= t - 1;
}
}
ans = curr;
int pos = k - 1;
for (int i = k + 1; i <= n; ++i) {
v = int((1LL * a * v + b) % c);
pos++;
if (pos == k) pos = 0;
int out = buf[pos];
buf[pos] = v;
t = out;
while (t) {
j = __builtin_ctz(t);
if (--cnt[j] == 0) curr &= ~(1 << j);
t &= t - 1;
}
t = v;
while (t) {
j = __builtin_ctz(t);
if (cnt[j]++ == 0) curr |= 1 << j;
t &= t - 1;
}
ans ^= curr;
}
cout << ans;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, x, a, b, c;
cin >> n >> k >> x >> a >> b >> c;
vector<pair<int, int>> in, out;
in.reserve(k);
out.reserve(k);
int val = x;
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (i > 1) val = int((1LL * a * val + b) % c);
int agg_in = in.empty() ? val : (in.back().second | val);
in.emplace_back(val, agg_in);
if (i > k) {
if (out.empty()) {
while (!in.empty()) {
auto [v, _] = in.back();
in.pop_back();
int agg_out = out.empty() ? v : (out.back().second | v);
out.emplace_back(v, agg_out);
}
}
out.pop_back();
}
if (i >= k) {
int window_or = 0;
if (!in.empty()) window_or |= in.back().second;
if (!out.empty()) window_or |= out.back().second;
ans ^= window_or;
}
}
cout << ans;
return 0;
}
E. Sliding Window Distinct Values
The key idea is to maintain a count of how many times each number appears in the current window using a map. Alongside this, we maintain a set that contains only the elements with a non-zero frequency, effectively tracking the unique elements currently in the window.
As we move the window forward, we insert the new element into the window: we increment its frequency in the map and insert it into the set. If the window has grown larger than k, we remove the oldest element: we decrement its frequency in the map, and if the frequency becomes zero, we remove it from the set as it’s no longer part of the current window. Once the window has reached the desired size (i.e., once i >= k $$$-$$$ 1), the number of distinct elements in the current window is simply the size of the set, and we output it. This approach ensures that each element is processed only as it enters and leaves the window, making it efficient.
Overall, time complexity of O(nlogk) due to insert and erase operations on the set, and a space complexity of O(k).
Input
Sliding Window: map (frequency) and set (distinct)
Final Output:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define endl "\n"
#define sp " "
#define pb push_back
const int MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k; cin >> n >> k;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
map<int, int>mp;
set<int>st;
int res = 0;
for (int i = 0; i < n; ++i)
{
st.insert(v[i]);
mp[v[i]]++;
if (i >= k) {
if (--mp[v[i - k]] == 0)st.erase(v[i - k]);
}
if (i >= k - 1) {
cout << st.size() << " ";
}
}
}
In this problem, we are given an array of n integers and a window size k. For every window of size k, we are asked to find the mode, i.e., the most frequent number in that window. If multiple numbers share the highest frequency, we must return the smallest among them. To solve this efficiently, we use a combination of a frequency map and a set. The map freq stores the frequency count of each number in the current window. Simultaneously, we maintain a set of pairs where each pair is of the form (-count, value). The minus sign ensures that higher frequencies come first in the set, and in case of a tie, the set naturally keeps the smaller number first due to pair ordering. This way, the first element in the set always represents the mode of the current window.
When a value enters the window, add(v) increases its count in the frequency map, removes the old (count, value) pair from the set if it exists, and inserts the updated pair. When a value exits the window, remove(v) decreases its count, updates the set accordingly, or deletes the entry completely if its count drops to zero. The sliding window is initialized by processing the first k elements. Then, for each subsequent step, we remove the element going out and add the new incoming one, and the mode for that window is simply the second element of the first pair in the set.
T.C. : O(nlogk)
Input
Sliding Window with Frequency Map + Ordered Set
Final Output:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector<int>a(n);
for (int i = 0; i < n; i++)cin >> a[i];
unordered_map<int, int>freq;
set<pair<int, int>>st;
auto add = [&](int v) {
int c = freq[v];
if (c > 0)st.erase({ -c, v});
freq[v] = c + 1;
st.insert({ -(c + 1), v});
};
auto remove = [&](int v) {
int c = freq[v];
st.erase({ -c, v});
if (c == 1)freq.erase(v);
else {freq[v] = c - 1; st.insert({ -(c - 1), v});}
};
for (int i = 0; i < k; i++)add(a[i]);
vector<int>res; res.reserve(n - k + 1);
res.push_back(st.begin()->second);
for (int i = k; i < n; i++) {
remove(a[i - k]);
add(a[i]);
res.push_back(st.begin()->second);
}
for (int x : res)cout << x << " ";
cout << endl;
return 0;
}
we use a sliding window approach combined with a frequency array and a multiset. The frequency array cnt keeps track of how many times each number from 0 to k appears in the current window. The multiset miss contains all numbers from 0 to k that are currently missing (i.e., whose frequency is zero).
The key idea is that the minimum element of miss will always be the smallest number not present in the current window. When a new number enters the window (add), we update the count and remove it from miss if it was previously missing. When a number exits the window (rem), we decrement its count and re-insert it into miss if its frequency drops to zero. We initialize the first window by adding its elements, compute its mex, then slide the window one element at a time by removing the outgoing element and adding the incoming one. At each step, we simply output *miss.begin(), which gives the current mex in O(1) time.
T.C. : O(nlogk).
Input :
Tracking Counts and Missing Values :
Final Output:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector<int>a(n);
for (int&i : a)cin >> i;
vector<int> cnt(k + 1, 0);
multiset<int> miss;
for (int i = 0; i <= k; i++) miss.insert(i);
auto add = [&](int v) {
if (v <= k) {
if (cnt[v] == 0) miss.erase(miss.find(v));
++cnt[v];
}
};
auto rem = [&](int v) {
if (v <= k) {
--cnt[v];
if (cnt[v] == 0) miss.insert(v);
}
};
for (int i = 0; i < k; i++) add(a[i]);
vector<int> ans; ans.reserve(n - k + 1);
ans.push_back(*miss.begin());
for (int i = k; i < n; i++) {
rem(a[i - k]);
add(a[i]);
ans.push_back(*miss.begin());
}
for (size_t i = 0; i < ans.size(); ++i) {
cout << ans[i] << " ";
}
cout << '\n';
return 0;
}
Policy-Based Data Structures — GNU C++ Library Manual
This documentation is your authoritative source for understanding:
Tree-Based Containers with Order-Statistics
PBDS offers powerful balanced tree containers with order-statistics support using:
Key Operations
find_by_order(k): returns the kth smallest element (0-based index)order_of_key(x): returns the number of elements strictly less than (x)
The median is defined as the middle element when the window is sorted. If k is odd, it is the element at position (k $$$-$$$ 1) / 2 (0-based index). To solve this efficiently, we need a data structure that allows fast insertion, deletion, and access to the k-th smallest element all in logarithmic time.
To achieve this, the solution uses a Policy-Based Data Structure (PBDS) called an indexed_multiset, which behaves like a balanced BST with support for order statistics. This structure allows us to insert and erase elements in O(logk) time, and more importantly, get the k-th smallest element in the set using find_by_order(). We initialize the first window by inserting the first k elements into the multiset. The median is then accessed directly as the element at position (k $$$-$$$ 1) / 2 using find_by_order().
As we slide the window, we remove the outgoing element (the one that just left the window) and insert the new incoming element. For deletion, since PBDS doesn’t directly support erasing one occurrence of a value in a multiset, we locate the correct iterator using order_of_key() and then call erase() on it. After each update, we simply fetch the new median and store it in the result.
T.C. : O(nlogk).
Input
We compute the median for each sliding window of size (k = 3).
Median = element at index $$$\left\lfloor \dfrac{k-1}{2} \right\rfloor = 1$$$
Step-by-step Sliding Window and Median Calculation
Final Output:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define indexed_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k; cin >> n >> k;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
vector<int>res;
indexed_multiset st;
int ind = (k - 1) / 2;
for (int i = 0; i < k; ++i)
{
st.insert(v[i]);
}
int val = *(st.find_by_order(ind));
res.push_back(val);
for (int i = k; i < n; ++i)
{
auto curr = st.find_by_order(st.order_of_key(v[i - k]));
if (curr != st.end()) {
st.erase(curr);
}
st.insert(v[i]);
val = *(st.find_by_order(ind));
res.push_back(val);
}
for (int i = 0; i < res.size(); ++i)
{
cout << res[i] << " ";
}
}
Maintain two multisets one for the lower half (low) and one for the upper half (high) of the current window along with the sums of their elements (sm1 and sm2 respectively).
As we slide the window, we insert the new incoming element into the appropriate multiset based on size balance. If the sizes are unequal, we insert into the one with fewer elements to maintain balance. To keep the multisets valid around the median, we also check if the maximum of low is greater than the minimum of high. If so, we swap the elements between the two sets and update the running sums accordingly. When an element leaves the window, we check which set it belongs to and remove it while adjusting the respective sum. The median is always the largest element in low, i.e., *low.rbegin().
To compute the cost efficiently, we use the formula:
This equation avoids recomputing the absolute differences from scratch and instead leverages the already maintained sums and sizes of both sets.
T.C. : O(nlogk).
Inputn = 8, k = 3a = [2, 4, 3, 5, 8, 1, 2, 1]
| step | window | low (sorted) | high (sorted) | median | cost |
|---|---|---|---|---|---|
| 0–2 | 2 4 3 | {2, 3} | {4} | 3 | 2 |
| 1–3 | 4 3 5 | {3, 4} | {5} | 4 | 2 |
| 2–4 | 3 5 8 | {3, 5} | {8} | 5 | 5 |
| 3–5 | 5 8 1 | {1, 5} | {8} | 5 | 7 |
| 4–6 | 8 1 2 | {1, 2} | {8} | 2 | 7 |
| 5–7 | 1 2 1 | {1, 1} | {2} | 1 | 1 |
Output2 2 5 7 7 1
low always stores $$$\lceil k/2\rceil$$$ elements,
so the median $$$m$$$ is simply $$$\max(\text{low})$$$.
Cost formula used in code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k; cin >> n >> k;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
multiset<int>low, high;
int sm1 = 0, sm2 = 0;
for (int i = 0; i < n; ++i)
{
if (i >= k) {
if (low.find(v[i - k]) != low.end()) {
sm1 -= v[i - k];
low.erase(low.find(v[i - k]));
}
else {
sm2 -= v[i - k];
high.erase(high.find(v[i - k]));
}
}
int len1 = low.size(), len2 = high.size();
if (len1 <= len2) {
low.insert(v[i]);
sm1 += v[i];
}
else {
high.insert(v[i]);
sm2 += v[i];
}
len1 = low.size(), len2 = high.size();
if (len1 != 0 && len2 != 0) {
int first = *(low.rbegin());
int second = *(high.begin());
if (first > second) {
sm1 += (second - first);
sm2 += (first - second);
low.erase(low.find(first));
high.erase(high.find(second));
low.insert(second);
high.insert(first);
}
}
if (i >= (k - 1)) {
int median = *low.rbegin();
int len1 = low.size(), len2 = high.size();
int res = (len1 * median) - sm1 + (sm2 - (len2 * median));
cout << res << " " ;
}
}
}
Segment Tree
In this problem, we are given an array of n integers and a window size k. For each sliding window of size k, we need to calculate the number of inversions. An inversion in a window is defined as a pair (i, j) such that i < j and a[i] > a[j].To solving this efficiently need to dynamically maintaining inversion counts using a Segment Tree and coordinate compression.
The idea is to treat each number as a point on a compressed coordinate line, and then for each new element entering the window, count how many elements currently in the window are greater than it which directly contributes to the inversion count. To do this, we use a segment tree where each index stores how many times a compressed value has appeared in the current window. For an incoming number x, we query the range (x+1 to max) to count how many values greater than x already exist in the window. Similarly, when removing an outgoing number y, we subtract how many values less than y it had dominated, and update the segment tree accordingly.
To make this efficient, we apply coordinate compression to reduce the values of the array into a continuous range [0 ... unique_values $$$-$$$ 1]. This allows us to use the segment tree efficiently without needing to worry about the actual input range. The segment tree supports O(log n) queries and updates, so every insertion and deletion contributes inversions or removes them in logarithmic time.
T.C. : O(nlogn).
input : n = 8, k = 3
array [1, 2, 3, 2, 5, 2, 4, 4]
How the code updates the inversion count inv
- enter x → add
query(x+1 … max)(how many earlier window elements are> x) - leave y → subtract
query(0 … y-1)(how many remaining window elements are< y) - Segment tree stores a frequency on compressed values.
| step | window [l..r] | leaving y | entering x | Δinv (leave) | Δinv (enter) | new inv |
|---|---|---|---|---|---|---|
| 0–2 | 1 2 3 | – | – | – | – | 0 |
| 1–3 | 2 3 2 | 1 | 2 | −0 | +1 | 1 |
| 2–4 | 3 2 5 | 2 | 5 | −0 | +0 | 1 |
| 3–5 | 2 5 2 | 3 | 2 | −0 | +0 | 1 |
| 4–6 | 5 2 4 | 2 | 4 | −1 | +2 | 2 |
| 5–7 | 2 4 4 | 5 | 4 | −2 | +0 | 0 |
Queries shown are exactly what the code performs via the segment tree.
Output:0 1 1 1 2 0
The table shows every window, the element that leaves/enters, how each query changes inv, and the resulting value printed by the program.
#include <bits/stdc++.h>
using namespace std;
class SGTree {
vector<int> seg;
public:
SGTree(int n) {
seg.resize(4 * n);
}
int query(int ind, int low, int high, int l, int r) {
if (r < low || high < l) return 0;
if (l <= low && high <= r) return seg[ind];
int mid = (low + high) >> 1;
return query(2 * ind + 1, low, mid, l, r) + query(2 * ind + 2, mid + 1, high, l, r);
}
void update(int ind, int low, int high, int i, int val) {
if (low == high) {
seg[ind] += val;
return;
}
int mid = (low + high) >> 1;
if (i <= mid)
update(2 * ind + 1, low, mid, i, val);
else
update(2 * ind + 2, mid + 1, high, i, val);
seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n), comp(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
comp[i] = a[i];
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int sz = comp.size();
for (int i = 0; i < n; i++) {
a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
}
SGTree tree(sz);
long long inv = 0;
vector<long long> res;
for (int i = 0; i < k; i++) {
inv += tree.query(0, 0, sz - 1, a[i] + 1, sz - 1);
tree.update(0, 0, sz - 1, a[i], 1);
}
res.push_back(inv);
for (int i = k; i < n; i++) {
int y = a[i - k];
inv -= tree.query(0, 0, sz - 1, 0, y - 1);
tree.update(0, 0, sz - 1, y, -1);
int x = a[i];
inv += tree.query(0, 0, sz - 1, x + 1, sz - 1);
tree.update(0, 0, sz - 1, x, 1);
res.push_back(inv);
}
for (auto v : res) {
cout << v << ' ';
}
cout << endl;
return 0;
}
K. Sliding Window Advertisement
Li Chao tree
For the Sliding Window Median problem, I think a cool approach that dont require a PBS can be:
For a window $$$w_1, \dots, w_k$$$, let the multisets L and R be defined such that for all pairs $$$w_i \in L, w_j \in R : w_i \leq w_j$$$, $$$|L| = \lceil\frac{k}{2} \rceil$$$ and $$$|R| = \lfloor\frac{k}{2} \rfloor$$$. Then the median of the window will always be the biggest number in $$$L$$$.
We can build $$$L,R$$$ in $$$O(k\log k)$$$ for the first window. And for each step, we can easily insert/remove elements from $$$L$$$ and $$$R$$$ while correcting their size after each operation in $$$O(\log k)$$$. Giving a $$$O(k\log k + n\log k)$$$ solution.
I have another solution for the Sliding Window Median not usig a PBS:
Keep a sorted set $$$S$$$ of elements in the current window and an iterator pointing to the median element (
&m,mis the median). When adding an $$$x$$$ and removing an element $$$y$$$:it easy to prove that this ensures that
&malways points to the medianm.