AtCoder Beginner Contest 439 F

https://atcoder.jp/contests/abc439/tasks/abc439_f

山と谷の数ということですが、山があれば谷があります。そして、山と谷は交互に来ます。つまり最初と最後が山なら門松的ということになります。最初の点とその次の点と最後の前の点と最後の点を、A, B, C, Dとすると、なら門松的になります。
まず、Aを固定することを考えると、どうにもならなそうですね。これは捨てて、Bを固定することを考えます。そうすると、可能なAの数が分かりそうですね。Bより前を木にして、Bより小さい点の個数を数えます。また、Cを固定して同様にCより小さいDの数を数えます。また、BとCの間に1点あると2倍、2点あると4倍などと倍々になります。これを考慮してCの方の累積和を計算して、Bの方の和と掛け合わせて、Bを動かします。また、BとCが一致するときも数えます。

// Beautiful Kadomatsu
#![allow(non_snake_case)]

use std::collections::BTreeSet;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// SegTree ////////////////////

trait Monoid {
    type S: Clone;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn e() -> Self::S;
}

struct SegTree<M: Monoid> {
    n: usize,
    size: usize,
    data: Vec<M::S>,
}

impl<M: Monoid> SegTree<M> {
    fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        SegTree {
            n,
            size,
            data: vec![M::e(); size*2-1],
        }
    }
    
    fn from(v: Vec<M::S>) -> Self {
        let n = v.len();
        let size = n.next_power_of_two();
        let mut data = vec![M::e(); size*2-1];
        for i in 0..n {
            data[i+size-1] = v[i].clone();
        }
        let mut seg = SegTree { n, size, data };
        for i in (0..size-1).rev() {
            seg.data[i] = M::op(&seg.data[2*i+1], &seg.data[2*i+2]);
        }
        seg
    }
    
    fn set(&mut self, mut i: usize, x: M::S) {
        i = i + self.size - 1;
        self.data[i] = x;
        while i != 0 {
            i = (i - 1) / 2;
            self.data[i] = M::op(&self.data[2*i+1], &self.data[2*i+2]);
        }
    }
    
    fn prod(&self, mut l: usize, mut r: usize) -> M::S {
        let mut sml = M::e();
        let mut smr = M::e();
        l = l + self.size - 1;
        r = r + self.size - 1;
        while l < r {
            if l % 2 == 0 {
                sml = M::op(&sml, &self.data[l]);
                l += 1;
            }
            if r % 2 == 0 {
                r -= 1;
                smr = M::op(&self.data[r], &smr);
            }
            l = (l - 1) / 2;
            r = (r - 1) / 2
        }
        M::op(&sml, &smr)
    }
    
    fn get(&self, i: usize) -> M::S {
        self.data[i+self.size-1].clone()
    }
}


//////////////////// Monoid ////////////////////

struct Sum;
impl Monoid for Sum {
    type S = i64;
    fn op(a: &Self::S, b: &Self::S) -> Self::S { a + b }
    fn e() -> Self::S { 0 }
}


//////////////////// Tree ////////////////////

struct Tree {
    seg: SegTree::<Sum>,    // Qと同じ値を数える
    Q: Vec<i32>,
}

impl Tree {
    fn size(&self) -> usize {
        self.Q.len()
    }
    
    // 与えられた値のQのindex
    fn find_Q_index(&self, x: i32) -> usize {
        let mut first: usize = 0;
        let mut last: usize = self.Q.len();
        while last - first > 1 {
            let mid = (first + last) / 2;
            if self.Q[mid] > x {
                last = mid
            }
            else {
                first = mid
            }
        }
        first
    }
    
    fn increment(&mut self, x: i32) {
        let index = self.find_Q_index(x);
        let n = self.seg.get(index);
        self.seg.set(index, n + 1)
    }
    
    // 与えられた値未満のQの値の和
    fn sum(&self, x: i32) -> i64 {
        let index = self.find_Q_index(x);
        self.seg.prod(0, index)
    }
    
    fn create(P: &Vec<i32>) -> Self {
        let set: BTreeSet<i32> = P.iter().cloned().collect();
        let Q: Vec<i32> = set.into_iter().collect();
        let N = Q.len();
        let seg = SegTree::<Sum>::new(N);
        Tree { seg, Q }
    }
}


//////////////////// process ////////////////////

fn read_input() -> Vec<i32> {
    let _N: usize = read();
    let P: Vec<i32> = read_vec();
    P
}

const D: i64 = 998244353;

fn half(x: i64) -> i64 {
    if x % 2 == 0 { x / 2 } else { (x + D) / 2 }
}

fn F(P: Vec<i32>) -> i64 {
    let N = P.len();
    
    // 左から追加して自分より小さい個数
    let mut tree1 = Tree::create(&P);
    let mut ns1: Vec<i64> = vec![0; N];
    for (i, &x) in P.iter().enumerate() {
        ns1[i] = tree1.sum(x);
        tree1.increment(x)
    }
    
    // 右から追加して自分より小さい個数
    let mut tree2 = Tree::create(&P);
    let mut ns2: Vec<i64> = vec![0; N];
    for (i, &x) in P.iter().enumerate().rev() {
        ns2[i] = tree2.sum(x);
        tree2.increment(x);
    }
    
    // 累積和
    let mut acc2: Vec<i64> = vec![0; N+1];
    let mut w: i64 = 1;
    for (i, &x) in P.iter().enumerate().rev() {
        w = half(w);
        acc2[i] = (acc2[i+1] + ns2[i] * w) % D;
        tree2.increment(x)
    }
    
    let mut s: i64 = 0;
    let mut w2: i64 = 1;
    for i in (0..N).rev() {
        s = (s + ns1[i] * (acc2[i+1] * w2 % D + ns2[i])) % D;
        w2 = w2 * 2 % D
    }
    s
}

fn main() {
    let kites = read_input();
    println!("{}", F(kites))
}