#1169666 (Rust) No.3464 Max and Sum on Grid

• 問題: No.3464 Max and Sum on Grid
• ユーザー: titia
• 提出日時: 2026-06-25 04:06:04
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 831 ms / 5,000 ms
• コード長: 7,008 bytes
• コンパイル時間: 1,317 ms
• コンパイル使用メモリ: 204,436 KB
• 実行使用メモリ: 29,952 KB
• 最終ジャッジ日時: 2026-06-25 04:06:20
• 合計ジャッジ時間: 10,857 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 10

ソースコード

// PyPyで通すのを諦めてChatGPTにより変換

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

#[derive(Clone)]
struct BIT {
    bit: Vec<i64>,
    len: usize,
}

impl BIT {
    fn new(len: usize) -> Self {
        Self {
            bit: vec![0; len + 1],
            len,
        }
    }

    fn update(&mut self, mut v: usize, w: i64) {
        while v <= self.len {
            self.bit[v] += w;
            v += v & (!v + 1);
        }
    }

    fn getvalue(&self, mut v: usize) -> i64 {
        let mut ans = 0i64;
        while v > 0 {
            ans += self.bit[v];
            v -= v & (!v + 1);
        }
        ans
    }

    #[allow(dead_code)]
    fn bisect_on_bit(&self, mut x: i64) -> usize {
        if x <= 0 {
            return 0;
        }

        let mut ans = 0usize;
        let mut h = 1usize;
        while (h << 1) <= self.len {
            h <<= 1;
        }

        while h > 0 {
            if ans + h <= self.len && self.bit[ans + h] < x {
                x -= self.bit[ans + h];
                ans += h;
            }
            h >>= 1;
        }

        ans + 1
    }
}

fn main() {
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();
    let q: usize = it.next().unwrap().parse().unwrap();

    let a: Vec<usize> = (0..n)
        .map(|_| it.next().unwrap().parse().unwrap())
        .collect();

    let b: Vec<usize> = (0..n)
        .map(|_| it.next().unwrap().parse().unwrap())
        .collect();

    let mut queries = Vec::with_capacity(q);

    for _ in 0..q {
        let l: usize = it.next().unwrap().parse().unwrap();
        let d: usize = it.next().unwrap().parse().unwrap();
        let r: usize = it.next().unwrap().parse().unwrap();
        let u: usize = it.next().unwrap().parse().unwrap();
        queries.push((l, d, r, u));
    }

    let mut list = Vec::<(usize, usize, usize)>::new();

    for (i, &(l0, d0, r0, u0)) in queries.iter().enumerate() {
        let l = l0 - 1;
        let d = d0 - 1;
        let r = r0 - 1;
        let u = u0 - 1;

        list.push((r, u, i * 4));

        if d >= 1 {
            list.push((r, d - 1, i * 4 + 1));
        }

        if l >= 1 {
            list.push((l - 1, u, i * 4 + 2));
        }

        if l >= 1 && d >= 1 {
            list.push((l - 1, d - 1, i * 4 + 3));
        }
    }

    let mut lans = vec![0i64; q * 4];

    const LEN: usize = 100_001;

    let mut asum = BIT::new(LEN + 1);
    let mut ako = BIT::new(LEN + 1);

    let mut bsum = BIT::new(LEN + 1);
    let mut bko = BIT::new(LEN + 1);

    const SQ: usize = 100;

    let mut qs = vec![Vec::<(usize, usize, usize)>::new(); n / SQ + 2];

    for (x, y, ind) in list {
        qs[x / SQ].push((x, y, ind));
    }

    for i in 0..qs.len() {
        if i % 2 == 0 {
            qs[i].sort_by_key(|x| x.1);
        } else {
            qs[i].sort_by(|a, b| b.1.cmp(&a.1));
        }
    }

    let mut nowx = 0usize;
    let mut nowy = 0usize;

    let mut ans = std::cmp::max(a[0], b[0]) as i64;

    asum.update(a[0], a[0] as i64);
    ako.update(a[0], 1);

    bsum.update(b[0], b[0] as i64);
    bko.update(b[0], 1);

    for i in 0..qs.len() {
        if i % 2 == 0 {
            for &(x, y, ind) in &qs[i] {
                while nowx < x {
                    let av = a[nowx + 1];

                    let plus =
                        bsum.getvalue(LEN) - bsum.getvalue(av);
                    let ko = bko.getvalue(av);

                    ans += av as i64 * ko + plus;

                    asum.update(av, av as i64);
                    ako.update(av, 1);

                    nowx += 1;
                }

                while nowx > x {
                    let av = a[nowx];

                    let plus =
                        bsum.getvalue(LEN) - bsum.getvalue(av);
                    let ko = bko.getvalue(av);

                    ans -= av as i64 * ko + plus;

                    asum.update(av, -(av as i64));
                    ako.update(av, -1);

                    nowx -= 1;
                }

                while nowy < y {
                    let bv = b[nowy + 1];

                    let plus =
                        asum.getvalue(LEN) - asum.getvalue(bv);
                    let ko = ako.getvalue(bv);

                    ans += bv as i64 * ko + plus;

                    bsum.update(bv, bv as i64);
                    bko.update(bv, 1);

                    nowy += 1;
                }

                while nowy > y {
                    let bv = b[nowy];

                    let plus =
                        asum.getvalue(LEN) - asum.getvalue(bv);
                    let ko = ako.getvalue(bv);

                    ans -= bv as i64 * ko + plus;

                    bsum.update(bv, -(bv as i64));
                    bko.update(bv, -1);

                    nowy -= 1;
                }

                lans[ind] = ans;
            }
        } else {
            for &(x, y, ind) in &qs[i] {
                while nowx > x {
                    let av = a[nowx];

                    let plus =
                        bsum.getvalue(LEN) - bsum.getvalue(av);
                    let ko = bko.getvalue(av);

                    ans -= av as i64 * ko + plus;

                    asum.update(av, -(av as i64));
                    ako.update(av, -1);

                    nowx -= 1;
                }

                while nowx < x {
                    let av = a[nowx + 1];

                    let plus =
                        bsum.getvalue(LEN) - bsum.getvalue(av);
                    let ko = bko.getvalue(av);

                    ans += av as i64 * ko + plus;

                    asum.update(av, av as i64);
                    ako.update(av, 1);

                    nowx += 1;
                }

                while nowy > y {
                    let bv = b[nowy];

                    let plus =
                        asum.getvalue(LEN) - asum.getvalue(bv);
                    let ko = ako.getvalue(bv);

                    ans -= bv as i64 * ko + plus;

                    bsum.update(bv, -(bv as i64));
                    bko.update(bv, -1);

                    nowy -= 1;
                }

                while nowy < y {
                    let bv = b[nowy + 1];

                    let plus =
                        asum.getvalue(LEN) - asum.getvalue(bv);
                    let ko = ako.getvalue(bv);

                    ans += bv as i64 * ko + plus;

                    bsum.update(bv, bv as i64);
                    bko.update(bv, 1);

                    nowy += 1;
                }

                lans[ind] = ans;
            }
        }
    }

    let mut out = String::new();

    for i in 0..q {
        let score =
            lans[i * 4]
            - lans[i * 4 + 1]
            - lans[i * 4 + 2]
            + lans[i * 4 + 3];

        out.push_str(&format!("{}\n", score));
    }

    print!("{}", out);
}