#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 hashmultimap{ private: float load_factor = 0.8; int table_size = 16; int mod = 15; Key null_key; uint32_t mask; int valid_size; int valid_type; vector idx_table; vector key_data; vector> val_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()()), valid_size(0), valid_type(0), idx_table(table_size, -1){} //データ数の総和 int size(){ return valid_size; } //データの種類数 int type(){ return valid_type; } //挿入 void emplace(Key k, Val v){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx!=-1){ if(key_data[idx]==k){ val_data[idx].push_back(v); valid_size++; return; } h = (h + 1) & mod; }else{ int m = key_data.size(); key_data.push_back(k); val_data.push_back(vector()); val_data[m].push_back(v); idx_table[h] = m; valid_type++; valid_size++; if(float(key_data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } //Key kの値を全て削除 void erase_all(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx==-1) return; if(key_data[idx]==k){ key_data[idx].first = null_key; valid_size -= int(val_data[idx].size()); valid_type--; val_data[idx].clear(); return; } h = (h + 1) & mod; } } //Key kに含まれている要素数 int size(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(key_data[idx]==k) return int(val_data[idx].size()); h = (h + 1) & mod; } } //Key kの要素たちを受け取る(計算量に注意) vector at(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx==-1) return vector(0); if(key_data[idx]==k) { return val_data[idx]; } h = (h + 1) & mod; } } }; int main(){ ll n, m;scanf("%lld %lld", &n, &m); hashmultimap mp; for(int i=0;i