test/data-structure/FastSet.test.cpp

View this file on GitHub
Last update: 2024-05-31 19:00:40+09:00
Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include "test/template.hpp"
using u64 = uint64_t;
#include "src/data-structure/FastSet.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   ll N, Q;
   cin >> N >> Q;
   string S;
   cin >> S;
   FastSet s(N);
   rep(i, 0, N) if(S[i] == '1') s.set(i);
   while(Q--) {
      ll c, k;
      cin >> c >> k;
      if(c == 0) s.set(k);
      if(c == 1) s.reset(k);
      if(c == 2) cout << (s.a[0][k / B] >> (k % B) & 1) << '\n';
      if(c == 3) {
         ll ans = s.next(k - 1);
         cout << (ans == N ? -1 : ans) << '\n';
      }
      if(c == 4) cout << s.prev(k + 1) << '\n';
   }
}

#line 1 "test/data-structure/FastSet.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 3 "test/data-structure/FastSet.test.cpp"
using u64 = uint64_t;
#line 1 "src/data-structure/FastSet.hpp"
// using u64 = uint64_t;
const u64 B = 64;
struct FastSet {
   u64 n;
   vector<vector<u64>> a;
   FastSet(u64 n_) : n(n_) {
      do a.emplace_back(n_ = (n_ + B - 1) / B);
      while(n_ > 1);
   }
   // bool operator[](ll i) const { return a[0][i / B] >> (i % B) & 1; }
   void set(ll i) {
      for(auto& v : a) {
         v[i / B] |= 1ULL << (i % B);
         i /= B;
      }
   }
   void reset(ll i) {
      for(auto& v : a) {
         v[i / B] &= ~(1ULL << (i % B));
         if(v[i / B]) break;
         i /= B;
      }
   }
   ll next(ll i) {  // i を超える最⼩の要素
      rep(h, 0, sz(a)) {
         i++;
         if(i / B >= sz(a[h])) break;
         u64 d = a[h][i / B] >> (i % B);
         if(d) {
            i += countr_zero(d);
            while(h--) i = i * B + countr_zero(a[h][i]);
            return i;
         }
         i /= B;
      }
      return n;
   }
   ll prev(ll i) {  // i より小さい最⼤の要素
      rep(h, 0, sz(a)) {
         i--;
         if(i < 0) break;
         u64 d = a[h][i / B] << (~i % B);
         if(d) {
            i -= countl_zero(d);
            while(h--) i = i * B + __lg(a[h][i]);
            return i;
         }
         i /= B;
      }
      return -1;
   }
};
#line 5 "test/data-structure/FastSet.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   ll N, Q;
   cin >> N >> Q;
   string S;
   cin >> S;
   FastSet s(N);
   rep(i, 0, N) if(S[i] == '1') s.set(i);
   while(Q--) {
      ll c, k;
      cin >> c >> k;
      if(c == 0) s.set(k);
      if(c == 1) s.reset(k);
      if(c == 2) cout << (s.a[0][k / B] >> (k % B) & 1) << '\n';
      if(c == 3) {
         ll ans = s.next(k - 1);
         cout << (ans == N ? -1 : ans) << '\n';
      }
      if(c == 4) cout << s.prev(k + 1) << '\n';
   }
}