結果
問題 | No.1091 Range Xor Query |
ユーザー | 43flyingcar |
提出日時 | 2020-06-26 23:47:15 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 34,266 bytes |
コンパイル時間 | 14,368 ms |
コンパイル使用メモリ | 384,376 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 00:42:50 |
合計ジャッジ時間 | 23,449 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 48 ms
5,376 KB |
testcase_04 | AC | 226 ms
5,376 KB |
testcase_05 | AC | 240 ms
5,376 KB |
testcase_06 | AC | 7 ms
5,376 KB |
testcase_07 | AC | 249 ms
5,376 KB |
testcase_08 | AC | 374 ms
5,376 KB |
testcase_09 | AC | 175 ms
5,376 KB |
testcase_10 | AC | 248 ms
5,376 KB |
testcase_11 | AC | 318 ms
5,376 KB |
testcase_12 | AC | 188 ms
5,376 KB |
testcase_13 | AC | 384 ms
5,376 KB |
testcase_14 | AC | 283 ms
5,376 KB |
testcase_15 | AC | 288 ms
5,376 KB |
testcase_16 | AC | 280 ms
5,376 KB |
testcase_17 | AC | 386 ms
5,376 KB |
testcase_18 | AC | 57 ms
5,376 KB |
testcase_19 | AC | 64 ms
5,376 KB |
testcase_20 | AC | 369 ms
5,376 KB |
testcase_21 | AC | 170 ms
5,376 KB |
testcase_22 | AC | 341 ms
5,376 KB |
testcase_23 | AC | 339 ms
5,376 KB |
testcase_24 | AC | 328 ms
5,376 KB |
testcase_25 | AC | 330 ms
5,376 KB |
testcase_26 | AC | 328 ms
5,376 KB |
testcase_27 | AC | 338 ms
5,376 KB |
コンパイルメッセージ
warning: unused import: `std::cmp::min` --> src/main.rs:63:5 | 63 | use std::cmp::min; | ^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `std::collections::BTreeMap` --> src/main.rs:64:5 | 64 | use std::collections::BTreeMap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::process` --> src/main.rs:65:5 | 65 | use std::process; | ^^^^^^^^^^^^ warning: unused import: `std::collections::HashSet` --> src/main.rs:68:5 | 68 | use std::collections::HashSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeSet` --> src/main.rs:70:5 | 70 | use std::collections::BTreeSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unnecessary parentheses around `while` condition --> src/main.rs:287:10 | 287 | while(n>0){ | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 287 - while(n>0){ 287 + while n>0 { | warning: unnecessary parentheses around `if` condition --> src/main.rs:332:11 | 332 | if(self.par[x] == x){ | ^ ^ | help: remove these parentheses | 332 - if(self.par[x] == x){ 332 + if self.par[x] == x { | warning: unnecessary parentheses around `if` condition --> src/main.rs:349:16 | 349 | if (self.rank[x] < self.rank[y]){ | ^ ^ | help: remove these parentheses | 349 - if (self.rank[x] < self.rank[y]){ 349 + if self.rank[x] < self.rank[y] { | warning: unnecessary parentheses around `if` condition --> src/main.rs:360:19 | 360 | if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;} | ^ ^ | help: remove these parentheses | 360 - if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;} 360 +
ソースコード
#[allow(unused_macros)] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } #[allow(unused_macros)] macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let mut $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } #[allow(unused_macros)] macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } use std::cmp::Ordering; use std::cmp; use std::cmp::min; use std::collections::BTreeMap; use std::process; use std::cmp::Ord; use std::collections::HashMap; use std::collections::HashSet; use std::collections::VecDeque; use std::collections::BTreeSet; use std::mem; use std::collections::BinaryHeap; use std::hash::{Hash, Hasher}; // ---------- begin ModInt ---------- #[derive(Clone, Copy)] struct ModInt(usize); impl std::ops::Add for ModInt { type Output = ModInt; fn add(self, rhs: ModInt) -> Self::Output { let mut d = self.0 + rhs.0; if d >= MODu { d -= MODu; } ModInt(d) } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, rhs: ModInt) { *self = *self + rhs; } } impl std::ops::Sub for ModInt { type Output = ModInt; fn sub(self, rhs: ModInt) -> Self::Output { let mut d = self.0 + MODu - rhs.0; if d >= MODu { d -= MODu; } ModInt(d) } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, rhs: ModInt) { *self = *self - rhs; } } impl std::ops::Mul for ModInt { type Output = ModInt; fn mul(self, rhs: ModInt) -> Self::Output { ModInt((self.0 as u64 * rhs.0 as u64 % MODu as u64) as usize) } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, rhs: ModInt) { *self = *self * rhs; } } impl std::ops::Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { ModInt(if self.0 == 0 {0} else {MODu - self.0}) } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let val = s.parse::<usize>()?; Ok(ModInt::new(val)) } } impl PartialEq for ModInt { fn eq(&self, other: &Self) -> bool { self.0 == other.0 } } impl Hash for ModInt { fn hash<H: Hasher>(&self, state: &mut H) { self.0.hash(state); self.0.hash(state); } } impl Eq for ModInt {} #[allow(dead_code)] impl ModInt { pub fn new(n: usize) -> ModInt { ModInt(n % MODu) } pub fn zero() -> ModInt { ModInt(0) } pub fn one() -> ModInt { ModInt(1) } pub fn pow(self, mut n: usize) -> ModInt { let mut t = ModInt::one(); let mut s = self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(self) -> ModInt { self.pow(MODu - 2) } } // ---------- end ModInt ---------- /// Equivalent to std::lowerbound and std::upperbound in c++ pub trait BinarySearch<T> { fn lower_bound(&self, x:&T) -> usize; fn upper_bound(&self, x:&T) -> usize; } impl<T: Ord> BinarySearch<T> for VecDeque<T>{ fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } impl<T: Ord> BinarySearch<T> for [T]{ fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } fn matmul(A:&Vec<Vec<i64>>, B:&Vec<Vec<i64>>) -> Vec<Vec<i64>>{ let mut C = vec![vec![0;B[0].len()];A.len()]; for i in 0..A.len(){ for k in 0..B.len(){ for j in 0..B[0].len(){ C[i][j] += A[i][k]*B[k][j]; C[i][j] %= MOD; } } } return C; } fn matpow(A:&mut Vec<Vec<i64>>, n:usize) -> Vec<Vec<i64>>{ let mut B = vec![vec![0;A.len()];A.len()]; for i in 0..A.len(){ B[i][i] = 1; } let mut n = n; let mut tmp = A.clone(); while(n>0){ if n&1 == 1{B = matmul(&B, &tmp);} tmp = matmul(&tmp, &tmp); n>>=1; } return B; } fn divisor(n:usize) -> Vec<usize>{ let mut res:Vec<usize> = Vec::new(); for i in 1..n+1{ if i*i>n{break;} if n%i == 0{ res.push(i); if i != n/i{ res.push(n/i); } } } res } struct UnionFind{ par:Vec<usize>, rank:Vec<usize>, size:Vec<usize>, size_edge:Vec<usize>, } impl UnionFind{ fn init(n:usize) -> UnionFind{ let mut par = vec![0;n]; for i in 0..n{ par[i] = i; } UnionFind{ par:par, rank:vec![0;n], size:vec![1;n], size_edge:vec![0;n], } } fn find(&mut self, x:usize) ->usize{ if(self.par[x] == x){ x } else{ let p = self.par[x]; let res = self.find(p); self.par[x] = res; res } } fn same(&mut self, a:usize, b:usize)->bool{ self.find(a) == self.find(b) } fn unite(&mut self, a:usize, b:usize){ let x = self.find(a); let y = self.find(b); if x != y{ if (self.rank[x] < self.rank[y]){ self.par[x] = y; self.size[y] += self.size[x]; self.size_edge[y] += self.size_edge[x]; self.size_edge[y] += 1; } else{ self.par[y] = x; self.size[x] += self.size[y]; self.size_edge[x] += self.size_edge[y]; self.size_edge[x] += 1; if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;} } } else{ self.size_edge[x] += 1; } } fn check_size(&mut self, a:usize) -> usize{ let x = self.find(a); let s = self.size[x]; s } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); std::str::from_utf8(&buf).unwrap() .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } } struct LazySegTree<BiOp> { n: usize, val: Vec<i64>, ma:Vec<i64>, op: BiOp, e: i64, upe:i64, inf:i64, } impl<BiOp> LazySegTree<BiOp> where BiOp: Fn(i64, i64) -> i64{ pub fn new(n_: usize, op: BiOp, e: i64, upe:i64, inf:i64) -> Self { let mut n = 1; while n < n_ { n *= 2; } // n is a power of 2 LazySegTree {n: n, val: vec![e; 2 * n ], ma:vec![upe;2*n], op: op, e: e, upe:upe, inf:inf} } pub fn query(&self, x:usize, y:usize, l:usize, r:usize, k:usize) -> i64 { if (r<=x || y<=l) {return self.inf;} if (x<=l && r<=y) {return self.ma[k];} let mut L = self.query(x,y,l,(l+r)/2, k*2); let mut R = self.query(x,y,(l+r)/2,r, k*2+1); return self.val[k] + (self.op)(L, R); } pub fn update(&mut self, x:usize, y:usize, v:i64, l:usize,r:usize, k:usize) { if (l>=r) {return;} if (x<=l && r<=y){ self.val[k]+=v; self.ma[k]+=v; } else if(l<y && x<r){ self.update(x, y, v, l, (l+r)/2, k*2); self.update(x,y,v,(l+r)/2,r, k*2+1); self.ma[k] = self.val[k] + (self.op)(self.ma[k*2], self.ma[k*2+1]); } } } fn modinv(a:ModInt)->ModInt{ let mut a = a.0 as usize; let mut b = MODu as i64; let mut u = 1 as i64; let mut v = 0 as i64; let mut a = a as i64; let mut m = MODu as i64; while(b>0){ let mut t = a/b; a -= t*b; mem::swap(&mut a, &mut b); u-=t*v; mem::swap(&mut u, &mut v); } u%=m; if u<0{u+=m;} return ModInt(u as usize); } fn modinv2(a:usize)->usize{ let mut a = a as usize; let mut b = MODu as i64; let mut u = 1 as i64; let mut v = 0 as i64; let mut a = a as i64; let mut m = MODu as i64; while(b>0){ let mut t = a/b; a -= t*b; mem::swap(&mut a, &mut b); u-=t*v; mem::swap(&mut u, &mut v); } u%=m; if u<0{u+=m;} return u as usize; } fn modpow(x:ModInt, n:ModInt) -> ModInt{ let mut ans = ModInt(1); let mut n = n.0 as usize; let mut x = x; while(n != 0){ if (n&1 == 1){ans = ans*x;} x = x*x; n = n>>1; } ans } fn comb(a:usize, b:usize, fac:&Vec<ModInt>, ifac:&Vec<ModInt>)->ModInt{ let mut a = a; let mut b = b; if a == 0 && b == 0{return ModInt(1);} if a<b || a<0{return ModInt(0);} let mut tmp = ifac[a-b]*ifac[b]; return tmp * fac[a]; } fn invs()->(Vec<ModInt>, Vec<ModInt>){ let mut fac = vec![ModInt(0);300001]; let mut ifac = vec![ModInt(0);300001]; fac[0] = ModInt(1); ifac[0] = ModInt(1); for i in 0..300000{ fac[i+1] = fac[i] * ModInt(i+1); ifac[i+1] = ifac[i] * modpow(ModInt(i+1), ModInt(MODu - 2)); } (fac, ifac) } struct ConvexHallTrick { Q: Vec<(i64, i64)>, } impl ConvexHallTrick{ pub fn new() -> Self { ConvexHallTrick {Q: Vec::new()} } pub fn calc(&self, p:(i64, i64), x:i64)->i64{ return p.0 * x + p.1; } pub fn dodo(& self, A:(i64, i64), B:(i64, i64), C:(i64, i64)) -> bool{ //max or min (A.1 - C.1) * (B.0 - A.0) <= (A.1 - B.1)*(C.0 - A.0) } pub fn add(&mut self, a:i64, b:i64){ self.Q.push((a, b)); let mut v = self.Q.len(); while(v >=3 && self.dodo(self.Q[v-3], self.Q[v-2], self.Q[v-1])){ self.Q[v-2] = self.Q[v-1]; self.Q.pop(); v = self.Q.len(); } } pub fn query(& self, x:i64) -> i64{ let mut L = -1; let mut R = (self.Q.len() - 1) as i64; while(R-L>1){ let mut m = (L+R)/2; if self.calc(self.Q[m as usize], x)>=self.calc(self.Q[m as usize+1], x){ L=m; } else{ R=m; } } return self.calc(self.Q[R as usize], x); } } #[derive(Eq, PartialEq, Clone, Debug)] pub struct Rev<T>(pub T); impl<T: PartialOrd> PartialOrd for Rev<T> { fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> { other.0.partial_cmp(&self.0) } } impl<T: Ord> Ord for Rev<T> { fn cmp(&self, other: &Rev<T>) -> Ordering { other.0.cmp(&self.0) } } fn sieve(n:usize) -> (Vec<bool>, Vec<usize>){ let mut p:usize = 0; let mut is_prime = vec![false; n+1]; let mut prime = Vec::new(); for i in 0..n+1{ is_prime[i] = true; } is_prime[0] = false; is_prime[1] = false; for i in 2..n+1{ if is_prime[i]{ prime.push(i as usize); let mut j = 2*i; while(j<=n){ is_prime[j] = false; j+=i; } } } (is_prime, prime) } fn nHr(n:usize, r:usize, fac:&Vec<ModInt>, ifac:&Vec<ModInt>) -> ModInt{ comb(n + r - 1, r, fac, ifac) } fn gcd(a:usize, b:usize)->usize{ if b==0{return a;} return gcd(b, a%b); } fn lcm(a:usize, b:usize)->usize{ return (b/gcd(a, b))*a; } struct SegTree_MOD<BiOp> { n: usize, dat: Vec<i64>, op: BiOp, e: i64, mod_:i64, } impl<BiOp> SegTree_MOD<BiOp> where BiOp: Fn(i64, i64) -> i64 { pub fn new(n_: usize, op: BiOp, e: i64, mod_:i64) -> Self { let mut n = 1; while n < n_ { n *= 2; } // n is a power of 2 SegTree_MOD {n: n, dat: vec![e; 2 * n - 1], op: op, e: e, mod_:mod_} } /* ary[k] <- v */ pub fn update(&mut self, idx: usize, v: i64) { let mut k = idx + self.n - 1; self.dat[k] = v; while k > 0 { k = (k - 1) / 2; self.dat[k] = (self.op)(self.dat[2 * k + 1], self.dat[2 * k + 2]); self.dat[k] %= self.mod_; } } /* [a, b) (note: half-inclusive) * http://proc-cpuinfo.fixstars.com/2017/07/optimize-segment-tree/ */ pub fn query(&self, mut a: usize, mut b: usize) -> i64 { let mut left = self.e; let mut right = self.e; a += self.n - 1; b += self.n - 1; while a < b { if (a & 1) == 0 { left = (self.op)(left, self.dat[a]); left %= self.mod_; } if (b & 1) == 0 { right = (self.op)(self.dat[b - 1], right); right %= self.mod_; } a = a / 2; b = (b - 1) / 2; } let mut res = (self.op)(left, right); res %= self.mod_; res } } fn modpow2(x:usize, n:usize) -> usize{ let mut ans = 1; let mut n = n; let mut x = x; while(n != 0){ if (n&1 == 1){ans = ans*x%MODu;} x = x*x%MODu; n = n>>1; } ans } #[derive(Clone)] struct PPUnionFind{ par:Vec<usize>, rank:Vec<usize>, time:Vec<usize>, now:usize, history:Vec<(usize, usize)>, } impl PPUnionFind{ fn init(n:usize) -> PPUnionFind{ let mut par = vec![0;n]; for i in 0..n{ par[i] = i; } PPUnionFind{ par:par, rank:vec![0;n], time:vec![INF as usize;n], now:0, history:vec![], } } fn find(&mut self, t:usize, x:usize) ->usize{ if self.time[x] > t{return x;} else { let tt = self.par[x]; return self.find(t, tt);} } fn unite(&mut self, x:usize, y:usize) -> usize{ self.now+=1; let mut x = x; let mut y = y; let nc = self.now; x = self.find(nc, x); y = self.find(nc, y); if x == y{return self.now;} if self.par[x] < self.par[y] {mem::swap(&mut x, &mut y);} self.par[x] += self.par[y]; self.history.push((self.now, self.par[x])); self.par[y] = x; self.time[y] = self.now; return self.now; } } fn prim(cost:&Vec<Vec<(usize, i64)>>, vs:usize)->i64{ let mut used = vec![false; vs]; let mut bh = BinaryHeap::new(); for j in 0..cost[0].len(){ bh.push((cost[0][j].1 * -1, cost[0][j].0)); } used[0] = true; let mut res = 0; while(bh.len()!=0){ let mut m = bh.pop().unwrap(); if used[m.1]{continue;} used[m.1] = true; for e in 0..cost[m.1].len(){ if used[cost[m.1][e].0] == false{ bh.push((cost[m.1][e].1 * -1, cost[m.1][e].0)); } } res += m.0*-1; } return res; } fn kruscal(cost:&mut Vec<(i64, usize, usize)>, vs:usize)->i64{ cost.sort(); let mut uf = UnionFind::init(vs); let mut res = 0; for i in 0..cost.len(){ let e = cost[i].clone(); if uf.find(e.1) != uf.find(e.2){ uf.unite(e.1, e.2); res += e.0; } } return res; } fn kruscal3(cost:&mut Vec<(f64, usize, usize, usize)>, vs:usize)->(UnionFind, Vec<usize>) { cost.sort_by(|a, b| (&a.0).partial_cmp(&b.0).unwrap()); let mut uf = UnionFind::init(vs); let mut res = 0.0; let mut rv = Vec::new(); let mut c = 0.0; let mut t = 0.0; for i in 0..cost.len(){ let e = cost[i].clone(); if uf.find(e.1) != uf.find(e.2){ uf.unite(e.1, e.2); rv.push(e.3); } } return (uf,rv); } fn kruscal2(cost:&mut Vec<(f64, usize, usize)>, vs:usize)->f64{ cost.sort_by(|a, b| (&a.0).partial_cmp(&b.0).unwrap()); let mut uf = UnionFind::init(vs); let mut res = 0.0; for i in 0..cost.len(){ let e = cost[i].clone(); if uf.find(e.1) != uf.find(e.2){ uf.unite(e.1, e.2); res+= e.0; } } return res; } struct segtree<I, Op>{ n: usize, dat: Vec<I>, op:Op, e:I, } impl<I, Op> segtree<I, Op> where Op: Fn(I, I) -> I, I:Copy{ pub fn new(n_:usize, op: Op, e:I)->Self{ let mut n = 1; while(n<n_){n*=2;} segtree{n: n, dat:vec![e; 2*n-1], op:op, e:e} } pub fn update(&mut self, k:usize, a:I){ let mut k = k; k += self.n-1; self.dat[k] = a; while(k>0){ k = (k-1)/2; self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]); } } pub fn query(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{ if r<=a || b<=l{return self.e;} if a<=l && r<=b{return self.dat[k];} else{ let mut vl = self.query(a, b, k*2+1, l, (l+r)/2); let mut vr = self.query(a, b, k*2+2, (l+r)/2, r); return (self.op)(vl, vr); } } } struct BIT<I, Op>{ n:usize, bit:Vec<I>, op:Op, e:I, ini:I, } impl <I, Op> BIT<I, Op> /* 1-index*/ where Op: Fn(I, I) -> I, I:Copy{ pub fn new(n_:usize, op:Op, e:I, ini:I)->Self{ BIT{n:n_, bit:vec![e;n_+1], op:op, e:e, ini:ini} } pub fn sum(&self, i:usize)->I{ let mut s = self.ini; let mut i = i as i64; while(i>0){ s = (self.op)(s, self.bit[i as usize]); i -= i & -i; } return s; } pub fn add(&mut self, i:usize, x:I){ let mut i = i as i64; while(i<=self.n as i64){ self.bit[i as usize] = (self.op)(self.bit[i as usize], x); i += i & -i; } } } struct Dsegtree{ n: usize, datA: Vec<i64>, datB:Vec<i64>, e:i64, } impl Dsegtree{ pub fn new(n_:usize, e:i64)->Self{ Dsegtree{n:n_, datA:vec![e; 1<<22 - 1], datB:vec![e;1<<22 - 1], e:e} } pub fn update(&mut self,a:usize, b:usize, x:i64, k:usize, l:usize, r:usize){ //println!("{} {} {} {} {} {}", a, b, x, k , l, r); if a<=l && r<=b{ self.datA[k] += x; } else if (l<b && a<r){ self.datB[k] += (cmp::min(b, r) as i64 - cmp::max(a, l) as i64) * x; self.update(a, b, x, k*2+1, l, (l+r)/2); self.update(a, b, x, k*2+2, (l+r)/2, r); } } pub fn query(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> i64{ if (b<=l || r<=a){ return 0; } else if (a<=l && r<=b){ return self.datA[k] * ((r as i64-l as i64)) + self.datB[k]; } else{ let mut res = (cmp::min(b, r) as i64 - cmp::max(a, l) as i64)* self.datA[k]; res += self.query(a, b, k*2+1, l, (l+r)/2); res += self.query(a, b, k*2+2, (l+r)/2, r); return res; } } } /* unwrap_or_else */ fn prime_factor(n:usize)->HashMap<usize, usize>{ let mut res = HashMap::new(); let mut n = n; for i in 2..n{ if i*i>n{break;} while(n%i==0){ *res.entry(i).or_insert(0)+=1; n/=i; } } if n != 1{ res.insert(n, 1); } res } struct rollinghash{ base:Vec<i64>, Mod:Vec<i64>, hash:Vec<Vec<i64>>, power:Vec<Vec<i64>>, } impl rollinghash{ pub fn new(s:&Vec<usize>)->Self{ let mut n = s.len(); let mut base = vec![1007, 2009]; let mut hash = vec![vec![0;n+1];2]; let mut power = vec![vec![1;n+1];2]; let mut Mod = vec![1000000007, 1000000009]; for iter in 0..2{ let mut ht = vec![0;n+1]; let mut pt = vec![1;n+1]; for i in 0..n{ hash[iter][i+1] = (hash[iter][i] * base[iter] + s[i] as i64) % Mod[iter]; power[iter][i+1] = power[iter][i] * base[iter] % Mod[iter]; } } return rollinghash{base:base, Mod:Mod, hash:hash, power:power} } pub fn get(&self, l:usize, r:usize)->(i64, i64){ let mut res = self.hash[0][r] - self.hash[0][l] * self.power[0][r-l] % self.Mod[0]; if res<0{ res += self.Mod[0]; } let mut res2 = self.hash[1][r] - self.hash[1][l] * self.power[1][r-l] % self.Mod[1]; if res2<0{ res2 += self.Mod[1]; } return (res, res2); } } struct LCA{ G:Vec<Vec<i64>>, parent:Vec<Vec<i64>>, depth:Vec<i64>, root:i64, } impl LCA{ pub fn new(G:Vec<Vec<i64>>, N:i64,R:i64)->Self{ let D = (f64::log2(N as f64)) as i64 + 2; LCA{G:G, parent:vec![vec![0;N as usize];1+D as usize], depth:vec![0;N as usize], root:R} } pub fn getP(&mut self, v:i64, p:i64, d:i64){ self.parent[0][v as usize] = p; self.depth[v as usize] = d; for i in 0..self.G[v as usize].len(){ if self.G[v as usize][i as usize] != p{ let n = self.G[v as usize][i as usize]; self.getP(n, v, d+1); } } } pub fn init(&mut self){ let root = self.root; self.getP(root, -1, 0); let V = self.depth.len(); let logN = f64::log2(V as f64) as i64 + 2; for k in 0..logN{ for v in 0..V{ if self.parent[k as usize][v as usize] <0{ self.parent[k as usize+1][v as usize] = -1; } else{ self.parent[k as usize+1][v as usize] = self.parent[k as usize][ (self.parent[k as usize][v as usize]) as usize]; } } } } fn ft(&self, f:i64, d:i64)->i64{ let mut now = f; let mut now2 = 0; let V = self.depth.len(); let logN = f64::log2(V as f64) as i64 + 2; let mut v = f; for k in 0..logN{ if (d >> k) & 1 == 1{ v = self.parent[k as usize][v as usize]; } } return v; } fn lca(&mut self,u:i64, v:i64)->i64{ let mut u = u; let mut v = v; if self.depth[u as usize] > self.depth[v as usize]{ mem::swap(&mut u, &mut v); } let mut V = self.depth.len(); let logN = f64::log2(V as f64) as i64 + 2; for k in 0..logN{ if ((self.depth[v as usize] - self.depth[u as usize]) >> k)&1 == 1{ v = self.parent[k as usize][v as usize]; } } if u == v{return u;} for k in (0..logN).rev(){ if self.parent[k as usize][u as usize] != self.parent[k as usize][v as usize]{ u = self.parent[k as usize][u as usize]; v = self.parent[k as usize][v as usize]; } } return self.parent[0][u as usize]; } fn dist(&mut self,u:i64, v:i64)->i64{ let lc = self.lca(u, v); return self.depth[u as usize] + self.depth[v as usize] - 2* self.depth[lc as usize]; } } fn fast_prime_factor_table(ma:usize)->Vec<usize>{ let mut p = sieve(1001); let mut minf = vec![0;ma]; for j in 0..p.1.len(){ let P = p.1[j]; let mut now = P; for i in 2..ma{ if minf[now] ==0{ minf[now] = P; } now+=P; if now>=ma{ break; } } } return minf; } fn area_rectanble(x1:f64, x2:f64, x3:f64, y1:f64, y2:f64, y3:f64)->f64{ let tmp = x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1; tmp.abs()/2.0 } #[derive(PartialEq, Clone)] struct FW(f64); impl Eq for FW {} impl PartialOrd for FW { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.0.partial_cmp(&other.0) } } impl Ord for FW { fn cmp(&self, other: &FW) -> Ordering { other.partial_cmp(self).unwrap() } } /* parsing fn expr(s:&Vec<char>, i:&mut usize) -> Vec<usize>{ let mut val = term(s, i); while(*i<s.len() && (s[*i] == '+' || s[*i] == '-')){ let mut op = encode(s[*i]); *i+=1; let mut val2 = term(s, i); val = cal(val, val2, op); } return val; } fn term(s:&Vec<char>, i:&mut usize) -> Vec<usize>{ let mut val = factor(s, i); while(*i<s.len() && s[*i] == '*'){ let mut op = encode(s[*i]); *i+=1; let mut val2 = factor(s, i); val = cal(val, val2, op); } return val; } fn factor(s:&Vec<char>, i:&mut usize)->Vec<usize>{ if s[*i] == 'R' || s[*i] == 'S' || s[*i] == 'P' || s[*i] == '?'{ let mut res = encode(s[*i]); *i+=1; return res; } *i+=1; let mut ret = expr(s, i); *i+=1; return ret; } */ fn matmulf64(A:&Vec<Vec<f64>>, B:&Vec<Vec<f64>>) -> Vec<Vec<f64>>{ let mut C = vec![vec![0.0;B[0].len()];A.len()]; for i in 0..A.len(){ for k in 0..B.len(){ for j in 0..B[0].len(){ C[i][j] += A[i][k]*B[k][j]; } } } return C; } //sort_by_key(|a| vec![a[0], -a[1]]); //v.sort_by(|a, b| a.partial_cmp(b).unwrap()); fn fact_mod(n:usize)->usize { let mut f = 1; for i in 2..n+1{ f = f * (i % MODu) % MODu; } return f; } fn mod_pow(x:usize, n:usize) ->usize{ if(n == 0){ return 1;} let mut res = mod_pow((x * x) % MODu, n / 2 ); if(n & 1 == 1){ res = (res * x) % MODu;} return res; } fn comb2(n:usize, r:usize)->usize { let mut n = n; let mut r = r; if(r > n-r) {r = n-r;} if(r == 0) {return 1;} let mut a = 1; for i in 0..r{ a = a * ((n-i) % MODu) % MODu; } let mut b = mod_pow(fact_mod(r), MODu-2); return (a % MODu) * (b % MODu) % MODu; } struct scc{ G:Vec<Vec<usize>>, rG:Vec<Vec<usize>>, vs:Vec<usize>, used:Vec<bool>, cmp:Vec<usize>, } impl scc{ pub fn new(N:usize, G:&Vec<Vec<usize>>, rG:&Vec<Vec<usize>>)->Self{ scc{G:G.clone(), rG:rG.clone(), vs:vec![], used:vec![false;N], cmp:vec![0;N]} } pub fn add_edge(&mut self, from:usize, to:usize){ self.G[from].push(to); self.rG[to].push(from); } pub fn dfs(&mut self, v:usize){ self.used[v] = true; for i in 0..self.G[v].len(){ let t = self.G[v][i]; if !self.used[t]{ self.dfs(t); } } self.vs.push(v); } pub fn rdfs(&mut self, v:usize, k:usize){ self.used[v] = true; self.cmp[v] = k; for i in 0..self.rG[v].len(){ let t = self.rG[v][i]; if !self.used[t]{ self.rdfs(t, k); } } } pub fn scc(&mut self)->usize{ for v in 0..self.G.len(){ if !self.used[v]{ self.dfs(v); } } self.used = vec![false;self.used.len()]; let mut k = 0; for i in (0..self.vs.len()).rev(){ if !self.used[self.vs[i]]{ let t = self.vs[i]; self.rdfs(t, k); k+=1; } } k } } #[macro_use] fn modpow3(x:usize, n:usize,m:usize) -> usize{ let mut ans = 1; let mut n = n; let mut x = x; x%=m; while(n != 0){ if (n&1 == 1){ans = ans*x%m;} x = x*x%m; n = n>>1; } ans%m } fn cal1(x:usize, n:usize, m:usize, h:&mut HashMap<usize, usize>)->usize{ if h.contains_key(&n){ return h[&n]; } if n == 1{ return x; } if n == 0{ return 0; } let mut res = 0; let mut a = n/2; let mut b = n-a; res = cal1(x, b, m, h)%m; res = ((res*modpow3((10)%m, a*x.to_string().len(), m)%m)%m + cal1(x, a, m, h)%m)%m; h.insert(n, res); return res; } fn cal2(x:usize, n:usize, m:usize, h:&mut HashMap<usize, usize>, l:usize)->usize{ if h.contains_key(&n){ return h[&n]; } if n == 1{ return x; } if n == 0{ return 0; } let mut res = 0; let mut a = n/2; let mut b = n-a; res = cal2(x, b, m, h, l)%m; res = ((res*modpow3((10)%m, a*l, m)%m)%m + cal2(x, a, m, h, l)%m)%m; h.insert(n, res); return res; } fn modinv3(a:usize, m:usize)->usize{ let mut a = a as usize; let mut b = m as i64; let mut u = 1 as i64; let mut v = 0 as i64; let mut a = a as i64; let mut m = m as i64; while(b>0){ let mut t = a/b; a -= t*b; mem::swap(&mut a, &mut b); u-=t*v; mem::swap(&mut u, &mut v); } u%=m; if u<0{u+=m;} return u as usize; } fn dijkstra(s:usize, g:&Vec<Vec<(usize, i64)>>)->Vec<i64>{ let mut dist = vec![INF;g.len()]; dist[s] = 0; let mut h = BinaryHeap::new(); h.push((0, s)); while(h.len() != 0){ let mut t = h.pop().unwrap(); let mut d = t.0 * -1; let mut v = t.1; if dist[v]<d{ continue; } for i in 0..g[v].len(){ let n = g[v][i].0; let dd = g[v][i].1; if dist[n]>d+dd{ dist[n] = d+dd; h.push((dist[n]*-1, n)); } } } return dist; } fn dijkstra2(s:usize, g:&Vec<Vec<(usize, i64)>>)->Vec<i64>{ let mut dist = vec![INF;g.len()]; dist[s] = 0; let mut h = BinaryHeap::new(); h.push((0, s)); while(h.len() != 0){ let mut t = h.pop().unwrap(); let mut d = t.0 * -1; let mut v = t.1; if dist[v]<d{ continue; } for i in 0..g[v].len(){ let n = g[v][i].0; let dd = g[v][i].1; if dist[n]>d+dd{ dist[n] = d+dd; h.push((dist[n]*-1, n)); } } } return dist; } fn solve(){ let sssss = std::io::stdin(); let mut sc = Scanner { stdin: sssss.lock() }; let mut N:usize = sc.read(); let mut Q:usize = sc.read(); fn xxx(a:usize, b:usize)->usize{ a^b } let mut st = segtree::new(N, xxx, 0); for i in 0..N{ let mut t:usize = sc.read(); st.update(i, t); } for i in 0..Q{ let mut l:usize = sc.read(); let mut r:usize= sc.read(); l-=1; println!("{}", st.query(l, r, 0,0,st.n)); } } fn main(){ solve(); } const PI:f64 = std::f64::consts::PI; pub static MOD:i64 = 1000000007; pub static MODu:usize = 1000000007; pub static MODi32:i32 = 1000000007; pub static eps:f64 = 1e-6; const INF: i64 = 1 << 62; const INFu:usize = 1<<62;