Fast Set
(DataStructure/fastset.hpp)

• View this file on GitHub
• Last update: 2024-01-12 04:16:01+09:00
• Include: #include "DataStructure/fastset.hpp"

Code

#pragma once

struct FastSet{
    static constexpr int B=64;
    int n,lg;
    vector<vector<ull>> seg;
    FastSet(int m):n(m){
        do{
            seg.push_back(vector<ull>((m+B-1)/B));
            m=(m+B-1)/B;
        }while(m>1);
        lg=seg.size();
    }
    bool operator[](int i)const{
        return (seg[0][i/B]>>(i%B)&1);
    }
    void insert(int i){
        rep(h,0,lg){
            seg[h][i/B]|=1ull<<(i%B);
            i/=B;
        }
    }
    void erase(int i){
        rep(h,0,lg){
            seg[h][i/B]&=~(1ull<<(i%B));
            if(seg[h][i/B])break;
            i/=B;
        }
    }
    int next(int i){ // smallest >= i
        rep(h,0,lg){
            if(i/B==seg[h].size())break;
            ull d=seg[h][i/B]>>(i%B);
            if(!d){
                i=i/B+1;
                continue;
            }
            i+=lowbit(d);
            for(int g=h-1;g>=0;g--){
                i*=B;
                i+=lowbit(seg[g][i/B]);
            }
            return i;
        }
        return -1;
    }
    int prev(int i){ // largest <= i
        rep(h,0,lg){
            if(i==-1)break;
            ull d=seg[h][i/B]<<(63-i%64);
            if(!d){
                i=i/B-1;
                continue;
            }
            i+=topbit(d)-(B-1);
            for(int g=h-1;g>=0;g--){
                i*=B;
                i+=topbit(seg[g][i/B]);
            }
            return i;
        }
        return -1;
    }
};

/**
 * @brief Fast Set
 */

#line 2 "DataStructure/fastset.hpp"

struct FastSet{
    static constexpr int B=64;
    int n,lg;
    vector<vector<ull>> seg;
    FastSet(int m):n(m){
        do{
            seg.push_back(vector<ull>((m+B-1)/B));
            m=(m+B-1)/B;
        }while(m>1);
        lg=seg.size();
    }
    bool operator[](int i)const{
        return (seg[0][i/B]>>(i%B)&1);
    }
    void insert(int i){
        rep(h,0,lg){
            seg[h][i/B]|=1ull<<(i%B);
            i/=B;
        }
    }
    void erase(int i){
        rep(h,0,lg){
            seg[h][i/B]&=~(1ull<<(i%B));
            if(seg[h][i/B])break;
            i/=B;
        }
    }
    int next(int i){ // smallest >= i
        rep(h,0,lg){
            if(i/B==seg[h].size())break;
            ull d=seg[h][i/B]>>(i%B);
            if(!d){
                i=i/B+1;
                continue;
            }
            i+=lowbit(d);
            for(int g=h-1;g>=0;g--){
                i*=B;
                i+=lowbit(seg[g][i/B]);
            }
            return i;
        }
        return -1;
    }
    int prev(int i){ // largest <= i
        rep(h,0,lg){
            if(i==-1)break;
            ull d=seg[h][i/B]<<(63-i%64);
            if(!d){
                i=i/B-1;
                continue;
            }
            i+=topbit(d)-(B-1);
            for(int g=h-1;g>=0;g--){
                i*=B;
                i+=topbit(seg[g][i/B]);
            }
            return i;
        }
        return -1;
    }
};

/**
 * @brief Fast Set
 */

Back to top page