結果
| 問題 | No.925 紲星 Extra |
| ユーザー |
 QCFium
|
| 提出日時 | 2019-11-09 09:53:16 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,436 bytes |
| コンパイル時間 | 2,621 ms |
| コンパイル使用メモリ | 197,588 KB |
| 実行使用メモリ | 814,976 KB |
| 最終ジャッジ日時 | 2024-09-15 04:12:05 |
| 合計ジャッジ時間 | 4,798 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | MLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
ソースコード
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
#define MAX_NODE (1 << 22)
struct AVL {
struct Node {
Node *l;
Node *r;
int64_t val;
int64_t sum;
int size;
int height;
Node *fetch() {
size = 1 + l->size + r->size;
height = 1 + std::max(l->height, r->height);
sum = val + l->sum + r->sum;
return this;
}
Node *rotate_l() {
Node *new_root = r;
r = new_root->l;
new_root->l = this;
return fetch(), new_root->fetch();
}
Node *rotate_r() {
Node *new_root = l;
l = new_root->r;
new_root->r = this;
return fetch(), new_root->fetch();
}
int height_diff() { return l->height - r->height; }
Node *balance() {
int dif = height_diff();
if (dif == 2) {
if (l->height_diff() < 0) l = l->rotate_l();
return rotate_r();
} else if (dif == -2) {
if (r->height_diff() > 0) r = r->rotate_r();
return rotate_l();
} else return fetch();
}
};
static Node nodes[], *NONE, *removed_tmp;
static int head;
Node *root = NONE;
AVL() {
if (!head) nodes[head++] = {NONE, NONE, 0, 0, 0, 0};
}
private :
static Node *insert(Node *node, int64_t val) {
if (node == NONE) return &(nodes[head++] = {NONE, NONE, val, val, 1, 1});
if (val <= node->val) node->l = insert(node->l, val);
else node->r = insert(node->r, val);
return node->balance();
}
static Node *remove_rightest(Node *node) {
if (node->r != NONE) {
node->r = remove_rightest(node);
return node->balance();
} else return (removed_tmp = node)->l;
}
static Node *remove(Node *node, int64_t val) {
if (val < node->val) node->l = remove(node->l, val);
else if (val > node->val) node->r = remove(node->r, val);
else {
if (node->l == NONE) return node->r;
node->l = remove_rightest(node->l);
removed_tmp->l = node->l;
removed_tmp->r = node->r;
return removed_tmp->balance();
}
return node->balance();
}
static Node *construct(const int64_t *start, const int64_t *end) {
int mid = (end - start) >> 1;
Node *l = mid ? construct(start, start + mid) : NONE;
Node *r = start + mid + 1 < end ? construct(start + mid + 1, end) : NONE;
return (nodes[head++] = {l, r, start[mid], start[mid], 1, 1}).fetch();
}
public :
void insert(int64_t val) { root = insert(root, val); }
void remove(int64_t val) { root = remove(root, val); }
int64_t operator [] (int i) {
for (Node *cur = root; ; ) {
int lsize = cur->l->size;
if (i < lsize) cur = cur->l;
else if (i > lsize) cur = cur->r, i -= lsize + 1;
else return cur->val;
}
}
void build(const int64_t *start, const int64_t *end) {
std::vector<int64_t> a(start, end);
std::sort(a.begin(), a.end());
root = construct(&a[0], &a[0] + a.size());
}
int size() { return root->size; }
int lower_count(int64_t n) {
int res = 0;
for (Node *cur = root; cur != NONE; ) {
if (n < cur->val) cur = cur->l;
else res += cur->l->size + 1, cur = cur->r;
}
return res;
}
int64_t sum() { return root->sum; }
int64_t sum(int64_t upper) {
int64_t res = 0;
for (Node *cur = root; cur != NONE; ) {
if (upper < cur->val) cur = cur->l;
else res += cur->l->sum + cur->val, cur = cur->r;
}
return res;
}
};
AVL::Node AVL::nodes[MAX_NODE + 1], *AVL::NONE = nodes, *AVL::removed_tmp;
int AVL::head = 0;
unsigned int msb(unsigned int n) {
n = n | n >> 1;
n = n | n >> 2;
n = n | n >> 4;
n = n | n >> 8;
n = n | n >> 16;
return n ^ n >> 1;
}
struct SegTree {
int n;
std::vector<AVL> data;
std::vector<int64_t> a;
SegTree (const std::vector<int64_t> &a) {
this->a = a;
for (n = 1; n < (int) a.size(); n <<= 1);
data.resize(n << 1);
for (int i = 0; i < (int) a.size(); i++) data[i + n].insert(a[i]);
for (int i = 2 * n - 1; i; i--) {
int heighest = (31 - __builtin_clz(i));
int one = n >> heighest;
int start = one * (i ^ 1 << heighest);
int end = std::min<int>(a.size(), start + one);
if (end > start) data[i].build(&a[start], &a[0] + end);
}
}
int64_t calc(int l, int r) {
std::vector<AVL *> trees;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (r & 1) trees.push_back(&data[--r]);
if (l & 1) trees.push_back(&data[l++]);
}
int all = 0;
for (auto i : trees) all += i->size();
int64_t ll = -1, rr = 1LL << 40;
while (rr - ll > 1) {
int64_t m = ll + ((rr - ll) >> 1);
int cnt = 0;
for (auto j : trees) cnt += j->lower_count(m);
if (cnt <= all / 2) ll = m;
else rr = m;
}
int64_t res = 0;
for (auto i : trees) {
int64_t low = i->sum(rr);
int lsize = i->lower_count(rr);
int64_t high = i->sum() - low;
int hsize = i->size() - lsize;
res += lsize * rr - low + high - hsize * rr;
}
return res;
}
void assign(int i, int64_t val) {
int i_ = i;
for (i += n; i; i >>= 1) {
data[i].remove(a[i_]);
data[i].insert(val);
}
a[i_] = val;
}
};
int main() {
int n = ri();
assert(n < 1 << 16);
int q = ri();
std::vector<int64_t> a(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
SegTree tree(a);
int64_t xored = 0;
for (int i = 0; i < q; i++) {
int t = ri();
if (t == 1) {
int index = (ri() ^ (xored & 0xFFFF)) - 1;
int64_t val;
std::cin >> val;
val ^= (xored & 0xFFFFFFFFFF);
tree.assign(index, val);
} else {
int l = ri() ^ (xored & 0xFFFF);
int r = ri() ^ (xored & 0xFFFF);
if (r < l) std::swap(l, r);
l--;
int64_t res = tree.calc(l, r);
xored ^= res;
std::cout << res << std::endl;
}
}
return 0;
}