sliding window or(CSES)

amankbps's blog

By amankbps, history, 12 months ago, In English

You are given an array of n integers. Your task is to calculate the bitwise or of each window of k elements, from left to right. In this problem the input data is large and it is created using a generator. Input The first line contains two integers n and k: the number of elements and the size of the window. The next line contains four integers x, a, b and c: the input generator parameters. The input is generated as follows:

problem link

how to solve this efficiently i got tle when i try to solve n*31

sliding window, bitmask

amankbps
12 months ago
24

Comments (23)

Show archived | Write comment?

coderdhanraj

12 months ago, hide # |

+16

Hint: Double Deque or Four Stacks (Double Stack trick to work as a deque).

→ Reply

SamyakSinghania

12 months ago, hide # ^ |

can you elaborate?

→ Reply

HusseinFarhat

12 months ago, hide # ^ |

Check this

→ Reply

SamyakSinghania

12 months ago, hide # ^ |

Not sure if this is the intended solution but optimizing the loop for counting bits works. https://cses.fi/paste/e1dabeef32aa00fbc4cc83/

→ Reply

ngu_dot

12 months ago, hide # |

← Rev. 2 →

+30

First of all, you need to construct the array $$$a$$$ from the provided generator.

After that, you split $$$a$$$ into several blocks of length $$$k$$$ with the length of the last one being at most $$$k$$$ (since $$$n \equiv 0$$$ $$$(mod$$$ $$$k)$$$ doesn't always hold), then compute the prefix and suffix OR of each of these blocks. For better understanding, here is an illustration for $$$n = 8, k = 3$$$ (I know I'm talented at drawing <(")).

Ultimately, the answer for a window $$$[i-k+1, i]$$$ is basically just $$$pre_i$$$ $$$|$$$ $$$suf_{i-k+1}$$$. For example, the OR sum of the window $$$[3, 5]$$$ is $$$pre_5$$$ $$$|$$$ $$$suf_3$$$ which is equal to $$$a_3$$$ $$$|$$$ $$$a_4$$$ $$$|$$$ $$$a_5$$$.

The resulting complexity is $$$O(n)$$$ for both time and memory.

→ Reply

H_a_r_M_i_t

12 months ago, hide # ^ |

← Rev. 3 →

Loved the idea, first time I’ve come across this kind of trick!

Attaching the Accepted C++ code for the above approach.

C++ Code - AC

#include <bits/stdc++.h>
using namespace std;

#define Author_HarMit ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long

#define fo(i, n) for (ll i = 0; i < n; i++)
#define rfo(i, n) for (ll i = n - 1; i >= 0; i--)

#define in(n) ll n; cin >> n;
#define inn(n, k) ll n, k; cin >> n >> k;
#define vin(a, n) vector<ll> a(n); for (ll i = 0; i < n; i++) cin >> a[i];
#define strin(s) string s; cin >> s;

#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))

const ll inf = 1e15;
const ll mod = 998244353;

// In the end, when it's all over, all that matters is what you have done.

/*    
    
*/


void useless(){
    
    ll n,k;
    cin >> n >> k;

    ll x;
    cin >> x;

    ll a,b,c;
    cin >> a >> b >> c;

    vector<ll> vec(n);
    vec[0] = x;

    for(ll i=1; i<n; i++){
        vec[i] = (vec[i-1]*a%c + b)%c;
    }

    ll totSeg = (n + k-1)/k;

    ll res = 0;

    vector<ll> nxtPref(k,0);
    vector<ll> curSuff(k,0);

    for(ll seg=0; seg+1<totSeg; seg++){

        ll BaseId = seg*k;
        ll LastId = min(n-1,BaseId+k-1);

        // calculate current suffix
            ll cId;
            ll cBaseId = seg*k;
            ll cLastId = min(n-1,cBaseId+k-1);

            for(ll i=cLastId; i>=cBaseId; i--){
                cId = i-cBaseId;

                if(i==cLastId)
                    curSuff[cId] = vec[i];
                else
                    curSuff[cId] = vec[i] | curSuff[cId+1];
            }

        // calculate next prefix
            ll nId;
            ll nBaseId = (seg+1)*k;
            ll nLastId = min(n-1,nBaseId+k-1);

            for(ll i=nBaseId; i<=nLastId; i++){
                nId = i-nBaseId;

                if(i==nBaseId)
                    nxtPref[nId] = vec[i];
                else
                    nxtPref[nId] = vec[i] | nxtPref[nId-1];
            }

        for(ll i=BaseId; i<=LastId && i<(n-k+1); i++){
            ll inNxtSeg = i - BaseId;
            ll inCurSeg = k - inNxtSeg;

            ll currOrr = 0;

            if(inNxtSeg == 0){
                currOrr = curSuff[0];
            }
            else{
                currOrr = curSuff[k - inCurSeg] | nxtPref[inNxtSeg - 1];
            }

            res = res ^ currOrr;
        }
    }   

    // i.e. last seg is of size k
    if(n%k == 0){
        ll cId;
        ll cBaseId = (totSeg-1)*k;
        ll cLastId = min(n-1,cBaseId+k-1);

        for(ll i=cLastId; i>=cBaseId; i--){
            cId = i-cBaseId;

            if(i==cLastId)
                curSuff[cId] = vec[i];
            else
                curSuff[cId] = vec[i] | curSuff[cId+1];
        }

        ll currOrr = curSuff[0];
        res = res ^ currOrr;
    }

    cout << res << '\n';

}

signed main(){
    Author_HarMit;
    
    ll tt = 1;
    // cin >> tt;
    
    while(tt--) {
        useless();
    }
    
    return 0;
}

C++ Code - Much Simpler than mine

/**
 *    author:  devangsvaghani
 *    created: 15.05.2025 16:27:35
**/

#include <bits/stdc++.h>
using namespace std;

#ifndef ONLINE_JUDGE
#include "dev/debug.hpp"
#else
#define debug(...) 8
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

#define all(x) (x).begin(), (x).end()
#define f(i, x, n) for (ll i = x; i < n; i++)
#define rf(i, x, n) for (ll i = x; i >= n; i--)

const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ll N = 1e6+5;

void init(){
    
}

void solve(){
    ll n, k;
    cin >> n >> k;

    ll x, a, b, c;
    cin >> x >> a >> b >> c;

    vector<ll> p(n), s(n), v(n);
    p[0] = s[n - 1] = x;
    v[0] = x;
    f(i, 1, n) v[i] = (v[i - 1] * a + b) % c;

    ll ans = 0;
    if(k == 1){
        f(i, 0, n) ans ^= v[i];
        cout << ans << "\n";
        return;
    }

    f(i, 1, n){
        p[i] = (i % k == 0 ? v[i] : p[i - 1] | v[i]); 
    }

    rf(i, n - 2, 0){
        s[i] = (i % k == k - 1 ? v[i] : s[i + 1] | v[i]);
    }

    
    f(i, k - 1, n){
        if(i % k == k - 1){
            ans ^= p[i];
        }else{
            ans ^= (s[i - k + 1] | p[i]);
        }
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    // #ifndef ONLINE_JUDGE
    //   freopen("input.txt", "r", stdin);
    //   freopen("output.txt", "w", stdout);
    //   freopen("Error.txt", "w", stderr);
    // #endif

    init();
    
    ll t = 1;
    // cin >> t;
    for (ll T = 1; T <= t; T++) {
        // debug(T);
        solve();
    }
    return 0;
}

I initially tried a simpler implementation using a 2D vector to store prefix and suffix arrays for each segment, but that gave a RUNTIME ERROR due to overhead—especially when k = 1, leading to around 1e7 vectors being created. So, I optimized the space by reusing 1D vectors curSuff and nxtPref during segment iteration. Also Attaching that Code.

C++ Code - RE

#include <bits/stdc++.h>
using namespace std;
 
#define Author_HarMit ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
 
#define fo(i, n) for (ll i = 0; i < n; i++)
#define rfo(i, n) for (ll i = n - 1; i >= 0; i--)
 
#define in(n) ll n; cin >> n;
#define inn(n, k) ll n, k; cin >> n >> k;
#define vin(a, n) vector<ll> a(n); for (ll i = 0; i < n; i++) cin >> a[i];
#define strin(s) string s; cin >> s;
 
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
 
const ll inf = 1e15;
const ll mod = 998244353;
 
// In the end, when it's all over, all that matters is what you have done.
 
/*    
    
*/
 
 
void useless(){
    
    ll n,k;
    cin >> n >> k;
 
    ll x;
    cin >> x;
 
    ll a,b,c;
    cin >> a >> b >> c;
 
    vector<ll> vec(n);
    vec[0] = x;
 
    for(ll i=1; i<n; i++){
        vec[i] = (vec[i-1]*a + b)%c;
    }
 
    ll totSeg = (n + k-1)/k;
 
    vector<vector<ll>> pref(totSeg, vector<ll> (k, 0));
    vector<vector<ll>> suff(totSeg, vector<ll> (k, 0));
 
    for(ll seg=0; seg<totSeg; seg++){
 
        ll baseId = seg*k;
        ll lastId = min(n-1,baseId+k-1);
 
        for(ll i=baseId; i<=lastId; i++){
            if(i==baseId)
                pref[seg][i-baseId] = vec[i];
            else
                pref[seg][i-baseId] = vec[i] | pref[seg][i-baseId-1];
        }
 
        for(ll i=lastId; i>=baseId; i--){
            if(i==lastId)
                suff[seg][i-baseId] = vec[i];
            else
                suff[seg][i-baseId] = vec[i] | suff[seg][i-baseId+1];
        }
 
    }
 
    ll res = 0;
 
    for(ll i=0; i+k-1<n; i++){
 
        ll segId = i/k;
        ll inNxtSeg = i%k;
        ll inCurSeg = k - inNxtSeg;
 
        ll currOrr = 0;
 
        if(inNxtSeg == 0){
            currOrr = suff[segId][0];
        }
        else{
            currOrr = suff[segId][k - inCurSeg] | pref[segId+1][inNxtSeg - 1];
        }
 
        res = res ^ currOrr;
    }   
 
    cout << res << '\n';
 
}
 
signed main(){
    Author_HarMit;
    
    ll tt = 1;
    // cin >> tt;
    
    while(tt--) {
        useless();
    }
    
    return 0;
}

→ Reply

VaiseIamHere

5 months ago, hide # ^ |

There is a minor initialization bug in the smaller code where "s[n — 1] = x" is not true always, thanks for sharing the code btw!

→ Reply

surajiyer

12 months ago, hide # ^ |

Wow, how did you come up with this?

→ Reply

i-am-vivek

12 months ago, hide # ^ |

Thanks for sharing such a nice solution. Here is my C++ code :-)


#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k; cin >> n >> k;
    int64_t x, a, b, c; cin >> x >> a >> b >> c;
    vector<int64_t> arr(n);
    vector<int64_t> prefix(n);
    vector<int64_t> suffix(n);

    arr[0] = x;
    for (int i = 1; i < n; i++) arr[i] = (a * arr[i - 1] + b) % c;

    prefix[0] = x;
    for (int i = 1; i < n; i++) {
        if (i % k == 0) prefix[i] = arr[i];
        else prefix[i] = prefix[i - 1] | arr[i];
    }

    suffix[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        if (i % k == k - 1) suffix[i] = arr[i];
        else suffix[i] = suffix[i + 1] | arr[i];
    }

    int64_t ans = 0;
    int l = 0, r = k - 1;
    while (r < n) {
        if (r % k == k - 1) ans ^= prefix[r];
        else ans ^= (prefix[r] | suffix[l]);
        r++, l++;
    }

    cout << ans << "\n";
}

→ Reply

amankumar0724

10 months ago, hide # ^ |

amazing solution bro

→ Reply

Snowdust

10 months ago, hide # ^ |

The same concept is used in another CSES Range Query problem which asks to find the maximum subarray sum in a given range [l...r]. When merging two childs one of the best segment (segment with the maximum subarray sum) could lie partially in the left child and right child and it is always possible to make that segment with some suffix of left child and prefix of right child ! So we store prefix, suffix sum max of each segment (and also another stuff the ans) in each child and get the answer by quering...Same concept used here!

→ Reply

Arise_0111

7 months ago, hide # ^ |

We can say that main logic comes from the observation that range of size k cannot lie in more than 2 different k size segments.

Functions like min, max, OR, AND follows Idempotent and associative property therefore they are Overlapping-friendly Operation.

This trick can also be seen as the specialization of sparse table for fixed range.

→ Reply

Snowdust

3 months ago, hide # ^ |

True

→ Reply

PhanTom_001

7 months ago, hide # ^ |

Appreciated man! way too clean and way too brilliant solution!!

→ Reply

avighnakc

6 months ago, hide # ^ |

Literally too orz

I drew this while implementing, just posting it here for reference

→ Reply

nikhil_thogaru

4 months ago, hide # ^ |

Good observation

→ Reply

vstiff

12 months ago, hide # |

-19

Alternative solution is observe that once bit is seen it will be on for k next windows, so just track off time for each bit and reconstruct or.

→ Reply

pasricha_dhruv

12 months ago, hide # |

Just wrote a blog on this: Sliding Window: Handling Non-Invertible operators

→ Reply

cry

12 months ago, hide # |

well i did get ac with n*30 lol, probably because the constant factor was really good https://cses.fi/paste/a871c74160e6983ec5e9d5/

→ Reply

SkiLl1_ISSuE

8 months ago, hide # |

Can't we store the sum of bitcounts a window in a count array and update the or of the window?

→ Reply

dhananjaysangle29

8 months ago, hide # |

← Rev. 2 →

Soution with two stacks. Easy to understand and accepted AC. The idea is to use two stacks one for storing bitwise or of first k elements and the other is to store bitwise or of the same elements in the reverse order so we get bitwise or in reverse order. C++ code Link. https://cses.fi/paste/a0140c746968381fe1ba9b/

→ Reply