結果

問題 No.1802 Range Score Query for Bracket Sequence
ユーザー akakimidoriakakimidori
提出日時 2022-01-09 16:30:20
言語 Rust
(1.77.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 4,401 bytes
コンパイル時間 6,738 ms
コンパイル使用メモリ 156,404 KB
実行使用メモリ 8,008 KB
最終ジャッジ日時 2023-09-12 14:15:43
合計ジャッジ時間 5,338 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 56 ms
8,008 KB
testcase_02 AC 56 ms
7,964 KB
testcase_03 AC 57 ms
7,948 KB
testcase_04 AC 56 ms
7,992 KB
testcase_05 AC 56 ms
7,964 KB
testcase_06 AC 56 ms
7,964 KB
testcase_07 AC 56 ms
7,932 KB
testcase_08 AC 58 ms
7,956 KB
testcase_09 AC 56 ms
8,004 KB
testcase_10 AC 56 ms
7,988 KB
testcase_11 AC 47 ms
7,992 KB
testcase_12 AC 48 ms
7,932 KB
testcase_13 AC 48 ms
7,996 KB
testcase_14 AC 55 ms
7,988 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin SegmentTree Point update Range query ----------
mod segment_tree {
    pub struct PURQ<T, F> {
        size: usize,
        data: Vec<T>,
        e: T,
        op: F,
    }
    #[allow(dead_code)]
    impl<T, F> PURQ<T, F>
    where
        T: Clone,
        F: Fn(&T, &T) -> T,
    {
        pub fn new(size: usize, e: T, op: F) -> PURQ<T, F> {
            let size = size.next_power_of_two();
            PURQ {
                size,
                data: vec![e.clone(); 2 * size],
                e: e,
                op: op,
            }
        }
        pub fn update(&mut self, x: usize, v: T) {
            assert!(x < self.size);
            let mut x = x + self.size;
            let data = &mut self.data;
            data[x] = v;
            x >>= 1;
            while x > 0 {
                data[x] = (self.op)(&data[2 * x], &data[2 * x + 1]);
                x >>= 1;
            }
        }
        pub fn update_tmp(&mut self, x: usize, v: T) {
            assert!(x < self.size);
            self.data[x + self.size] = v;
        }
        pub fn update_all(&mut self) {
            let data = &mut self.data;
            for k in (1..self.size).rev() {
                data[k] = (self.op)(&data[2 * k], &data[2 * k + 1]);
            }
        }
        pub fn find(&self, l: usize, r: usize) -> T {
            assert!(l <= r && r <= self.size);
            if l == r {
                return self.e.clone();
            }
            let mut p = self.e.clone();
            let mut q = self.e.clone();
            let mut l = l + self.size;
            let mut r = r + self.size;
            let data = &self.data;
            while l < r {
                if l & 1 == 1 {
                    p = (self.op)(&p, &data[l]);
                    l += 1;
                }
                if r & 1 == 1 {
                    r -= 1;
                    q = (self.op)(&data[r], &q);
                }
                l >>= 1;
                r >>= 1;
            }
            (self.op)(&p, &q)
        }
    }
}
// ---------- end SegmentTree Point update Range query ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let n: usize = sc.next();
    let q: usize = sc.next();
    let mut s: Vec<u8> = sc.next_bytes();
    s.insert(0, b')');
    s.push(b'(');
    let mut seg = segment_tree::PURQ::new(n + 2, 0, |a, b| *a + *b);
    for (i, s) in s.windows(2).enumerate() {
        if s[0] == b'(' && s[1] == b')' {
            seg.update_tmp(i, 1);
        }
    }
    seg.update_all();
    for _ in 0..q {
        let op: u8 = sc.next();
        if op == 1 {
            let x = sc.next::<usize>();
            seg.update(x - 1, 0);
            seg.update(x, 0);
            s[x] ^= b'(' ^ b')';
            for &y in [x - 1, x].iter() {
                if s[y] == b'(' && s[y + 1] == b')' {
                    seg.update(y, 1);
                }
            }
        } else {
            let l = sc.next::<usize>();
            let r = sc.next::<usize>();
            let ans = if l < r {
                seg.find(l, r)
            } else {
                0
            };
            writeln!(out, "{}", ans).ok();
        }
    }
}
0