結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー norioc
提出日時 2026-01-30 21:08:40
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 1,039 ms / 5,000 ms
コード長 3,632 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,923 ms
コンパイル使用メモリ 234,232 KB
実行使用メモリ 93,296 KB
最終ジャッジ日時 2026-01-30 21:08:47
合計ジャッジ時間 6,408 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::collections::HashSet`
 --> src/main.rs:3:5
  |
3 | use std::collections::HashSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: unused imports: `marker::Chars` and `marker::Usize1`
 --> src/main.rs:6:23
  |
6 | use proconio::{input, marker::Usize1, marker::Chars};
  |                       ^^^^^^^^^^^^^^  ^^^^^^^^^^^^^

warning: field `vs` is never read
  --> src/main.rs:68:5
   |
67 | struct Compression<T> {
   |        ----------- field in this struct
68 |     vs: Vec<T>,                 // ソート済み・重複なしの値
   |     ^^
   |
   = note: `Compression` has a derived impl for the trait `Debug`, but this is intentionally ignored during dead code analysis
   = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: methods `len`, `value`, and `map` are never used
   --> src/main.rs:93:8
    |
 72 | / impl<T> Compression<T>
 73 | | where
 74 | |     T: Ord + Copy + Eq + Hash,
    | |______________________________- methods in this implementation
...
 93 |       fn len(&self) -> usize {
    |          ^^^
...
103 |       fn value(&self, index: usize) -> T {
    |          ^^^^^
...
108 |       fn map<I>(&self, iterable: I) -> Vec<usize>
    |          ^^^

ソースコード

diff #
raw source code 

#![allow(non_snake_case)]

use std::collections::HashSet;
use std::collections::HashMap;
use std::hash::Hash;
use proconio::{input, marker::Usize1, marker::Chars};
use itertools::Itertools;

const INF: i64 = 1 << 62;

#[derive(Debug, Clone)]
struct FenwickTree {
    n: usize,
    data: Vec<i64>,
}

impl FenwickTree {
    /// サイズ n の Fenwick Tree を作成
    fn new(n: usize) -> Self {
        let size = n + 10;
        FenwickTree {
            n: size,
            data: vec![0; size],
        }
    }

    /// p 番目に x を加算 (0-indexed)
    fn add(&mut self, mut p: usize, x: i64) {
        assert!(p < self.n);
        p += 1;
        while p < self.data.len() {
            self.data[p] += x;
            p += p & (!p + 1); // p & -p
        }
    }

    /// 区間 [0, p] の和 (0-indexed)
    fn sum(&self, mut p: usize) -> i64 {
        assert!(p < self.n);
        p += 1;
        let mut s = 0;
        while p > 0 {
            s += self.data[p];
            p &= p - 1; // p -= p & -p
        }
        s
    }

    /// 区間 [l, r] の和
    fn range_sum(&self, l: usize, r: usize) -> i64 {
        assert!(l <= r && r < self.n);
        if l == 0 {
            self.sum(r)
        } else {
            self.sum(r) - self.sum(l - 1)
        }
    }

    /// p 番目の値
    fn get(&self, p: usize) -> i64 {
        self.range_sum(p, p)
    }
}


#[derive(Debug)]
struct Compression<T> {
    vs: Vec<T>,                 // ソート済み・重複なしの値
    v2i: HashMap<T, usize>,     // 値 -> インデックス
}

impl<T> Compression<T>
where
    T: Ord + Copy + Eq + Hash,
{
    /// iterable から座標圧縮を構築
    fn new<I>(iterable: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut vs: Vec<T> = iterable.into_iter().collect();
        vs.sort();
        vs.dedup();

        let mut v2i = HashMap::new();
        for (i, &val) in vs.iter().enumerate() {
            v2i.insert(val, i);
        }

        Self { vs, v2i }
    }

    fn len(&self) -> usize {
        self.vs.len()
    }

    /// val のインデックスを返す
    fn index(&self, val: T) -> usize {
        self.v2i[&val]
    }

    /// インデックスに対応する値を返す
    fn value(&self, index: usize) -> T {
        self.vs[index]
    }

    /// iterable を圧縮後のインデックス列に変換
    fn map<I>(&self, iterable: I) -> Vec<usize>
    where
        I: IntoIterator<Item = T>,
    {
        iterable.into_iter().map(|x| self.index(x)).collect()
    }
}

fn main() {
    input! {
        N: usize,
        A: [i64; N],
    }

    let comp = Compression::new(A.iter().chain([-INF, INF].iter()));
    let xs = A.iter().map(|x| comp.index(x)).collect_vec();
    let sz = xs.len();

    let mut lt = FenwickTree::new(sz+10);
    let mut rt = FenwickTree::new(sz+10);
    let mut dup = FenwickTree::new(sz+10); // dup.get(x) : x の重複数
    for &x in &xs {
        rt.add(x, 1);
    }

    let mut ans = 0;
    for x in xs {  // 真ん中を x で固定
        // 真ん中を最小値とする
        let l = lt.range_sum(x+1, sz+5);
        let r = rt.range_sum(x+1, sz+5);
        ans += l * r; // 重複が含まれる
        ans -= dup.range_sum(x+1, sz+5); // 重複を除く

        // 真ん中を最大値とする
        let l = lt.sum(x-1);
        let r = rt.sum(x-1);
        ans += l * r; // 重複が含まれる
        ans -= dup.sum(x-1); // 重複を除く

        lt.add(x, 1);
        rt.add(x, -1);
        let old = dup.get(x);
        dup.add(x, lt.get(x) * rt.get(x) - old);
    }

    println!("{}", ans);
}
0