#include "data_structure/bit_vector.hpp"
#pragma once /** * @brief BitVector */ class bitvec{ using u32=unsigned int; using u8=unsigned char; using lint=long long; //4*10^6対応 //ブロック幅8,チャンク幅256 const int bw=8,cw=256; const int len=15625,sz=4000000; bool data[4000000]={0}; u32 chunk[15626]; u8 block[15625][33]; public: bitvec(){} void build(){ chunk[0]=0; for(int i=0;i<15625;i++){ block[i][0]=0; for(int j=0;j<31;j++){ block[i][j+1]=block[i][j]; for(int k=0;k<8;k++)block[i][j+1]+=data[i*cw+j*bw+k]; } chunk[i+1]=chunk[i]+block[i][31]; for(int k=0;k<8;k++)chunk[i+1]+=data[i*cw+31*bw+k]; } } inline void set(int idx,bool b){data[idx]=b;} inline bool get(int idx){return data[idx];} inline int rank(int idx,bool b)const{ if(b)return rank1(idx); else return idx-rank1(idx); } inline int rank1(int idx)const{ int a=idx/cw,b=idx%cw/bw,c=idx%bw; int res=chunk[a]+block[a][b]; for(int i=1;i<c+1;i++)res+=data[idx-i]; return res; } inline int select(int num){ if (num==0)return 0; if (rank1(sz)<num)return -1; int ok=sz,ng=0; while (ok-ng>1) { int mid=(ok+ng)/2; if (rank1(mid)>=num)ok =mid; else ng=mid; } return ok; } };
#line 2 "data_structure/bit_vector.hpp" /** * @brief BitVector */ class bitvec{ using u32=unsigned int; using u8=unsigned char; using lint=long long; //4*10^6対応 //ブロック幅8,チャンク幅256 const int bw=8,cw=256; const int len=15625,sz=4000000; bool data[4000000]={0}; u32 chunk[15626]; u8 block[15625][33]; public: bitvec(){} void build(){ chunk[0]=0; for(int i=0;i<15625;i++){ block[i][0]=0; for(int j=0;j<31;j++){ block[i][j+1]=block[i][j]; for(int k=0;k<8;k++)block[i][j+1]+=data[i*cw+j*bw+k]; } chunk[i+1]=chunk[i]+block[i][31]; for(int k=0;k<8;k++)chunk[i+1]+=data[i*cw+31*bw+k]; } } inline void set(int idx,bool b){data[idx]=b;} inline bool get(int idx){return data[idx];} inline int rank(int idx,bool b)const{ if(b)return rank1(idx); else return idx-rank1(idx); } inline int rank1(int idx)const{ int a=idx/cw,b=idx%cw/bw,c=idx%bw; int res=chunk[a]+block[a][b]; for(int i=1;i<c+1;i++)res+=data[idx-i]; return res; } inline int select(int num){ if (num==0)return 0; if (rank1(sz)<num)return -1; int ok=sz,ng=0; while (ok-ng>1) { int mid=(ok+ng)/2; if (rank1(mid)>=num)ok =mid; else ng=mid; } return ok; } };