結果

問題 No.3446 Range Adjacent Differences
ユーザー 👑 ArcAki
提出日時 2026-02-10 09:27:58
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
TLE  
実行時間 -
コード長 9,664 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,614 ms
コンパイル使用メモリ 224,000 KB
実行使用メモリ 16,328 KB
最終ジャッジ日時 2026-02-18 20:50:29
合計ジャッジ時間 8,371 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::BTreeMap;
use std::collections::btree_map::Range as BTreeRange;
use std::mem::swap;
use std::ops::RangeBounds;

use proconio::{input, marker::Usize1, fastout};

#[derive(Debug, Clone)]
pub struct Counter<T: Ord> {
    c: usize,
    map: BTreeMap<T, usize>,
}

impl<T: Copy + Ord> Counter<T> {
    pub fn new() -> Self {
        Counter { c: 0, map: BTreeMap::new() }
    }

    #[inline(always)]
    pub fn range<R>(&self, range: R) -> BTreeRange<'_, T, usize>
    where
        R: RangeBounds<T>,
    {
        self.map.range(range)
    }

    #[inline(always)]
    pub fn add(&mut self, x: T, c: usize) {
        *self.map.entry(x).or_insert(0) += c;
        self.c += c;
    }

    #[inline(always)]
    pub fn sub(&mut self, x: T, c: usize) {
        let e = self.map.entry(x).or_insert(0);
        *e = e.saturating_sub(c);
        if self.map[&x] == 0 {
            self.map.remove(&x);
        }
        self.c = self.c.saturating_sub(c);
    }

    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    #[allow(dead_code)]
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.map.len()
    }

    #[allow(dead_code)]
    #[inline(always)]
    pub fn clear(&mut self) {
        self.map.clear();
        self.c = 0;
    }

    #[allow(dead_code)]
    #[inline(always)]
    pub fn merge(&mut self, rhs: &mut Counter<T>) {
        if self.len() < rhs.len() {
            swap(self, rhs);
        }
        for (&k, &v) in rhs.map.iter() {
            self.add(k, v);
        }
        rhs.clear();
    }
}

pub trait SegtreeMonoid {
    type S: Clone;
    fn identity() -> Self::S;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
}

pub struct Segtree<M: SegtreeMonoid> {
    n: usize,
    data: Vec<M::S>,
}

impl<M: SegtreeMonoid> Segtree<M> {
    pub fn new(n: usize) -> Self {
        let n = n.next_power_of_two();
        let data = vec![M::identity(); 2 * n];
        Segtree { n, data }
    }

    pub fn set(&mut self, i: usize, x: M::S) {
        let mut p = i + self.n;
        self.data[p] = x;
        while p > 0 {
            p /= 2;
            self.data[p] = M::op(&self.data[p << 1], &self.data[(p << 1) | 1]);
        }
    }

    pub fn get(&self, p: usize) -> M::S {
        self.data[self.n + p].clone()
    }

    pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
    where
        F: Fn(&M::S) -> bool,
    {
        assert!(f(&M::identity()));
        if l == self.n {
            return self.n;
        }
        l += self.n;
        let mut ac = M::identity();
        while {
            while l % 2 == 0 {
                l >>= 1;
            }
            if !f(&M::op(&ac, &self.data[l])) {
                while l < self.n {
                    l <<= 1;
                    let res = M::op(&ac, &self.data[l]);
                    if f(&res) {
                        ac = res;
                        l += 1;
                    }
                }
                return l - self.n;
            }
            ac = M::op(&ac, &self.data[l]);
            l += 1;
            let z = l as isize;
            (z & -z) != z
        } {}
        self.n
    }

    pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
    where
        F: Fn(&M::S) -> bool,
    {
        assert!(f(&M::identity()));
        if r == 0 {
            return 0;
        }
        r += self.n;
        let mut ac = M::identity();
        while {
            r -= 1;
            while r > 1 && r % 2 == 1 {
                r >>= 1;
            }
            if !f(&M::op(&self.data[r], &ac)) {
                while r < self.n {
                    r = 2 * r + 1;
                    let res = M::op(&self.data[r], &ac);
                    if f(&res) {
                        ac = res;
                        r -= 1;
                    }
                }
                return r + 1 - self.n;
            }
            ac = M::op(&self.data[r], &ac);
            let z = r as isize;
            z & -z != z
        } {}
        0
    }
}

// ====== セグ木のモノイド（和） ======
struct Sum;
impl SegtreeMonoid for Sum {
    type S = usize;
    #[inline(always)]
    fn identity() -> Self::S { 0 }
    #[inline(always)]
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a + *b }
}

// ====== ヒルベルト順 ======
const ROT_DELTA: [u32; 4] = [3, 0, 0, 1];
#[inline]
pub fn hilbert_order(x: u32, y: u32, pow: u32, rot: u32) -> u64 {
    if pow == 0 { return 0; }
    let h: u32 = 1u32 << (pow - 1);
    let mut seg: u32 = if x < h { if y < h { 0 } else { 3 } }
                       else     { if y < h { 1 } else { 2 } };
    seg = (seg + rot) & 3;
    let nrot = (rot + ROT_DELTA[seg as usize]) & 3;
    let nx = x & (h - 1);
    let ny = y & (h - 1);
    let sub: u64 = 1u64 << (2 * pow - 2);
    let mut ord = (seg as u64) * sub;
    let add = hilbert_order(nx, ny, pow - 1, nrot);
    ord += if seg == 1 || seg == 2 { add } else { sub - 1 - add };
    ord
}

// ====== distinct 値集合（セグ木）から predecessor/successor を取る ======
// 「p 未満で最大」(strict) を返す。なければ None
#[inline(always)]
fn prev_distinct(st: &Segtree<Sum>, p: usize) -> Option<usize> {
    if p == 0 { return None; }
    // [l, p) の和が 0 である限り左へ伸ばす。止まった位置は (pred+1)
    let l = st.min_left(p, |s| *s == 0);
    if l == 0 { None } else { Some(l - 1) }
}

// 「p より大で最小」(strict) を返す。なければ None
#[inline(always)]
fn next_distinct(st: &Segtree<Sum>, p: usize, m: usize) -> Option<usize> {
    if p + 1 >= m { return None; }
    // [p+1, r) の和が 0 の間伸ばし、最初に非0が出る位置が succ
    let r = st.max_right(p + 1, |s| *s == 0);
    if r >= m { None } else { Some(r) }
}

// ====== Mo の add/remove（配列 index を渡す） ======
#[inline(always)]
fn add_idx(
    i: usize,
    comp: &[usize],
    vals: &[usize],
    cnt_val: &mut [usize],
    st: &mut Segtree<Sum>,
    gaps: &mut Counter<usize>,
) {
    let p = comp[i];
    let old = cnt_val[p];
    cnt_val[p] = old + 1;
    st.set(p, cnt_val[p]);

    if old == 0 {
        // distinct 新規出現：隣接差分を貼り替える
        let l = prev_distinct(st, p);
        let r = next_distinct(st, p, vals.len());
        let vp = vals[p];

        if let (Some(li), Some(ri)) = (l, r) {
            gaps.sub(vals[ri] - vals[li], 1);
        }
        if let Some(li) = l {
            gaps.add(vp - vals[li], 1);
        }
        if let Some(ri) = r {
            gaps.add(vals[ri] - vp, 1);
        }
    } else {
        // 重複追加：0差分が1本増える
        gaps.add(0, 1);
    }
}

#[inline(always)]
fn remove_idx(
    i: usize,
    comp: &[usize],
    vals: &[usize],
    cnt_val: &mut [usize],
    st: &mut Segtree<Sum>,
    gaps: &mut Counter<usize>,
) {
    let p = comp[i];
    let old = cnt_val[p];
    cnt_val[p] = old - 1;
    st.set(p, cnt_val[p]);

    if old == 1 {
        // distinct 消滅：隣接差分を貼り替える（p が居なくなった後の近傍）
        let l = prev_distinct(st, p);
        let r = next_distinct(st, p, vals.len());
        let vp = vals[p];

        if let Some(li) = l {
            gaps.sub(vp - vals[li], 1);
        }
        if let Some(ri) = r {
            gaps.sub(vals[ri] - vp, 1);
        }
        if let (Some(li), Some(ri)) = (l, r) {
            gaps.add(vals[ri] - vals[li], 1);
        }
    } else {
        // 重複削除：0差分が1本減る
        gaps.sub(0, 1);
    }
}

#[fastout]
fn main() {
    input! {
        n: usize, q: usize,
        a_in: [usize; n],                   // 1..=1e7 想定
        query: [(Usize1, usize, usize, char); q], // (L-1, R, X, 'L'/'R') で [L,R) として扱う
    }

    // 0-index化（差分は不変）
    let a: Vec<usize> = a_in.into_iter().map(|x| x - 1).collect();

    // 座圧
    let mut vals = a.clone();
    vals.sort_unstable();
    vals.dedup();
    let m = vals.len();

    let comp: Vec<usize> = a.iter()
        .map(|&x| vals.binary_search(&x).unwrap())
        .collect();

    // 値集合（カウント）セグ木
    let mut st: Segtree<Sum> = Segtree::new(m);
    let mut cnt_val = vec![0usize; m];

    // 差分 multiset
    let mut gaps: Counter<usize> = Counter::new();

    // Mo（ヒルベルト順）
    let pow = 17u32; // 2^17=131072 >= 1e5 程度なら十分
    let mut ord: Vec<usize> = (0..q).collect();
    ord.sort_unstable_by_key(|&idx| {
        let (l, r, _x, _c) = query[idx];
        hilbert_order(l as u32, r as u32, pow, 0)
    });

    let mut ans = vec![0i32; q];
    let (mut l, mut r) = (0usize, 0usize); // [l,r)

    for idx in ord {
        let (ql, qr, x, c) = query[idx];

        while r < qr {
            add_idx(r, &comp, &vals, &mut cnt_val, &mut st, &mut gaps);
            r += 1;
        }
        while l > ql {
            l -= 1;
            add_idx(l, &comp, &vals, &mut cnt_val, &mut st, &mut gaps);
        }
        while r > qr {
            r -= 1;
            remove_idx(r, &comp, &vals, &mut cnt_val, &mut st, &mut gaps);
        }
        while l < ql {
            remove_idx(l, &comp, &vals, &mut cnt_val, &mut st, &mut gaps);
            l += 1;
        }

        // 回答：gaps から <=x の最大 / >=x の最小
        let res = if gaps.is_empty() {
            None
        } else if c == 'L' {
            gaps.range(..=x).next_back().map(|(k, _)| *k)
        } else {
            gaps.range(x..).next().map(|(k, _)| *k)
        };

        ans[idx] = res.map(|v| v as i32).unwrap_or(-1);
    }

    for v in ans {
        println!("{}", v);
    }
}
0