class LazySegmentTree(): def __init__(self, n, f, g, merge, ef, eh): self.n = n self.f = f self.g = lambda xh, x: g(xh, x) if xh != eh else x self.merge = merge self.ef = ef self.eh = eh l = (self.n - 1).bit_length() self.size = 1 << l self.tree = [self.ef] * (self.size << 1) self.lazy = [self.eh] * ((self.size << 1) + 1) self.plt_cnt = 0 def build(self, array): """ bulid seg tree from array """ for i in range(self.n): self.tree[self.size + i] = array[i] for i in range(self.size - 1, 0, -1): self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1]) def update(self, i, x): """ update (=replace) st[i] by x NOT update_range(i,i+1) """ i += self.size self.propagate_lazy(i) self.tree[i] = x self.lazy[i] = self.eh self.propagate_tree(i) def get(self, i): i += self.size self.propagate_lazy(i) return self.g(self.lazy[i], self.tree[i]) def update_range(self, l, r, x): """ act op(x, a) on elements a in [l, r) ( 0-indexed ) ( O(logN) ) """ if l >= r: return l += self.size r += self.size l0 = l//(l&-l) r0 = r//(r&-r) self.propagate_lazy(l0) self.propagate_lazy(r0-1) while l < r: if r&1: r -= 1 self.lazy[r] = self.merge(x, self.lazy[r]) if l&1: self.lazy[l] = self.merge(x, self.lazy[l]) l += 1 l >>= 1 r >>= 1 self.propagate_tree(l0) self.propagate_tree(r0-1) def get_range(self, l, r): """ get value from [l, r) (0-indexed) """ l += self.size r += self.size self.propagate_lazy(l//(l&-l)) self.propagate_lazy((r//(r&-r))-1) res_l = self.ef res_r = self.ef while l < r: if l & 1: res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l])) l += 1 if r & 1: r -= 1 res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r) l >>= 1 r >>= 1 return self.f(res_l, res_r) def max_right(self,l,func): """ return r such that ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false """ if l >= self.n: return self.n l += self.size s = self.ef while 1: while l % 2 == 0: l >>= 1 if not func(self.f(s,self.g(self.lazy[l],self.tree[l]))): while l < self.size: l *= 2 if func(self.f(s,self.g(self.lazy[l],self.tree[l]))): s = self.f(s, self.g(self.lazy[l], self.tree[l])) l += 1 return l - self.size s = self.f(s, self.g(self.lazy[l], self.tree[l])) l += 1 if l & -l == l: break return self.n def min_left(self,r,func): """ return l such that ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false """ if r <= 0: return 0 r += self.size s = self.ef while 1: r -= 1 while r > 1 and r % 2: r >>= 1 if not func(self.f(self.g(self.lazy[r],self.tree[r]),s)): while r < self.size: r = r * 2 + 1 if func(self.f(self.g(self.lazy[r],self.tree[r]),s)): s = self.f(self.g(self.lazy[r], self.tree[r]), s) r -= 1 return r + 1 - self.size s = self.f(self.g(self.lazy[r], self.tree[r]), s) if r & -r == r: break return 0 def propagate_lazy(self, i): for k in range(i.bit_length()-1,0,-1): x = i>>k if self.lazy[x] == self.eh: continue laz = self.lazy[x] self.lazy[(x<<1)|1] = self.merge(laz, self.lazy[(x << 1) | 1]) self.lazy[x<<1] = self.merge(laz, self.lazy[x << 1]) self.tree[x] = self.g(laz, self.tree[x]) self.lazy[x] = self.eh def propagate_tree(self, i): while i>1: i>>=1 self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1])) def __getitem__(self, i): if i<0: i=self.n+i return self.get(i) def __setitem__(self, i, value): if i<0: i=self.n+i self.update(i,value) def __iter__(self): for x in range(1, self.size): if self.lazy[x] == self.eh: continue self.lazy[(x<<1)|1] = self.merge(self.lazy[x], self.lazy[(x << 1) | 1]) self.lazy[x<<1] = self.merge(self.lazy[x], self.lazy[x << 1]) self.tree[x] = self.g(self.lazy[x], self.tree[x]) self.lazy[x] = self.eh for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]): yield self.g(xh,x) def __str__(self): return str(list(self)) def debug(self): def full_tree_pos(G): n = G.number_of_nodes() if n == 0: return {} pos = {0: (0.5, 0.9)} if n == 1: return pos i = 1 while not n >= 2 ** i or not n < 2 ** (i + 1): i+=1 height = i p_key, p_y, p_x = 0, 0.9, 0.5 l_child = True for i in range(height): for j in range(2 ** (i + 1)): if 2 ** (i + 1) + j - 1 < n: if l_child == True: pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1) G.add_edge(2 ** (i + 1) + j - 1, p_key) l_child = False else: pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1) l_child = True G.add_edge(2 ** (i + 1) + j - 1, p_key) p_key += 1 (p_x, p_y) = pos[p_key] return pos import networkx as nx import matplotlib.pyplot as plt A = self.tree[1:] G = nx.Graph() labels = {} for i, a in enumerate(A): G.add_node(i) labels[i] = a pos = full_tree_pos(G) nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000) plt.savefig("tree-{0}.png".format(self.plt_cnt)) plt.clf() A = self.lazy[1:-1] G = nx.Graph() labels = {} for i, a in enumerate(A): G.add_node(i) labels[i] = a pos = full_tree_pos(G) nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000) plt.savefig("lazy-{0}.png".format(self.plt_cnt)) plt.clf() self.plt_cnt += 1 def max2(x,y): return x if x > y else y def min2(x,y): return x if x < y else y ############################################################# import sys from bisect import * from collections import Counter input = sys.stdin.readline def example(): global input example = iter( """ 2 1 1 0 2 """ .strip().split("\n")) input = lambda: next(example) # example() N,A,B=map(int, input().split()) X=list(map(int, input().split())) ####### 更新:代入 取得:min ######################################################## # get chain rule def f(x,y): return x if x < y else y ef = 10**6 # merge of update def merge(a,b): return a if a != eh else b eh = -1 # update chain rule def g(a,x): return a st = LazySegmentTree(N, f, g, merge, ef, eh) ################################################################################ st.build([i for i in range(N)]) for i in range(N): x=X[i] l=bisect_left(X,x+A) r=bisect_right(X,x+B) k=min2(st.get_range(l,min2(r,N)),st.get(i)) st.update_range(l,min2(r,N),k) st.update_range(i,i+1,k) C=Counter(st) for i in range(N): k=st.get(i) print(C[k])