結果
| 問題 | No.2809 Sort Query |
| ユーザー |
 Pres1dent
|
| 提出日時 | 2024-07-14 21:44:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,800 ms / 2,000 ms |
| コード長 | 9,132 bytes |
| コンパイル時間 | 8,249 ms |
| コンパイル使用メモリ | 311,560 KB |
| 最終ジャッジ日時 | 2025-02-22 06:57:17 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 71 |
ソースコード
#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using ll = long long;using lll = __int128;using i64 = long long;using i128 = __int128;constexpr int INF = numeric_limits<int>::max();constexpr ll LNF= numeric_limits<ll>::max();using ull = unsigned long long;using ld = long double;using i_i = pair<int, int>;using l_l = pair<ll, ll>;using d_d = pair<double, double>;using s_s = pair<string, string>;using i_i_i = tuple<int, int, int>;using i_i_i_i = tuple<int, int, int, int>;using i_i_i_i_i = tuple<int, int, int, int, int>;using l_l_l = tuple<ll, ll, ll>;using l_l_l_l = tuple<ll, ll, ll, ll>;using l_l_l_l_l = tuple<ll, ll, ll, ll, ll>;using _bool = int;#define rep2(i, m, n) for (ll i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (ll i = (n)-1; i >= (m); --i)#define drep(i, n) drep2(i, 0, n)#define ifbit(n,k) ((n>>k)&1) //if kth bit of n is on then true (sitakara, 0-indexed)#define zpad(i) cout << setfill('0') << setw(i)#define dout cout << fixed << setprecision(10)#define douts(i) cout << fixed << setprecision(i) << scientific#define pcnt __builtin_popcountlltemplate <class T, class U> bool chmax(T &l, const U &r) { if (l < r) { l = r; return true; } return false; }template <class T, class U> bool chmin(T &l, const U &r) { if (l > r) { l = r; return true; } return false; }template <class T> pair<int, bool> ub(const vector<T> &v, const T &key) { int ind = upper_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); }template <class T> pair<int, bool> rub(const vector<T> &v, const T &key) { int ind = upper_bound(v.rbegin(), v.rend(), key, [](const T & l, const T &r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }template <class T> pair<int, bool> lb(const vector<T> &v, const T &key) { int ind = lower_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); }template <class T> pair<int, bool> rlb(const vector<T> &v, const T &key) { int ind = lower_bound(v.rbegin(), v.rend(), key, [](const T & l, const T &r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }vector<int> di = { -1, 0, 1, 0 };vector<int> dj = { 0, 1, 0, -1 };ll my_pow(ll a, int x) { assert(x >= 0); ll ret = 1; rep(i, x) { assert(LNF / x > a); ret *= a; } return ret; }using ll = long long;// .insert(value) ok// - split// - merge// .exist(value) ok// .erase(value) ok// .dump ok// .size() ok// .at(index) i the element ok// .upper_bound(value) ok// .lower_bound(value) ok// for (auto : treap)template <class T> struct Treap {private:struct Node {T key;int pri, sz;Node *l, *r;Node(T k, int p) : key(k), pri(p), l(nullptr), r(nullptr) {}} *root = nullptr;int size(Node *t) const {return (t ? t->sz : 0);}void update(Node *&t) {if (!t) return;t->sz = size(t->l) + size(t->r) + 1;}// l (key より小さい), r (keyより大きい)void split(Node *&t, T key, Node *&l, Node *&r) {// cerr << "split cur (t) " << (t ? t->key : -1) << endl;if (!t) {// cerr << "ぬるぽ" << endl;l = r = nullptr;} else if (key < t->key) {// cerr << "address (t, t->l) " << t << " " << t->l << endl;r = t;// cerr << "address (t->l, r->l) " << t->l << " " << r->l << endl;split(t->l, key, l, r->l);} else {// cerr << "split 1 (t) " << (t ? t->key : -1) << endl;l = t;// cerr << "address (t, l->r, r) " << t << " " << l->r << " " << r << endl;split(t->r, key, l->r, r);// cerr << "address (t, l->r, r) " << t << " " << l->r << " " << r << " ";// if (t) cerr << t->r;// else cerr << "ぬるぽ";// cerr << endl;// cerr << "split 2 (t) " << (t ? t->key : -1) << endl;// cerr << "split 3 (t) " << (t ? t->key : -1) << endl;// assert(false);}// cerr << "split end (t) " << (t ? t->key : -1) << endl;// cerr << "split end (l, r) " << (l ? l->key : -1) << " " << (r ? r->key : -1) << endl;update(l), update(r);}void insert(Node *&t, Node *v) {if (t == root) {// cerr << "insert " << v->key << endl;}if (!t) {t = v;} else if (v->pri < t->pri) {insert(v->key < t->key ? t->l : t->r, v);} else {split(t, v->key, v->l, v->r);t = v;}update(t);}void merge(Node *&t, Node *l, Node *r) {if (!l or !r) {t = (l ? l : r);} else if (l->pri < r->pri) {t = r;merge(t->l, l, r->l);} else {t = l;merge(t->r, l->r, r);}update(t);}void erase(Node *&t, T key) {if (!t) return;if (t->key == key) {merge(t, t->l, t->r);} else {erase(key < t->key ? t->l : t->r, key);}update(t);}bool exist(Node *&t, T key) const {if (!t) {return false;} else if (t->key == key) {return true;} else if (key < t->key) {return exist(t->l, key);} else {return exist(t->r, key);}}void all(Node *t, vector<T>& ret) const {if (!t) return;all(t->l, ret);ret.emplace_back(t->key);all(t->r, ret);}T split2(Node *t, int ind) {if (!t) assert(0 && "couln't find by index");int t_ind = size(t->l);// cerr << "split2 " << t->key << " " << ind << endl;if (ind == t_ind) {return t->key;} else if (ind < t_ind) {return split2(t->l, ind);} else {return split2(t->r, ind - t_ind - 1);}update(t);}public:explicit Treap(void) : Treap(vector<T>()) {}explicit Treap(vector<T> v) {for (T e : v) {insert(e);}}void insert(T key) {insert(root, new Node(key, rand()));}void erase(T key) {erase(root, key);}bool exist(T key) {return exist(root, key);}vector<T> all(void) {vector<T> ret;all(root, ret);return ret;}int size(void) {return size(root);}T at(int ind) {assert(0 <= ind and ind < size());return split2(root, ind);}void dump(void) {int d = 0;vector<vector<T>> debug;auto rec = [&](auto&& self, Node *v) -> void {if (d == debug.size()) debug.push_back({});if (!v) {debug[d].push_back(-1);return;}debug[d].push_back(v->key);d++;self(self, v->l);self(self, v->r);d--;};rec(rec, root);int sum = 0;for (auto v : debug) {int cnt = 0;int sz = 0;for (auto e : v) {if (e != -1) {sz += 1;sum++;}}// cerr << "size " << sz << " ";for (auto e : v) {// cerr << e << " ";}// cerr << endl;}// cerr << "sum " << sum << endl;}};int main() {// void solve () {int n, q; cin >> n >> q;vector<ll> A(n); rep(i, n) { cin >> A[i]; }Treap<ll> t;int cnt = 0;map<int, ll> mp;rep(i, n) mp[i] = A[i];bool first = true;rep(i, q) {// cerr << t.size() << endl;int op; cin >> op;// cerr << i << " " << op << endl;if (op == 1) {ll k, x; cin >> k >> x;k--;mp[k] = x;} else if (op == 2) {if (first) {for (auto [k, v] : mp) {A[k] = v;}t = Treap(A);first = false;mp = {};} else {vector<ll> tmp;for (auto [k, v] : mp) {auto res = t.at(k);tmp.push_back(t.at(k));}for (auto e : tmp) {assert(t.exist(e));t.erase(e);}for (auto [k, v] : mp) {t.insert(v);}mp = {};}} else {int k; cin >> k;k--;if (mp.find(k) == mp.end()) {cout << t.at(k) << endl;} else {cout << mp[k] << endl;}}}}// int main() {// Treap<int> t;// t.insert(3);// t.insert(3);// t.insert(4);// t.insert(5);// t.insert(5);// t.insert(7);// t.insert(0);// int n = 10;// for (int i = 0; i < n; i++) {// cerr << t.exist(i) << " ";// }// cerr << endl;// for (auto e : t.all()) {// cerr << e << " ";// }// cerr << endl;// cerr << "size " << t.size() << endl;// t.erase(5);// t.erase(4);// for (int i = 0; i < n; i++) {// cerr << t.exist(i) << " ";// }// cerr << endl;// cerr << "size " << t.size() << endl;// cerr << "DUMP" << endl;// t.dump();// cerr << "DUMP" << endl;// for (auto e : t.all()) {// cerr << e << " ";// }// cerr << endl;// cerr << t.size() << endl;// cerr << "at test" << endl;// for (int i = 0; i < 6; i++) {// auto res = t.at(i);// cerr << "at " << res << endl;// }// cerr << endl;// }//