#1171779 (Rust) No.3590 I Love Inversions

• 問題: No.3590 I Love Inversions
• ユーザー: urectanc
• 提出日時: 2026-07-17 21:41:28
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 1,857 ms / 5,000 ms
• コード長: 6,176 bytes
• コンパイル時間: 12,824 ms
• コンパイル使用メモリ: 197,352 KB
• 実行使用メモリ: 5,888 KB
• 平均クエリ数: 12104.46
• 最終ジャッジ日時: 2026-07-17 21:42:02
• 合計ジャッジ時間: 32,341 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 43

ソースコード

use itertools::Itertools;
use proconio::input;

use crate::urectanc::binary_indexed_tree::BinaryIndexedTree;

fn main() {
    input! { n: usize }

    let ask = |l: usize, r: usize| {
        println!("? {} {}", l + 1, r);
        input! { x: i64 }
        assert_ne!(x, -1);
        x as usize
    };

    let mut bit = BinaryIndexedTree::from(vec![1; n]);
    let mut inv = ask(0, n);
    let mut p = vec![];
    for i in 1..n {
        let ninv = ask(i, n);
        let idx = inv - ninv;
        let x = bit.max_right(|sum| (sum as usize) <= idx);
        bit.add(x, -1);
        p.push(x);
        inv = ninv;
    }
    let x = bit.max_right(|sum| sum <= 0);
    p.push(x);

    let ans = p.iter().map(|&p| p + 1).join(" ");
    println!("! {ans}");
}

pub mod urectanc {
    pub mod binary_indexed_tree {
        use crate::urectanc::{clamp_range, num_traits};
        use clamp_range::ClampRange;
        use num_traits::PrimitiveInteger;
        use std::ops::RangeBounds;
        pub struct BinaryIndexedTree<T> {
            len: usize,
            tree: Vec<T>,
        }
        impl<T, A> From<A> for BinaryIndexedTree<T>
        where
            T: PrimitiveInteger,
            A: AsRef<[T]>,
        {
            fn from(a: A) -> Self {
                let a = a.as_ref();
                let len = a.len();
                let mut tree = vec![T::zero(); len + 1];
                tree[1..].copy_from_slice(a);
                for i in 1..len {
                    let lsb = i & i.wrapping_neg();
                    if i + lsb <= len {
                        let add = tree[i];
                        tree[i + lsb] += add;
                    }
                }
                Self { len, tree }
            }
        }
        impl<T> BinaryIndexedTree<T>
        where
            T: PrimitiveInteger,
        {
            pub fn new(len: usize) -> Self {
                Self {
                    len,
                    tree: vec![T::zero(); len + 1],
                }
            }
            pub fn to_vec(&self) -> Vec<T> {
                let mut a = self.tree.clone();
                for i in (1..self.len).rev() {
                    let lsb = i & i.wrapping_neg();
                    if i + lsb <= self.len {
                        let sub = a[i];
                        a[i + lsb] -= sub;
                    }
                }
                a[1..].to_owned()
            }
            pub fn get(&self, i: usize) -> T {
                self.sum(i..=i)
            }
            pub fn set(&mut self, i: usize, x: T) {
                self.add(i, x - self.get(i));
            }
            pub fn add(&mut self, i: usize, x: T) {
                let mut i = i + 1;
                while i <= self.len {
                    self.tree[i] += x;
                    i += i & i.wrapping_neg();
                }
            }
            pub fn sum(&self, range: impl RangeBounds<usize>) -> T {
                let (mut l, mut r) = range.clamp(0, self.len);
                let mut sum = T::zero();
                while l < r {
                    sum += self.tree[r];
                    r -= r & r.wrapping_neg();
                }
                while r < l {
                    sum -= self.tree[l];
                    l -= l & l.wrapping_neg();
                }
                sum
            }
            pub fn max_right(&self, f: impl Fn(T) -> bool) -> usize {
                let mut r = 0;
                let mut sum = T::zero();
                assert!(f(sum));
                let mut width = self.len.next_power_of_two();
                while width > 0 {
                    if r + width <= self.len && f(sum + self.tree[r + width]) {
                        sum += self.tree[r + width];
                        r += width;
                    }
                    width >>= 1;
                }
                r
            }
        }
    }
    pub mod clamp_range {
        use std::ops::{Bound, RangeBounds};
        pub trait ClampRange: RangeBounds<usize> {
            fn clamp(&self, l: usize, r: usize) -> (usize, usize) {
                assert!(l <= r);
                let start = match self.start_bound() {
                    Bound::Included(&l) => l,
                    Bound::Excluded(&l) => l + 1,
                    Bound::Unbounded => l,
                }
                .clamp(l, r);
                let end = match self.end_bound() {
                    Bound::Included(&r) => r + 1,
                    Bound::Excluded(&r) => r,
                    Bound::Unbounded => r,
                }
                .clamp(l, r);
                (start.min(end), end)
            }
        }
        impl<T: ?Sized> ClampRange for T where T: RangeBounds<usize> {}
    }
    pub mod num_traits {
        use std::{
            fmt::Debug,
            ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Rem, RemAssign, Sub, SubAssign},
        };
        pub trait PrimitiveInteger:
            'static
            + Copy
            + Ord
            + Debug
            + Add<Output = Self>
            + Sub<Output = Self>
            + Mul<Output = Self>
            + Div<Output = Self>
            + Rem<Output = Self>
            + AddAssign
            + SubAssign
            + MulAssign
            + DivAssign
            + RemAssign
        {
            fn midpoint(self, rhs: Self) -> Self;
            fn rem_euclid(self, rhs: Self) -> Self;
            fn zero() -> Self;
            fn one() -> Self;
            fn min_value() -> Self;
            fn max_value() -> Self;
        }
        macro_rules! impl_primitive_integer {
            ($($ty:ty),*) => {
                $(impl PrimitiveInteger for $ty { fn midpoint(self, rhs : Self) -> Self {
                self.midpoint(rhs) } fn rem_euclid(self, rhs : Self) -> Self { self
                .rem_euclid(rhs) } fn zero() -> Self { 0 } fn one() -> Self { 1 } fn
                min_value() -> Self { Self::MIN } fn max_value() -> Self { Self::MAX }
                })*
            };
        }
        impl_primitive_integer!(
            i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize
        );
    }
}