結果
| 問題 |
No.2809 Sort Query
|
| コンテスト | |
| ユーザー |
 Tatsu_mr
|
| 提出日時 | 2024-08-06 01:37:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,890 bytes |
| コンパイル時間 | 4,761 ms |
| コンパイル使用メモリ | 267,108 KB |
| 最終ジャッジ日時 | 2025-02-23 21:06:01 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 WA * 6 RE * 27 TLE * 2 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using lint = long long;
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct Treap {
private:
unsigned int xorshift() {
static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned int t = (x ^ (x << 11));
x = y;
y = z;
z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
struct Node {
Node *left, *right;
S value;
int priority, size;
S sum;
F lazy;
int rev;
Node(S value_, int priority_) :
left(nullptr), right(nullptr), value(value_),
priority(priority_), size(1),
sum(value_), lazy(id()), rev(0) {}
};
Node *root = nullptr;
int cnt(Node *t) {
return t ? t->size : 0;
}
S get_sum(Node *t) {
return t ? t->sum : e();
}
void update(Node *t) {
if (t) {
t->size = cnt(t->left) + cnt(t->right) + 1;
t->sum = op(op(get_sum(t->left), t->value), get_sum(t->right));
}
}
void push(Node *t) {
if (t && t->rev) {
t->rev = false;
swap(t->left, t->right);
if (t->left) {
t->left->rev ^= 1;
}
if (t->right) {
t->right->rev ^= 1;
}
}
all_apply(t->left, t->lazy);
all_apply(t->right, t->lazy);
t->lazy = id();
}
Node *merge(Node *lroot, Node *rroot) {
if (!lroot || !rroot) {
return lroot ? lroot : rroot;
} else if (lroot->priority > rroot->priority) {
push(lroot);
lroot->right = merge(lroot->right, rroot);
update(lroot);
return lroot;
} else {
push(rroot);
rroot->left = merge(lroot, rroot->left);
update(rroot);
return rroot;
}
}
pair<Node *, Node *> split(Node *t, int k) {
if (!t) {
return {nullptr, nullptr};
}
push(t);
if (k <= cnt(t->left)) {
auto [lroot, rroot] = split(t->left, k);
t->left = rroot;
update(t);
return {lroot, t};
} else {
auto [lroot, rroot] = split(t->right, k - cnt(t->left) - 1);
t->right = lroot;
update(t);
return {t, rroot};
}
}
void all_apply(Node *t, F f) {
if (!t) {
return;
}
t->value = mapping(f, t->value);
t->sum = mapping(f, t->sum);
t->lazy = composition(f, t->lazy);
}
void dump(Node *t) {
if (!t) {
return;
}
push(t);
dump(t->left);
cout << t->value << " ";
dump(t->right);
}
public:
Treap() {}
Treap(vector<S> v) {
std::reverse(v.begin(), v.end());
for (S &x : v) {
insert(0, x);
}
}
Treap(int n) {
for (int i = 0; i < n; i++) {
insert(0, e());
}
}
void set(int p, S x) {
assert(0 <= p && p < cnt(root));
erase(p);
insert(p, x);
}
void insert(int p, S x) {
assert(0 <= p && p <= cnt(root));
auto [lroot, rroot] = split(root, p);
root = merge(merge(lroot, new Node(x, xorshift())), rroot);
}
void erase(int p) {
assert(0 <= p && p < cnt(root));
auto [Lroot, rroot] = split(root, p + 1);
auto [lroot, mroot] = split(Lroot, p);
root = merge(lroot, rroot);
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= cnt(root));
if (l == r) {
return e();
}
auto [Lroot, rroot] = split(root, r);
auto [lroot, mroot] = split(Lroot, l);
S res = mroot->sum;
root = merge(merge(lroot, mroot), rroot);
return res;
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= cnt(root));
if (l == r) {
return;
}
auto [Lroot, rroot] = split(root, r);
auto [lroot, mroot] = split(Lroot, l);
all_apply(mroot, f);
root = merge(merge(lroot, mroot), rroot);
}
void reverse(int l, int r) {
assert(0 <= l && l <= r && r <= cnt(root));
if (l == r) {
return;
}
auto [Lroot, rroot] = split(root, r);
auto [lroot, mroot] = split(Lroot, l);
mroot->rev ^= 1;
push(mroot);
root = merge(merge(lroot, mroot), rroot);
}
void rotate(int l, int r, int m) {
assert(0 <= l && l <= r && r <= cnt(root));
assert(l <= m && m < r);
reverse(l, r);
reverse(l, l + r - m);
reverse(l + r - m, r);
}
S operator[](int p) {
assert(0 <= p && p < cnt(root));
return prod(p, p + 1);
}
int size() {
return cnt(root);
}
void dump() {
dump(root);
cout << endl;
}
};
template <class T>
struct Compression {
vector<T> a;
Compression(vector<T> a_) : a(a_) {
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
int size() {
return (int)a.size();
}
T val(int p) {
return a[p];
}
int idx(T x) {
int res = lower_bound(a.begin(), a.end(), x) - a.begin();
return res;
}
};
lint op(lint a, lint b) { return a + b; }
lint e() { return 0LL; }
int main() {
int n, q;
cin >> n >> q;
vector<long long> a(n), d;
for (int i = 0; i < n; i++) {
cin >> a[i];
d.emplace_back(a[i]);
}
vector<vector<long long>> qs(q);
for (int i = 0; i < q; i++) {
int type;
cin >> type;
if (type == 1) {
int k;
long long x;
cin >> k >> x;
k--;
qs[i] = {type, k, x};
d.emplace_back(x);
} else if (type == 2) {
qs[i] = {type};
} else {
int k;
cin >> k;
k--;
qs[i] = {type, k};
}
}
Compression c(d);
Treap<lint, op, e, lint, op, op, e> tr(a);
fenwick_tree<int> fw(c.size());
for (int i = 0; i < n; i++) {
fw.add(c.idx(a[i]), 1);
}
bool sorted = false;
queue<pair<int, long long>> wait;
vector<long long> b(n, -1);
auto getidx = [&](int k) -> int {
if (fw.sum(0, 1) > k) {
return 0;
}
int l = 0, r = (int)c.size() - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (fw.sum(0, mid + 1) > k) {
r = mid;
} else {
l = mid;
}
}
return r;
};
for (int i = 0; i < q; i++) {
int type = qs[i][0];
if (type == 1) {
int k = qs[i][1];
long long x = qs[i][2];
wait.push({k, x});
b[k] = x;
sorted = false;
} else if (type == 2) {
while (!wait.empty()) {
auto [k, x] = wait.front();
wait.pop();
b[k] = -1;
int id = getidx(k);
long long px = tr[id];
tr.set(id, x);
fw.add(c.idx(px), -1);
fw.add(c.idx(x), 1);
}
sorted = true;
} else {
int k = qs[i][1];
if (sorted) {
int id = getidx(k);
cout << c.val(id) << endl;
} else {
cout << (b[k] == -1 ? tr[k] : b[k]) << endl;
}
}
}
}