CPSCO2019 Session1 E - Exclusive OR Queries (python)
python だと難易度が爆上がりするやつ。
E - Exclusive OR Queries
CPSCOのsession1のEをPythonで通そうと頑張ってみたけどダメそうということがわかった(はい)(ごめんなさい)
— てんぷら (@tempura_cpp) May 12, 2019
本編まで飛ばしていいよ。
やるべき動作は
１．特定の範囲 [L,R] の XOR を出力する
２．[L,R] にある数字を全て削除する
３．[L,R] に存在する数の個数分だけ、ソートを維持して数 x を追加
ですが、これを全て log(N) とかでやってくれるものは python にはありません。
(実は近いものは存在していて後ろの方で書きます。）
まず、XOR の性質に注目すると、a^a = 0 なので、list(A) にある数字のなかで、k回でてくるものは k%2 回出てくると考えていいです。A = [1,2,2,3,3,3,4,4,4,4] なら A = [1,3] と出来るということです。
同じように x を追加する回数も 2 で割った余りだけ行えば十分です。
なので、動作２．はうまく A に存在しているものだけを削除することができれば、Q 回 1.~3. のの動作を行ったときに [L,R] に存在する数を求める回数は最大でも Q になることが分かります。
また、数字を削除するという動作は XOR の場合 a^0 = a なので、数字を 0 に置き換えるとして考えることができます。
なので区間取得・一点更新ができるセグ木と、BIT木の両方を導入して、
先にクエリを読み、A と x の種類の分だけ、セグ木で値を管理、BIT木で要素の数を管理することで、
１．→ セグ木で区間取得
２．→ BIT木で個数が i 以上になる最小の index 二分探索 → その index にあたる値、要素を0に更新
３．→ セグ木で一点更新、BITで一点更新（BIT木は更新そのものはできないので、加算をうまく使う）
でなんとか実現できます。
N = len(A) とすると計算量は
1 : O(Q*log(N+Q)), 2 : 最大 O(Q*log(N+Q)) 3 : log(N+Q) で、最初にクエリ先読みして座標圧縮する過程で O(Q), O(N+Q) 、区間を探すのに O(log(N+Q)) かかります。（多分）
ほんとにギリギリ耐えた。(2999ms)
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from bisect import bisect,bisect_left from collections import Counter n,q = map(int,readline().split()) a = list(map(int,readline().split())) c = Counter(a) s = set(a) chk = [] for i in range(q): l,r,x = map(int,readline().split()) chk.append([l,r,x]) s.add(x) s = sorted(list(s)) #座標圧縮 def compress(list1): list2 = sorted(set(list1)) memo = {value : index for index, value in enumerate(list2)} return memo, len(list2) memo, len_memo = compress(s) class Bit: # BIT def __init__(self, n): self.size = n self.tree = [0] * (n + 1) self.depth = n.bit_length() def sum(self, i): s = 0 while i > 0: s += self.tree[i] i -= i & -i return s def add(self, i, x): while i <= self.size: self.tree[i] += x i += i & -i def lower_bound(self, x): #累積和がx以上になる最小のindexを返す sum_ = 0 pos = 0 for i in range(self.depth, -1, -1): k = pos + (1 << i) if k <= self.size and sum_ + self.tree[k] < x: sum_ += self.tree[k] pos += 1 << i return pos + 1 class segment_(): def __init__(self,n,ide_ele,segfunc): self.ide_ele = ide_ele self.num = 1 << n.bit_length() self.seg = [self.ide_ele] * 2 * self.num self.segfunc = segfunc def update(self, k, r): k += self.num self.seg[k] = r while k: k >>= 1 self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1]) def query(self, p, q): # qは含まない if q < p: return self.ide_ele p += self.num; q += self.num res = self.ide_ele while p < q: if p & 1 == 1: res = self.segfunc(res, self.seg[p]) p += 1 if q & 1 == 1: q -= 1 res = self.segfunc(res, self.seg[q]) p >>= 1; q >>= 1 return res S = segment_(len_memo,0,lambda a, b: a^b) num = Bit(len_memo) for i in set(a): if c[i]%2 == 1: # ２で割った個数分だけ考えればいい ind = memo[i] num.add(ind+1,1) S.update(ind+1,i) for i in range(q): l,r,x = chk[i] L = bisect_left(s,l) #区間を求める R = bisect(s,r) if R > L: ans = S.query(L+1,R+1) # 1, 区間取得 sl = num.sum(L) #区間にある個数を求める ss = num.sum(R)-sl if ss > 0: hp = ss while hp > 0: # 2 ind = num.lower_bound(sl+1) #区間に存在する数を抽出 num.add(ind,-1) #削除する S.update(ind,0) #削除する hp -= 1 to = memo[x]+1 # 3 RR = num.sum(to) LL = num.sum(to-1) #ｘの個数が奇数になるなら 1 つだけｘが存在しているように更新 #ｘの個数が偶数になるなら ｘが存在していないように更新 if RR == LL: num.add(to,ss%2) S.update(to,ss%2*x) else: if (1+ss)%2 == 0: num.add(to,-1) S.update(to,(1+ss)%2*x) print(ans) else: print(0)
本編
python でも二分木そのものが使いたいよね。
これです。本当にきりさんありがとうございます。
平衡二分木を実装する - Qiita
これ一つで、
heap（ソートを維持して追加、最大最小出力）
特定の区間の最大最小の出力
一点削除
値が存在しているかの判定
ができるそうです。もう全部これでいいんじゃないかな。
今回は動作３．はそのままできるので、１. ２. がうまくできれば終わりです。
[L,R] に存在する数字は、特定の区間の最小値の出力を [L,R] で繰り返すことで過不足なく求めれるので、小さい順に XOR の計算と値の削除を並行して処理したら実現できます。
計算量もなんと座圧しなくても 1+2 : O(Q*log(log(max(A))))
3 : O(Q*log(log(max(A)))) ででき、前処理もないので普通に間に合います。
前処理して座圧すると、O(Q) + O(Q*log(log(Q+N))) + O(Q*log(log(Q+N))) とかになります。（多分）
出してみた。2043ms
Submission #14426077 - CPSCO2019 Session1
