結果
問題 | No.925 紲星 Extra |
ユーザー | akakimidori |
提出日時 | 2020-02-19 20:41:56 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 3,992 ms / 10,000 ms |
コード長 | 8,143 bytes |
コンパイル時間 | 16,323 ms |
コンパイル使用メモリ | 400,364 KB |
実行使用メモリ | 76,288 KB |
最終ジャッジ日時 | 2024-10-08 18:15:27 |
合計ジャッジ時間 | 68,538 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,820 KB |
testcase_03 | AC | 10 ms
6,820 KB |
testcase_04 | AC | 10 ms
6,820 KB |
testcase_05 | AC | 3,127 ms
75,008 KB |
testcase_06 | AC | 3,196 ms
75,776 KB |
testcase_07 | AC | 3,169 ms
75,264 KB |
testcase_08 | AC | 3,404 ms
75,648 KB |
testcase_09 | AC | 3,197 ms
75,648 KB |
testcase_10 | AC | 3,479 ms
74,752 KB |
testcase_11 | AC | 2,996 ms
75,904 KB |
testcase_12 | AC | 2,820 ms
75,392 KB |
testcase_13 | AC | 2,538 ms
75,136 KB |
testcase_14 | AC | 3,201 ms
74,880 KB |
testcase_15 | AC | 2,276 ms
75,648 KB |
testcase_16 | AC | 3,545 ms
75,392 KB |
testcase_17 | AC | 3,738 ms
74,624 KB |
testcase_18 | AC | 3,393 ms
76,032 KB |
testcase_19 | AC | 3,992 ms
75,776 KB |
testcase_20 | AC | 2,747 ms
76,160 KB |
testcase_21 | AC | 1,645 ms
76,288 KB |
ソースコード
type Link = Option<Box<Node>>;struct Node {val: u64,sum: u64,size: usize,rank: usize,left: Link,right: Link,}fn get_size(node: &Link) -> usize {node.as_ref().map_or(0, |t| t.get_size())}fn get_sum(node: &Link) -> u64 {node.as_ref().map_or(0, |t| t.get_sum())}fn get_rank(node: &Link) -> usize {node.as_ref().map_or(0, |t| t.get_rank())}fn insert(node: &mut Link, val: u64) {if node.is_none() {*node = Some(Box::new(Node {val: val,sum: val,size: 1,rank: 1,left: None,right: None,}));return;}let node = node.as_mut().unwrap();if node.val <= val {insert(&mut node.right, val);} else {insert(&mut node.left, val);}node.update();node.balance();}fn merge(l: Link, r: Link) -> Link {if l.is_none() {return r;}if r.is_none() {return l;}let l_size = get_size(&l);let r_size = get_size(&r);if l_size >= r_size {let mut l = l.unwrap();l.right = merge(l.right.take(), r);l.update();l.balance();Some(l)} else {let mut r = r.unwrap();r.left = merge(l, r.left.take());r.update();r.balance();Some(r)}}fn remove(node: &mut Link, val: u64) {assert!(node.is_some());let t = node.as_mut().unwrap();if t.val == val {let l = t.left.take();let r = t.right.take();*node = merge(l, r);} else if t.val < val {remove(&mut t.right, val);t.update();t.balance();} else {remove(&mut t.left, val);t.update();t.balance();}}// x >= val となるnodeの数, xの和fn eval(node: &Link, val: u64) -> (usize, u64) {if node.is_none() {return (0, 0);}let node = node.as_ref().unwrap();if node.val >= val {let size = get_size(&node.right);let sum = get_sum(&node.right);let res = eval(&node.left, val);(res.0 + size + 1, res.1 + sum + node.val)} else {eval(&node.right, val)}}#[allow(dead_code)]fn walk(node: &Link) {if node.is_none() {return;}let node = node.as_ref().unwrap();walk(&node.left);print!("{} ", node.val);walk(&node.right);}impl Node {fn get_size(&self) -> usize {self.size}fn get_sum(&self) -> u64 {self.sum}fn get_rank(&self) -> usize {self.rank}fn update(&mut self) {self.size = 1 + get_size(&self.left) + get_size(&self.right);self.sum = self.val + get_sum(&self.left) + get_sum(&self.right);self.rank = std::cmp::max(get_rank(&self.left), get_rank(&self.right)) + 1;}fn rotate_left(&mut self) {let mut r = self.right.take().unwrap();self.right = r.left.take();self.update();std::mem::swap(self, &mut r);self.left = Some(r);self.update();}fn rotate_right(&mut self) {let mut l = self.left.take().unwrap();self.left = l.right.take();self.update();std::mem::swap(self, &mut l);self.right = Some(l);self.update();}fn get_bias(&self, b: usize) -> i32 {let l_size = get_rank(&self.left);let r_size = get_rank(&self.right);match (l_size <= b + r_size, b + l_size >= r_size) {(true, true) => 0,(false, _) => 1,(_, false) => -1,}}fn balance(&mut self) {let c = self.get_bias(1);if c == 0 {return;}if c == 1 {let l = self.left.as_mut().unwrap();if l.get_bias(0) == -1 {l.rotate_left();}self.rotate_right();} else {let r = self.right.as_mut().unwrap();if r.get_bias(0) == 1 {r.rotate_right();}self.rotate_left();}}}use std::io::Write;use std::io::Read;fn run() {let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace();let n: usize = it.next().unwrap().parse().unwrap();let q: usize = it.next().unwrap().parse().unwrap();let mut a: Vec<u64> = (0..n).map(|_| it.next().unwrap().parse().unwrap()).collect();let size = n.next_power_of_two();let mut tree: Vec<_> = (0..(2 * size)).map(|_| None).collect();for (i, &a) in a.iter().enumerate() {let mut x = i + size;while x > 0 {insert(&mut tree[x], a);x >>= 1;}}let mut sum = vec![0; 2 * size];for (sum, a) in sum[size..].iter_mut().zip(a.iter()) {*sum = *a;}for i in (1..size).rev() {sum[i] = sum[2 * i] + sum[2 * i + 1];}let mut xor = 0u64;let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());for _ in 0..q {let op: usize = it.next().unwrap().parse().unwrap();if op == 1 {let x: usize = it.next().unwrap().parse().unwrap();let x = ((x ^ (xor as usize)) & ((1 << 16) - 1)) - 1;let y: u64 = it.next().unwrap().parse().unwrap();let y = (y ^ xor) & ((1u64 << 40) - 1);let val = a[x];a[x] = y;let mut k = x + size;while k > 0 {remove(&mut tree[k], val);insert(&mut tree[k], y);k >>= 1;}let mut k = x + size;sum[k] = y;k >>= 1;while k > 0 {sum[k] = sum[2 * k] + sum[2 * k + 1];k >>= 1;}} else {let l: usize = it.next().unwrap().parse().unwrap();let mut l = (l ^ (xor as usize)) & ((1 << 16) - 1);let r: usize = it.next().unwrap().parse().unwrap();let mut r = (r ^ (xor as usize)) & ((1 << 16) - 1);if l > r {std::mem::swap(&mut l, &mut r);}l -= 1;let add = |a: (usize, u64), b: (usize, u64)| (a.0 + b.0, a.1 + b.1);let find = |val: u64| -> (usize, u64) {let mut x = l + size;let mut y = r + size;let mut ans = (0, 0);while x < y {if x & 1 == 1 {ans = add(ans, eval(&tree[x], val));x += 1;}if y & 1 == 1 {y -= 1;ans = add(ans, eval(&tree[y], val));}x >>= 1;y >>= 1;}ans};let len = r - l;let mid = (len + 1) / 2;let mut ok = 0;let mut ng = 1u64 << 40;while ng - ok > 1 {let m = (ok + ng) / 2;if find(m).0 >= mid {ok = m;} else {ng = m;}}let res = find(ok);let mut total = 0;let mut x = l + size;let mut y = r + size;while x < y {if x & 1 == 1 {total += sum[x];x += 1;}if y & 1 == 1 {y -= 1;total += sum[y];}x >>= 1;y >>= 1;}let len = len as u64;let mid = mid as u64;let res = (res.0 as u64, res.1);let mut ans = 0;ans += res.1 - mid * ok - ok * (res.0 - mid);ans += ok * (len - mid) - (total - res.1 + ok * (res.0 - mid));writeln!(out, "{}", ans).ok();xor ^= ans;}}}fn main() {run();}