結果
問題 |
No.3298 K-th Slime
|
ユーザー |
|
提出日時 | 2025-10-05 13:54:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 352 ms / 2,000 ms |
コード長 | 9,102 bytes |
コンパイル時間 | 4,777 ms |
コンパイル使用メモリ | 335,012 KB |
実行使用メモリ | 85,760 KB |
最終ジャッジ日時 | 2025-10-05 13:54:24 |
合計ジャッジ時間 | 8,875 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); } istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } typedef long long ll; typedef vector<vector<int>> Graph; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define FOR(i,l,r) for (int i = l;i < (int)(r); i++) #define rep(i,n) for (int i = 0;i < (int)(n); i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define my_sort(x) sort(x.begin(), x.end()) #define my_max(x) *max_element(all(x)) #define my_min(x) *min_element(all(x)) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int INF = (1<<30) - 1; const ll LINF = (1LL<<62) - 1; const int MOD = 998244353; const int MOD2 = 1e9+7; const double PI = acos(-1); vector<int> di = {1,0,-1,0}; vector<int> dj = {0,1,0,-1}; #ifdef LOCAL # include <debug_print.hpp> # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif // Binary Trie template<typename INT, size_t MAX_DIGIT> struct BinaryTrie { struct Node { size_t count; Node *prev, *left, *right; Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {} }; INT lazy; Node *root; // constructor BinaryTrie() : lazy(0), root(emplace(nullptr)) {} inline size_t get_count(Node *v) const { return v ? v->count : 0; } // add and get value of Node inline void add(INT val) { lazy ^= val; } inline INT get(Node *v) { if (!v) return -1; INT res = 0; for (int i = 0; i < MAX_DIGIT; ++i) { if (v == v->prev->right) res |= INT(1)<<i; v = v->prev; } return res ^ lazy; } // find Node* whose value is val Node* find(INT val) { INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT-1; i >= 0; --i) { bool flag = (nval >> i) & 1; if (flag) v = v->right; else v = v->left; if (!v) return v; } return v; } // insert inline Node* emplace(Node *prev) { return new Node(prev); } void insert(INT val, size_t k = 1) { INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT-1; i >= 0; --i) { bool flag = (nval >> i) & 1; if (flag && !v->right) v->right = emplace(v); if (!flag && !v->left) v->left = emplace(v); if (flag) v = v->right; else v = v->left; } v->count += k; while ((v = v->prev)) v->count = get_count(v->left) + get_count(v->right); } // erase Node* clear(Node *v) { if (!v || get_count(v)) return v; delete(v); return nullptr; } bool erase(Node *v, size_t k = 1) { if (!v) return false; v->count -= k; while ((v = v->prev)) { v->left = clear(v->left); v->right = clear(v->right); v->count = get_count(v->left) + get_count(v->right); } return true; } bool erase(INT val) { auto v = find(val); return erase(v); } bool erase_k(INT val, size_t k = 1) { return erase(find(val), k); } // max (with xor-addition of val) and min (with xor-addition of val) Node* get_max(INT val = 0) { INT nval = val ^ lazy; Node* v = root; for (int i = MAX_DIGIT-1; i >= 0; --i) { bool flag = (nval >> i) & 1; if (!v->right) v = v->left; else if (!v->left) v = v->right; else if (flag) v = v->left; else v = v->right; } return v; } Node* get_min(INT val = 0) { return get_max(~val & ((INT(1)<<MAX_DIGIT)-1)); } // lower_bound, upper_bound Node* get_cur_node(Node *v, int i) { if (!v) return v; Node *left = v->left, *right = v->right; if ((lazy >> i) & 1) swap(left, right); if (left) return get_cur_node(left, i+1); else if (right) return get_cur_node(right, i+1); return v; } Node* get_next_node(Node *v, int i) { if (!v->prev) return nullptr; Node *left = v->prev->left, *right = v->prev->right; if ((lazy >> (i+1)) & 1) swap(left, right); if (v == left && right) return get_cur_node(right, i); else return get_next_node(v->prev, i+1); } Node* lower_bound(INT val) { INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT-1; i >= 0; --i) { bool flag = (nval >> i) & 1; if (flag && v->right) v = v->right; else if (!flag && v->left) v = v->left; else if ((val >> i) & 1) return get_next_node(v, i); else return get_cur_node(v, i); } return v; } Node* upper_bound(INT val) { return lower_bound(val + 1); } size_t order_of_val(INT val) { Node *v = root; size_t res = 0; for (int i = MAX_DIGIT-1; i >= 0; --i) { Node *left = v->left, *right = v->right; if ((lazy >> i) & 1) swap(left, right); bool flag = (val >> i) & 1; if (flag) { res += get_count(left); v = right; } else v = left; } return res; } // k-th, k is 0-indexed Node* get_kth(size_t k, INT val = 0) { Node *v = root; if (get_count(v) <= k) return nullptr; for (int i = MAX_DIGIT-1; i >= 0; --i) { bool flag = (lazy >> i) & 1; Node *left = (flag ? v->right : v->left); Node *right = (flag ? v->left : v->right); if (get_count(left) <= k) k -= get_count(left), v = right; else v = left; } return v; } // debug void print(Node *v, string prefix = "") { if (!v) return; cout << prefix << ": " << v->count << endl; print(v->left, prefix + "0"); print(v->right, prefix + "1"); } void print() { print(root); } vector<INT> eval(Node *v, int digit) const { vector<INT> res; if (!v) return res; if (!v->left && !v->right) { for (int i = 0; i < get_count(v); ++i) res.push_back(0); return res; } const auto& left = eval(v->left, digit-1); const auto& right = eval(v->right, digit-1); for (auto val : left) res.push_back(val); for (auto val : right) res.push_back(val + (INT(1)<<digit)); return res; } vector<INT> eval() const { auto res = eval(root, MAX_DIGIT-1); for (auto &val : res) val ^= lazy; return res; } friend ostream& operator << (ostream &os, const BinaryTrie<INT, MAX_DIGIT> &bt) { auto res = bt.eval(); for (auto val : res) os << val << " "; return os; } }; //https://drken1215.hatenablog.com/entry/2020/02/29/035900 //BinaryTrie<int,30> trie; //trie.root->count -> 集合のサイズ //trie.get_count(x) -> xの個数 //trie.xor_query(val) -> 全体にvalをxor //trie.get(v) -> 遅延伝搬のため,取り出す時は基本的にこれを使う //trie.find(x) -> xがあるか //trie.insert(x,k=1) -> xをk個挿入 //trie.erase(x) -> xを1個削除 //trie.erase_k(x,k=1) -> xをk個削除 //trie.get_max(val = 0) -> valとxorを取った時の最大値 //trie.get_min(val = 0) -> valとxorを取った時の最小値 //trie.get_kth(x) -> x番目(0-indexed)の値を取り出す. //trie.lower_bound(x) -> //trie.upper_bound(x) -> //trie.order_of_val(x) -> xが何番目か(0-indexed),xが集合にある場合のみ有効 //trie.get_kth(x) -> 0indexedでx番目の値、x個無いならnullptr(<-int型、!get_kth(val)は可能) int main(){ cin.tie(0); ios_base::sync_with_stdio(false); ll N, K, Q; cin >> N >> K >> Q; K--; BinaryTrie<ll, 60> trie; rep(_, N){ ll A; cin >> A; trie.insert(A); } while(Q--){ int f; cin >> f; if(f == 1){ ll x; cin >> x; trie.insert(x); } else if(f == 2){ ll y; cin >> y; ll v = trie.get(trie.get_kth(K)); trie.erase(v); trie.insert(v + y); } else{ cout << trie.get(trie.get_kth(K)) << "\n"; } } }