結果
問題 | No.2879 Range Flip Queries |
ユーザー |
![]() |
提出日時 | 2024-09-08 12:41:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 444 ms / 2,000 ms |
コード長 | 6,021 bytes |
コンパイル時間 | 376 ms |
コンパイル使用メモリ | 82,700 KB |
実行使用メモリ | 163,088 KB |
最終ジャッジ日時 | 2024-09-08 12:42:04 |
合計ジャッジ時間 | 12,279 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
# oj t -c "python3 main.py"import sys,mathfrom collections import defaultdict,dequefrom itertools import combinations,permutations,accumulate,productfrom bisect import bisect_left,bisect_rightfrom heapq import heappop,heappush,heapify#from more_itertools import distinct_permutations,distinct_combinations#from sortedcontainers import SortedList,SortedSetdef input():return sys.stdin.readline().rstrip()def ii(): return int(input())def ms(): return map(int, input().split())def li(): return list(map(int,input().split()))inf = pow(10,18)mod = 998244353#/////////////////////////////////N,Q = ms()A = li()class lazy_segtree(): # すべて 0-indexdef _update(self,k):self.data[k]=self.op(self.data[2*k],self.data[2*k+1])def _all_apply(self,k,f):self.data[k]=self.mapping(f,self.data[k])if (k<self.size):self.lz[k]=self.composition(f,self.lz[k])def _push(self,k):self._all_apply(2*k,self.lz[k])self._all_apply(2*k+1,self.lz[k])self.lz[k]=self.identitydef __init__(self,V,OP,E,MAPPING,COMPOSITION,ID):self.n=len(V)self.log=(self.n-1).bit_length()self.size=1<<self.logself.data=[E for i in range(2*self.size)]self.lz=[ID for i in range(self.size)]self.e=Eself.op=OPself.mapping=MAPPINGself.composition=COMPOSITIONself.identity=IDfor i in range(self.n):self.data[self.size+i]=V[i]for i in range(self.size-1,0,-1):self._update(i)# 一点更新def set(self,p,x):assert 0<=p and p<self.np+=self.sizefor i in range(self.log,0,-1):self._push(p>>i)self.data[p]=xfor i in range(1,self.log+1):self._update(p>>i)# data[p] を取得するdef get(self,p):assert 0<=p and p<self.np+=self.sizefor i in range(self.log,0,-1):self._push(p>>i)return self.data[p]# 区間 [l,r) の演算結果を返すdef prod(self,l,r):assert 0<=l and l<=r and r<=self.nif l==r:return self.el+=self.sizer+=self.sizefor i in range(self.log,0,-1):if (((l>>i)<<i)!=l):self._push(l>>i)if (((r>>i)<<i)!=r):self._push(r>>i)sml,smr=self.e,self.ewhile(l<r):if l&1:sml=self.op(sml,self.data[l])l+=1if r&1:r-=1smr=self.op(self.data[r],smr)l>>=1r>>=1return self.op(sml,smr)# 全区間の演算結果を返すdef all_prod(self):return self.data[1]# 一点に対して操作する# あんまわからんdef apply_point(self,p,f):assert 0<=p and p<self.np+=self.sizefor i in range(self.log,0,-1):self._push(p>>i)self.data[p]=self.mapping(f,self.data[p])for i in range(1,self.log+1):self._update(p>>i)# 区間操作# f は mapping に与える引数の fdef apply(self,l,r,f):assert 0<=l and l<=r and r<=self.nif l==r:returnl+=self.sizer+=self.sizefor i in range(self.log,0,-1):if (((l>>i)<<i)!=l):self._push(l>>i)if (((r>>i)<<i)!=r):self._push((r-1)>>i)l2,r2=l,rwhile(l<r):if (l&1):self._all_apply(l,f)l+=1if (r&1):r-=1self._all_apply(r,f)l>>=1r>>=1l,r=l2,r2for i in range(1,self.log+1):if (((l>>i)<<i)!=l):self._update(l>>i)if (((r>>i)<<i)!=r):self._update((r-1)>>i)# check(operate(data[l],data[l+1],...,data[r-1])) = True# を満たす最大の r を返すdef max_right(self,l,check):assert 0<=l and l<=self.nassert check(self.e)if l==self.n:return self.nl+=self.sizefor i in range(self.log,0,-1):self._push(l>>i)sm=self.ewhile(1):while(l%2==0):l>>=1if not(check(self.op(sm,self.data[l]))):while(l<self.size):self._push(l)l=(2*l)if (check(self.op(sm,self.data[l]))):sm=self.op(sm,self.data[l])l+=1return l-self.sizesm=self.op(sm,self.data[l])l+=1if (l&-l)==l:breakreturn self.n# check(operate(data[l],data[l+1],...,data[r-1])) = True# を満たす最小の l を返すdef min_left(self,r,check):assert (0<=r and r<=self.n)assert check(self.e)if r==0:return 0r+=self.sizefor i in range(self.log,0,-1):self._push((r-1)>>i)sm=self.ewhile(1):r-=1while(r>1 and (r%2)):r>>=1if not(check(self.op(self.data[r],sm))):while(r<self.size):self._push(r)r=(2*r+1)if g(self.op(self.data[r],sm)):sm=self.op(self.data[r],sm)r-=1return r+1-self.sizesm=self.op(self.data[r],sm)if (r&-r)==r:breakreturn 0# data の単位元e = 0# lazy の単位元# 区間更新なら lazy としてとりえない値にするide = 0# 区間に対して行いたい演算def operate(a,b):return a+b# 遅延させていた操作をdataに伝搬させる関数# f が遅延させた操作、x がdata# ex. 区間加算なら f+xdef mapping(f,x):# 区間更新なら# if f==ide: return xreturn f+x# 既に遅延させていた操作にさらに操作を追加する関数# f が追加する操作、g がいままでの操作def composition(f,g):# 区間更新なら# if f==ide: return greturn f+gseg = lazy_segtree(A,operate,e,mapping,composition,ide)# セグ木壊れてる後でみなおす//////////////////acc = [0]*(N+1)for _ in range(Q):l,r = ms()l -= 1r -= 1acc[l] += 1acc[r+1] -= 1acc = list(accumulate(acc))for i in range(N):if acc[i]%2==0:print(A[i],end=" ")else:print(1-A[i],end=" ")print()