#1149702 (Rust) No.3530 「」

• 問題: No.3530 「」
• ユーザー: aa36
• 提出日時: 2026-02-27 23:40:43
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 565 ms / 3,000 ms
• コード長: 7,300 bytes
• コンパイル時間: 14,120 ms
• コンパイル使用メモリ: 213,304 KB
• 実行使用メモリ: 22,280 KB
• 最終ジャッジ日時: 2026-05-04 20:51:37
• 合計ジャッジ時間: 22,758 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 27

コンパイルメッセージ

warning: variable does not need to be mutable
  --> src/main.rs:17:18
   |
17 |     fn pow(self, mut e: i64) -> Self {
   |                  ----^
   |                  |
   |                  help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` (part of `#[warn(unused)]`) on by default

warning: field `n` is never read
  --> src/main.rs:98:5
   |
97 | struct LazySegTree {
   |        ----------- field in this struct
98 |     n: usize,
   |     ^
   |
   = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: variable `X` should have a snake case name
   --> src/main.rs:194:13
    |
194 |     let mut X = vec![0i64; n];
    |             ^ help: convert the identifier to snake case (notice the capitalization): `x`
    |
    = note: `#[warn(non_snake_case)]` (part of `#[warn(nonstandard_style)]`) on by default

warning: variable `Y` should have a snake case name
   --> src/main.rs:195:13
    |
195 |     let mut Y = vec![0i64; n];
    |             ^ help: convert the identifier to snake case (notice the capitalization): `y`

warning: variable `zX` should have a snake case name
   --> src/main.rs:210:13
    |
210 |     let mut zX = X.clone();
    |             ^^ help: convert the identifier to snake case: `z_x`

warning: variable `zY` should have a snake case name
   --> src/main.rs:211:13
    |
211 |     let mut zY = Y.clone();
    |             ^^ help: convert the identifier to snake case: `z_y`

warning: variable `rX` should have a snake case name
   --> src/main.rs:215:13
    |
215 |     let mut rX = vec![0usize; n];
    |             ^^ help: convert the identifier to snake case: `r_x`

warning: variable `rY` should have a snake case name
   --> src/main.rs:216:13
    |
216 |     let mut rY = vec![0usize; n];
    |             ^^ help: convert the identifier to snake case: `r_y`

warning: variable `G` should have a snake case name
   --> src/main.rs:230:17
    |
230 |         let mut G: Vec<Vec<usize>> = vec![Vec::new(); zX.len(

ソースコード

use std::io::{self, Read};

const MOD: i64 = 998244353;

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
struct Mint(i64);

impl Mint {
    fn new<T: Into<i128>>(v: T) -> Self {
        let mut x = v.into() % (MOD as i128);
        if x < 0 { x += MOD as i128; }
        Mint(x as i64)
    }
    fn zero() -> Self { Mint(0) }
    fn one() -> Self { Mint(1) }
    fn val(self) -> i64 { self.0 }
    fn pow(self, mut e: i64) -> Self {
        let mut base = self.0 as i128;
        let mut ex = e as i128;
        let mut res: i128 = 1;
        while ex > 0 {
            if (ex & 1) == 1 { res = (res * base) % (MOD as i128); }
            base = (base * base) % (MOD as i128);
            ex >>= 1;
        }
        Mint::new(res)
    }
    fn inv(self) -> Self {
        self.pow(MOD - 2)
    }
}

use std::ops::{Add, Sub, Mul, Div, AddAssign, MulAssign, SubAssign};

impl Add for Mint {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        let mut x = self.0 + rhs.0;
        if x >= MOD { x -= MOD; }
        Mint(x)
    }
}
impl Sub for Mint {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        let mut x = self.0 - rhs.0;
        if x < 0 { x += MOD; }
        Mint(x)
    }
}
impl Mul for Mint {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        Mint::new((self.0 as i128) * (rhs.0 as i128))
    }
}
impl Div for Mint {
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.inv()
    }
}
impl AddAssign for Mint {
    fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; }
}
impl SubAssign for Mint {
    fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; }
}
impl MulAssign for Mint {
    fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; }
}

#[derive(Copy, Clone, Debug)]
struct S {
    first: Mint,
    second: Mint,
}

fn op(a: S, b: S) -> S {
    let one = Mint::one();
    let term_a = a.first * (one - a.second);
    let term_b = b.first * (one - b.second);
    S { first: term_a + term_b, second: Mint::zero() }
}
fn e() -> S {
    S { first: Mint::one(), second: Mint::one() }
}
fn mapping(f: Mint, mut x: S) -> S {
    x.first *= f;
    x
}
fn composition(f: Mint, g: Mint) -> Mint {
    f * g
}
fn id() -> Mint { Mint::one() }

struct LazySegTree {
    n: usize,
    size: usize,
    data: Vec<S>,
    lazy: Vec<Mint>, // lazy[0] unused, indices 1..size-1 used
}

impl LazySegTree {
    fn new(v: &Vec<S>) -> Self {
        let n = v.len();
        let mut size = 1usize;
        while size < n { size <<= 1; }
        let mut data = vec![e(); 2 * size];
        for i in 0..n { data[size + i] = v[i]; }
        for i in (1..size).rev() {
            data[i] = op(data[i << 1], data[i << 1 | 1]);
        }
        let lazy = vec![id(); size]; // indices 0..size-1
        LazySegTree { n, size, data, lazy }
    }

    fn apply_node(&mut self, idx: usize, f: Mint) {
        self.data[idx] = mapping(f, self.data[idx]);
        if idx < self.size {
            self.lazy[idx] = composition(f, self.lazy[idx]);
        }
    }

    fn push(&mut self, idx: usize) {
        let f = self.lazy[idx];
        if f != id() {
            self.apply_node(idx << 1, f);
            self.apply_node(idx << 1 | 1, f);
            self.lazy[idx] = id();
        }
    }

    fn update_upward(&mut self, mut idx: usize) {
        while idx > 1 {
            idx >>= 1;
            self.data[idx] = op(self.data[idx << 1], self.data[idx << 1 | 1]);
        }
    }

    fn apply_range_rec(&mut self, idx: usize, l: usize, r: usize, ql: usize, qr: usize, f: Mint) {
        if ql >= r || qr <= l { return; }
        if ql <= l && r <= qr {
            self.apply_node(idx, f);
            return;
        }
        self.push(idx);
        let mid = (l + r) >> 1;
        self.apply_range_rec(idx << 1, l, mid, ql, qr, f);
        self.apply_range_rec(idx << 1 | 1, mid, r, ql, qr, f);
        self.data[idx] = op(self.data[idx << 1], self.data[idx << 1 | 1]);
    }

    fn apply_range(&mut self, l: usize, r: usize, f: Mint) {
        if l >= r { return; }
        self.apply_range_rec(1, 0, self.size, l, r, f);
    }

    fn set(&mut self, pos: usize, val: S) {
        let idx = self.size + pos;
        // push lazies from top to leaf
        let mut path = Vec::new();
        let mut i = idx;
        while i > 1 { i >>= 1; path.push(i); }
        for &p in path.iter().rev() { self.push(p); }
        self.data[idx] = val;
        self.update_upward(idx);
    }

    fn get(&mut self, pos: usize) -> S {
        let idx = self.size + pos;
        let mut path = Vec::new();
        let mut i = idx;
        while i > 1 { i >>= 1; path.push(i); }
        for &p in path.iter().rev() { self.push(p); }
        self.data[idx]
    }

    fn all_prod(&self) -> S {
        self.data[1]
    }
}

fn parse_input() -> Vec<i64> {
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse::<i64>().unwrap()).collect()
}

fn main() {
    let inp = parse_input();
    let mut idx = 0usize;
    let n = inp[idx] as usize; idx += 1;
    let mut X = vec![0i64; n];
    let mut Y = vec![0i64; n];
    // IMPORTANT: read pairs (X[i], Y[i]) in sequence, same as original C++
    for i in 0..n {
        X[i] = inp[idx]; idx += 1;
        Y[i] = inp[idx]; idx += 1;
    }

    if n == 0 {
        println!("0");
        return;
    }

    let f34 = Mint::new(3) / Mint::new(4);
    let f43 = Mint::one() / f34;

    let mut zX = X.clone();
    let mut zY = Y.clone();
    zX.sort_unstable();
    zY.sort_unstable();
    // do NOT dedup — keep same semantics as original C++ implementation
    let mut rX = vec![0usize; n];
    let mut rY = vec![0usize; n];
    for i in 0..n {
        rX[i] = zX.binary_search(&X[i]).unwrap();
        rY[i] = zY.binary_search(&Y[i]).unwrap();
    }

    if zX.len() == 1 || zY.len() == 1 {
        println!("0");
        return;
    }

    let mut ans = Mint::zero();

    for _rep in 0..2 {
        let mut G: Vec<Vec<usize>> = vec![Vec::new(); zX.len()];
        for i in 0..n {
            G[rX[i]].push(rY[i]);
        }

        let m = zY.len();
        let mut V = vec![e(); m];
        for i in 0..n {
            if rY[i] + 1 < m {
                V[rY[i] + 1].first *= f34;
            }
        }
        for i in 1..m {
            let prev = V[i - 1].first;
            V[i].first *= prev;
        }

        let mut seg = LazySegTree::new(&V);
        let mut fs = Mint::one();
        for i in 0..(zX.len() - 1) {
            for &y in &G[i] {
                let mut cur = seg.get(y);
                cur.second *= f34;
                seg.set(y, cur);
                seg.apply_range(0, y, f34);
                seg.apply_range(y + 1, m, f43);
                fs *= f34;
            }
            let all_prd = seg.all_prod();
            let one = Mint::one();
            let term = one - all_prd.first * (one - all_prd.second) - fs;
            let diff = (zX[i + 1] - zX[i]) as i64;
            ans += term * Mint::new(diff);
        }

        std::mem::swap(&mut rX, &mut rY);
        std::mem::swap(&mut zX, &mut zY);
    }

    for _ in 0..n {
        ans *= Mint::new(4);
    }
    let out = (ans * Mint::new(2)).val();
    println!("{}", out);
}