sliding window or(CSES)

→ Обратите внимание

До соревнования
Codeforces Round 1123 (Div. 2)
13:24:48
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 1123 Solution Discussion

aryanc403

До начала 15:49:48

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	136
8	BledDest	132
9	maroonrk	131
10	qwexd	129

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя amankbps

sliding window or(CSES)

Автор amankbps, история, 16 месяцев назад, По-английски

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
16 месяцев назад
25

Комментарии (23)

Показать архивные | Написать комментарий?

coderdhanraj

16 месяцев назад, скрыть # |

+16

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

→ Ответить

SamyakSinghania

16 месяцев назад, скрыть # ^ |

can you elaborate?

→ Ответить

HusseinFarhat

16 месяцев назад, скрыть # ^ |

Check this

→ Ответить

SamyakSinghania

16 месяцев назад, скрыть # ^ |

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

→ Ответить

Iameuler

4 месяца назад, скрыть # ^ |

I don't think this works anymore.

→ Ответить

ngu_dot

16 месяцев назад, скрыть # |

← 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.

→ Ответить

H_a_r_M_i_t

16 месяцев назад, скрыть # ^ |

← 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;
}

→ Ответить

VaiseIamHere

9 месяцев назад, скрыть # ^ |

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!

→ Ответить

surajiyer

16 месяцев назад, скрыть # ^ |

Wow, how did you come up with this?

→ Ответить

i-am-vivek

16 месяцев назад, скрыть # ^ |

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";
}

→ Ответить

Snowdust

14 месяцев назад, скрыть # ^ |

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!

→ Ответить

Arise_0111

11 месяцев назад, скрыть # ^ |

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.

→ Ответить

Snowdust

7 месяцев назад, скрыть # ^ |

True

→ Ответить

PhanTom_001

11 месяцев назад, скрыть # ^ |

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

→ Ответить

avighnakc

10 месяцев назад, скрыть # ^ |

Literally too orz

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

→ Ответить

nikhil_thogaru

8 месяцев назад, скрыть # ^ |

Good observation

→ Ответить

vstiff

16 месяцев назад, скрыть # |

-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.

→ Ответить

pasricha_dhruv

16 месяцев назад, скрыть # |

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

→ Ответить

cry

16 месяцев назад, скрыть # |

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

→ Ответить

SkiLl1_ISSuE

12 месяцев назад, скрыть # |

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

→ Ответить

dhananjaysangle29

12 месяцев назад, скрыть # |

← 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/

→ Ответить

Juan_Alejandro

7 месяцев назад, скрыть # |

Total overkill: I solved it with a segment tree of OR

→ Ответить

CarViz

7 месяцев назад, скрыть # |

-14

not sure if this is a foolish solution but im pretty sure you could just store the count of each bit and get n that way

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 25.09.2026 04:10:12 (f1).

Десктопная версия, переключиться на мобильную.

При поддержке