結果

問題 No.2571 列辞書順列
ユーザー navel_tosnavel_tos
提出日時 2023-12-02 16:59:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,401 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 154,648 KB
最終ジャッジ日時 2024-09-27 03:42:47
合計ジャッジ時間 31,670 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#緑以下Ex-C

#Segment Tree: O(logN)
class SegmentTree:
    def __init__(self,n,identity_e,combine_f):
        self._n=n;self._size=2  #size=1だとbisectが不便
        while self._size<self._n:self._size<<=1
        self._identity_e=identity_e;self._combine_f=combine_f;self._node=[self._identity_e]*2*self._size
    def build(self,array):
        assert len(array)==self._n,'array too large'
        for i,v in enumerate(array,start=self._size):self._node[i]=v
        for i in range(self._size-1,0,-1):self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def update(self,index,value):  #一点更新
        i=self._size+index;self._node[i]=value
        while i-1:i>>=1;self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def fold(self,L,R):  #区間取得: [L,R)の区間値を得る
        L+=self._size;R+=self._size;vL,vR=[self._identity_e]*2
        while L<R:
            if L&1:vL=self._combine_f(vL,self._node[L]);L+=1
            if R&1:R-=1;vR=self._combine_f(self._node[R],vR)
            L>>=1;R>>=1
        return self._combine_f(vL,vR)
    #down: Falseなら単調増加、Trueなら単調減少を仮定する。
    #[0:Lt]の作用値がX以上/以下 となる、最小のLtを返す。閉区間なので扱い注意。
    def bisect(self,X,down=False):
        now=1; cnt=self._identity_e
        while now<self._size:
            Lt,Rt=self._node[now<<1|0],self._node[now<<1|1]
            if not down and self._combine_f(cnt,Lt)>=X: now=now<<1|0
            elif   down and self._combine_f(cnt,Lt)<=X: now=now<<1|0
            else: cnt=self._combine_f(cnt,Lt); now=now<<1|1
        return now-self._size


#入力受取
N,M,K,Q = map(int,input().split())
A = list(map(lambda x: int(x)-1, input().split()))
MOD = 998244353

#SegTreeに乗せる  TLきついがまずtuple型で乗せてみる
#node = (区間幅, 作用値, 作用値+1)
def node_f(Lt,Rt):
    global M,MOD
    L_dist,L_cnt,L_func = Lt
    R_dist,R_cnt,R_func = Rt
    M_cnt = L_cnt * pow(M,R_dist,MOD) % MOD + R_cnt % MOD
    return (L_dist + R_dist, M_cnt ,(L_func+R_func)%MOD)
ST = SegmentTree(N,(0,0,0),node_f)
ST.build([(1,i,i+1) for i in A])

#クエリを処理
for _ in range(Q):
    t,x,y = map(int,input().split())
    x -= 1
    if t==1:
        _,cnt,func = ST.fold(x,y)
        print((cnt+func+1)%MOD)
    if t==2: ST.update(x, (1,y-1,y))
0