#1166113 (C++17) No.3553 Good Quartet

• 問題: No.3553 Good Quartet
• ユーザー: 👑 Nachia
• 提出日時: 2026-05-22 22:58:20
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 163 ms / 2,000 ms
• コード長: 6,132 bytes
• コンパイル時間: 1,253 ms
• コンパイル使用メモリ: 128,264 KB
• 実行使用メモリ: 54,128 KB
• 最終ジャッジ日時: 2026-05-22 22:58:26
• 合計ジャッジ時間: 5,340 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 15

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <optional>
#include <type_traits>
#include <cstring>

namespace nachia {

    template<typename K>
    struct Hash {
        using u64 = unsigned long long;
        using u128 = __uint128_t;
        u64 seed;
        u64 base;
        static u64 RngInit(){
            return std::chrono::high_resolution_clock::now().time_since_epoch().count() ^ std::random_device()();
        };
        u64 splitmix64(u64& x) {
            u64 z = (x += 0x9e3779b97f4a7c15);
            z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            return z ^ (z >> 31);
        }
        Hash() : seed(RngInit()), base(mulmod(splitmix64(seed), 1)) {}
        Hash(u64 seed) : seed(seed) {}
        static constexpr u64 MOD = (1ull << 61) - 1;
        static u64 takemod(u64 a){ return a >= MOD ? a - MOD : a; }
        static u64 mulmod(u64 a, u64 b){
            u128 x = u128(a) * b;
            return takemod((x >> 61) + (x & MOD));
        }
        template<typename L = K, std::enable_if_t<std::is_trivially_copyable_v<L>, int> = 0>
        u64 operator()(const K& key) const {
            if constexpr (std::is_integral_v<L> && (sizeof(L) <= 8)) return hash_trivial(key);
            constexpr size_t z = (sizeof(K) + 7) / 8;
            u64 h[z] = {}, res = 0;
            memcpy(h, &key, sizeof(K));
            for(u64 a : h) res = takemod(mulmod(res, base) + hash_trivial(a));
            return res;
        }
        u64 operator()(const K& key, int bitnum) const { return operator()(key) >> (61 - bitnum); }
    private:
        u64 hash_trivial(u64 key) const {
            u64 x = (key ^ seed) * 0x1cafefdc0172110full;
            return takemod((x >> 61) + (x & MOD));
        }
    };

} // namespace nachia

namespace nachia {

    template<class Key, class Val>
    struct HashMap {
        struct Tuple {
            Key key;
            Val val;
            bool has = false;
        };

        Hash<Key> hasher;
        int lgn;
        int n;
        unsigned long long mask;
        std::vector<Tuple> vload;

        struct iterator {
            typename std::vector<Tuple>::iterator i;
            typename std::vector<Tuple>::iterator e;
            iterator& operator++(){ i++; while(i != e && !i->has){ i++; } return *this; }
            iterator operator++(int) { auto res = *this; ++*this; return res; }
            bool operator==(const iterator& r) const { return i == r.i; }
            bool operator!=(const iterator& r) const { return !(i == r.i); }
            Tuple* operator->() const { return i.operator->(); }
        };

        HashMap() : lgn(2), n(0), mask(0), vload(0){}

        int hkey(const Key& key) const { return hasher(key, lgn); }
        int find_internal(const Key& key) const {
            int p = hkey(key);
            while(vload[p].has && !(vload[p].key == key)) p = (p + 1) & mask;
            return p;
        }
        void set_internal(Key key, Val val){
            int p = find_internal(key);
            if(!vload[p].has){ vload[p].key = std::move(key); vload[p].has = true; }
            vload[p].val = std::move(val);
        }

        void alloc(int new_lgn){
            lgn = new_lgn;
            mask = (1ull << lgn) - 1;
            auto buf = std::move(vload);
            vload.assign(1 << lgn, Tuple());
            for(size_t i=0; i<buf.size(); i++) if(buf[i].has){
                set_internal(std::move(buf[i].key), std::move(buf[i].val));
            }
        }

        Val& operator[](const Key& key){
            if(n >= int(mask / 2)) alloc(lgn + 1);
            int p = find_internal(key);
            if(!vload[p].has){ vload[p].key = std::move(key); vload[p].has = true; n++; }
            return vload[p].val;
        }

        int size(){ return n; }
        iterator begin() {
            if(size() == 0) return end();
            auto i = vload.begin();
            while(!i->has) i++;
            return { i, vload.end() };
        }
        iterator end() { return { vload.end(), vload.end() }; }
        iterator find(const Key& key){
            int p = find_internal(key);
            if(!vload[p].has) return end();
            return { vload.begin() + p, vload.end() };
        }

        void clear() {
            vload.clear();
            lgn = 2; n = 0; mask = 0;
        }

        void reserve(int expect_n){
            if(expect_n < n) expect_n = n;
            int next_lgn = 3;
            while(expect_n >= (1 << next_lgn) / 2 - 1) next_lgn++;
            alloc(next_lgn);
        }
    };

} // namespace nachia
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

void testcase(){
  ll N, Q; cin >> N >> Q;
  V<ll> A(N); REP(i,N) cin >> A[i];
  nachia::HashMap<ll, ll> ds0, ds1, ds2;
  ll ans = 0;
  auto insds0 = [&](ll x) -> void { if(++ds0[x] == 4) ans += 1; };
  auto remds0 = [&](ll x) -> void { if(ds0[x]-- == 4) ans -= 1; };
  auto insds1 = [&](ll x) -> void { if(++ds1[x] == 4) ans += 1; };
  auto remds1 = [&](ll x) -> void { if(ds1[x]-- == 4) ans -= 1; };
  auto insds2 = [&](ll x) -> void { if(++ds2[x] == 4) ans += 1; };
  auto remds2 = [&](ll x) -> void { if(ds2[x]-- == 4) ans -= 1; };
  auto insxds = [&](ll x) -> void {
    for(ll d : {1,5,7,11})   if(x%d == 0) insds0(x/d);
    for(ll d : {1,11,19,29}) if(x%d == 0) insds1(x/d);
  };
  auto remxds = [&](ll x) -> void {
    for(ll d : {1,5,7,11})   if(x%d == 0) remds0(x/d);
    for(ll d : {1,11,19,29}) if(x%d == 0) remds1(x/d);
  };
  REP(i,N) insxds(A[i]);
  REP(qi,Q){
    ll t, x; cin >> t >> x;
    if(t == 1) insxds(x); else remxds(x);
    cout << ans << "\n";
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}