結果

問題 No.925 紲星 Extra
ユーザー QCFiumQCFium
提出日時 2019-11-09 10:09:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,656 ms / 10,000 ms
コード長 5,468 bytes
コンパイル時間 2,193 ms
コンパイル使用メモリ 187,168 KB
実行使用メモリ 94,808 KB
最終ジャッジ日時 2024-09-15 04:14:33
合計ジャッジ時間 28,680 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 AC 8 ms
5,376 KB
testcase_04 AC 10 ms
5,376 KB
testcase_05 AC 1,476 ms
72,504 KB
testcase_06 AC 1,486 ms
73,060 KB
testcase_07 AC 1,481 ms
72,564 KB
testcase_08 AC 1,490 ms
72,916 KB
testcase_09 AC 1,351 ms
73,112 KB
testcase_10 AC 1,491 ms
59,432 KB
testcase_11 AC 1,656 ms
85,804 KB
testcase_12 AC 1,418 ms
89,280 KB
testcase_13 AC 1,284 ms
72,464 KB
testcase_14 AC 1,428 ms
56,636 KB
testcase_15 AC 1,288 ms
73,028 KB
testcase_16 AC 1,652 ms
73,080 KB
testcase_17 AC 1,571 ms
53,156 KB
testcase_18 AC 1,624 ms
73,560 KB
testcase_19 AC 1,554 ms
52,184 KB
testcase_20 AC 1,541 ms
92,248 KB
testcase_21 AC 1,150 ms
94,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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->r);
			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 = (Node *) malloc(sizeof(Node) * MAX_NODE), *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;
}
0