結果

問題 No.876 Range Compress Query
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-09-03 15:15:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,123 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 93,800 KB
最終ジャッジ日時 2024-11-23 18:44:13
合計ジャッジ時間 7,346 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,292 KB
testcase_01 WA -
testcase_02 AC 48 ms
63,500 KB
testcase_03 WA -
testcase_04 AC 57 ms
65,664 KB
testcase_05 AC 55 ms
66,612 KB
testcase_06 AC 78 ms
75,932 KB
testcase_07 WA -
testcase_08 AC 76 ms
76,176 KB
testcase_09 WA -
testcase_10 AC 74 ms
75,812 KB
testcase_11 AC 498 ms
89,236 KB
testcase_12 AC 563 ms
89,160 KB
testcase_13 AC 569 ms
89,148 KB
testcase_14 AC 505 ms
89,120 KB
testcase_15 AC 505 ms
91,312 KB
testcase_16 AC 594 ms
93,800 KB
testcase_17 AC 508 ms
93,216 KB
testcase_18 AC 603 ms
93,516 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/876

種類数(分断されている場合別カウント)を計算 + 区間更新を処理
xを足して、同じ、違うになる可能性があるのは端のみ
区間内の句切れ目の数+1が答え
和のセグ木を保存しておけばおk

"""

#0-indexed , 半開区間[a,b)
#calc変更で演算変更
class SegTree:

    def __init__(self,N,first):
        self.NO = 2**(N-1).bit_length()
        self.First = first
        self.data = [first] * (2*self.NO)

    def calc(self,l,r):
        return l+r

    def update(self,ind,x):
        ind += self.NO - 1
        self.data[ind] = x
        while ind >= 0:
            ind = (ind - 1)//2
            self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2])

    def query(self,l,r):
        L = l + self.NO
        R = r + self.NO
        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s , self.data[R-1])
            if L & 1:
                s = self.calc(s , self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

class RangeBIT:

    def __init__(self,N,indexed):
        self.bit1 = [0] * (N+2)
        self.bit2 = [0] * (N+2)
        self.mode = indexed

    def bitadd(self,a,w,bit): #aにwを加える(1-origin)
 
        x = a
        while x <= (len(bit)-1):
            bit[x] += w
            x += x & (-1 * x)
 
    def bitsum(self,a,bit): #ind 1～aまでの和を求める
 
        ret = 0
        x = a
        while x > 0:
            ret += bit[x]
            x -= x & (-1 * x)
        return ret
    
    def add(self,l,r,w): #半開区間[l,r)にwを加える

        l = l + (1-self.mode)
        r = r + (1-self.mode)
        self.bitadd(l,-1*w*l,self.bit1)
        self.bitadd(r,w*r,self.bit1)
        self.bitadd(l,w,self.bit2)
        self.bitadd(r,-1*w,self.bit2)

    def sum(self,l,r): #半開区間[l,r)の区間和

        l = l + (1-self.mode)
        r = r + (1-self.mode)
        #print ("s",l,r)
        ret =  self.bitsum(r,self.bit1) + r * self.bitsum(r,self.bit2)
        ret -= self.bitsum(l,self.bit1) + l * self.bitsum(l,self.bit2)

from sys import stdin
N,Q = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))

ST = RangeBIT(N,0)
RT = SegTree(N,0)
for i in range(N):
    ST.add(i,i+1,a[i])

#print (RT.data)
for i in range(N-1):
    if a[i] != a[i+1]:
        RT.update(i,1)
#print (RT.data)

for loop in range(Q):

    q = stdin.readline()
    if q[0] == "1":
        s,l,r,x = map(int,q.split())
        l -= 1 ; r -= 1
        
        if l - 1 >= 0 and RT.query(l-1,l) == 1:
            RT.update(l-1,0)
        if RT.query(r,r+1) == 1:
            RT.update(r,0)
        
        ST.add(l,r+1,x)
        if l-1 >= 0 and ST.sum(l-1,l) == ST.sum(l,l+1):
            RT.update(l-1,1)
        if r+1 < N and ST.sum(r,r+1) == ST.sum(r+1,r+2):
            RT.update(r,1)
    else:
        s,l,r = map(int,q.split())
        l -= 1 ; r -= 1
        if l == r:
            print (1)
        else:
            print (RT.query(l,r)+1)
0