#397133 (C++14) No.925 紲星 Extra

• 問題: No.925 紲星 Extra
• ユーザー: QCFium
• 提出日時: 2019-11-09 10:09:15
• 言語: C++14 (gcc 13.3.0 + boost 1.87.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

ファイルパターン	結果
sample	AC * 3
other	AC * 19

ソースコード

#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;
}