#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c struct hashset{ private: float load_factor = 0.8; int table_size = 16; int mod = 15; int valid_data; const Key null_key; uint32_t mask; vector idx_table; vector data; function f = std::hash(); void expand_table(){ table_size *= 2; mod = table_size - 1; idx_table.resize(table_size); fill(idx_table.begin(), idx_table.end(), -1); for(int i=0;i::max()), mask(random_device()()),idx_table(table_size, -1){} int size(){ return valid_data; } void erase(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ if(idx_table[h]==-1) return; if(data[idx_table[h]]==k){ data[idx_table[h]] = null_key; valid_data--; return; } h = (h + 1) & mod; } } void insert(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ if(idx_table[h]!=-1){ if(data[idx_table[h]]==k) return; h = (h + 1) & mod; }else{ data.push_back(k); idx_table[h] = int(data.size())-1; valid_data++; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } bool contain(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ if(idx_table[h]==-1) return false; if(data[idx_table[h]]==k) return true; h = (h + 1) & mod; } } }; template struct hashmultiset{ private: float load_factor = 0.8; int table_size = 16; int mod = 15; const Key null_key; uint32_t mask; vector idx_table; vector> data; function f = std::hash(); void expand_table(){ table_size *= 2; mod = table_size - 1; idx_table.resize(table_size); fill(idx_table.begin(), idx_table.end(), -1); for(int i=0;i::max()), mask(random_device()()),idx_table(table_size){} /* int size(){ return data.size(); } */ void insert(Key k, Cnt x=1){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx!=-1){ if(data[idx].first==k){ data[idx].second += x; return; } h = (h + 1) & mod; }else{ data.push_back({k, x}); idx_table[h] = int(data.size()) - 1; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } void erase(Key k, Cnt x=std::numeric_limits::max()){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx==-1) return; if(data[idx].first==k){ if(data[idx].second > x) data[idx].second -= x; else data[idx].first = null_key; return; } h = (h + 1) & mod; } } int count(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx==-1) return 0; if(data[idx].first==k) return data[idx].second; h = (h + 1) & mod; } } }; int main(){ ll n, m;scanf("%lld %lld", &n, &m); hashmultiset st; for(int i=0;i