import sys

class segTree():

    def __init__(self,arr,formula,identity_val):

        self.arr = arr

        self.formula = formula

        self.identity_val = identity_val

        self.n = len(arr)

        self.tree = [self.identity_val]*(4*self.n)

        if self.n > 0:

            self._build(0,0,self.n-1)

    def _build(self,node,start,end):

        if start == end:

            self.tree[node] = (self.arr[start],start)

            return

        mid = (start+end)//2

        self._build(2*node+1,start,mid)

        self._build(2*node+2,mid+1,end)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _update(self,node,start,end,idx,val):

        if start == end:

            self.tree[node] = (val,start)

            return

        mid = (start+end)//2

        if idx <= mid:

            self._update(2*node+1,start,mid,idx,val)

        else:

            self._update(2*node+2,mid+1,end,idx,val)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _query(self,node,start,end,left,right):

        if right < start or left > end:

            return self.identity_val

        if right >= end and left <= start:

            return self.tree[node]

        mid = (start+end)//2

        p1 = self._query(2*node+1,start,mid,left,right)

        p2 = self._query(2*node+2,mid+1,end,left,right)

        return self.formula(p1,p2)

    def update(self,idx,val):

        self._update(0,0,self.n-1,idx,val)

    def query(self,left,right):

        return self._query(0,0,self.n-1,left,right)

def mins(t1,t2):

    if t1[0] > t2[0]: return t2

    elif t1[0] < t2[0]: return t1

    else:

        if t1[1]>t2[1]: return t2

        else: return t1

def delete(idx,prev,next_):

    prev_index = prev[idx]

    next_index = next_[idx]

    if prev_index != -1:

        next_[prev_index] = next_index

    if next_index != -1:

        prev[next_index] = prev_index

n,t = list(map(int,sys.stdin.readline().split()))

data = list(map(int,sys.stdin.readline().split()))

prev = [-1]*n

next_ = [-1]*n

for i in range(n):

    if i > 0:

        prev[i] = i-1

    if i < n-1:

        next_[i] = i+1

score = 0

seg = segTree(data,formula=mins,identity_val=(float("inf"),float("inf")))

while True:

    challenge = seg.query(0,n-1)

    if challenge[0] > t:

        break

    score += challenge[0]

    seg.update(challenge[1],float("inf"))

    data[challenge[1]] = 0

    if next_[challenge[1]] != -1:

        target = data[next_[challenge[1]]]

        seg.update(next_[challenge[1]],target+challenge[0])

        data[next_[challenge[1]]] = target+challenge[0]

    delete(challenge[1],prev,next_) ###

print(score)

前4筆測資都能壓在20ms以內，但第五筆就tle了。

我是利用自己寫的segment_tree,和雙向鏈結串列來實作，理論上應該是O(n log n)

請求大神給點提示，告訴我哪裡有效能浪費。

Python 的線段樹常數超大，很容易TLE

這題n達到3e5

可以用heap+雙頭鏈結陣列實作

或者單調棧

import sys

class segTree():

    def __init__(self,arr,formula,identity_val):

        self.arr = arr

        self.formula = formula

        self.identity_val = identity_val

        self.n = len(arr)

        self.tree = [self.identity_val]*(4*self.n)

        if self.n > 0:

            self._build(0,0,self.n-1)

    def _build(self,node,start,end):

        if start == end:

            self.tree[node] = (self.arr[start],start)

            return

        mid = (start+end)//2

        self._build(2*node+1,start,mid)

        self._build(2*node+2,mid+1,end)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _update(self,node,start,end,idx,val):

        if start == end:

            self.tree[node] = (val,start)

            return

        mid = (start+end)//2

        if idx <= mid:

            self._update(2*node+1,start,mid,idx,val)

        else:

            self._update(2*node+2,mid+1,end,idx,val)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _query(self,node,start,end,left,right):

        if right < start or left > end:

            return self.identity_val

        if right >= end and left <= start:

            return self.tree[node]

        mid = (start+end)//2

        p1 = self._query(2*node+1,start,mid,left,right)

        p2 = self._query(2*node+2,mid+1,end,left,right)

        return self.formula(p1,p2)

    def update(self,idx,val):

        self._update(0,0,self.n-1,idx,val)

    def query(self,left,right):

        return self._query(0,0,self.n-1,left,right)

def mins(t1,t2):

    if t1[0] > t2[0]: return t2

    elif t1[0] < t2[0]: return t1

    else:

        if t1[1]>t2[1]: return t2

        else: return t1

def delete(idx,prev,next_):

    prev_index = prev[idx]

    next_index = next_[idx]

    if prev_index != -1:

        next_[prev_index] = next_index

    if next_index != -1:

        prev[next_index] = prev_index

n,t = list(map(int,sys.stdin.readline().split()))

data = list(map(int,sys.stdin.readline().split()))

prev = [-1]*n

next_ = [-1]*n

for i in range(n):

    if i > 0:

        prev[i] = i-1

    if i < n-1:

        next_[i] = i+1

score = 0

seg = segTree(data,formula=mins,identity_val=(float("inf"),float("inf")))

while True:

    challenge = seg.query(0,n-1)

    if challenge[0] > t:

        break

    score += challenge[0]

    seg.update(challenge[1],float("inf"))

    data[challenge[1]] = 0

    if next_[challenge[1]] != -1:

        target = data[next_[challenge[1]]]

        seg.update(next_[challenge[1]],target+challenge[0])

        data[next_[challenge[1]]] = target+challenge[0]

    delete(challenge[1],prev,next_) ###

print(score)

前4筆測資都能壓在20ms以內，但第五筆就tle了。

我是利用自己寫的segment_tree,和雙向鏈結串列來實作，理論上應該是O(n log n)

請求大神給點提示，告訴我哪裡有效能浪費。

Python 的線段樹常數超大，很容易TLE

這題n達到3e5

可以用heap+雙頭鏈結陣列實作

或者單調棧

我嘗試了heapq+雙向鏈結串列了，但zerojudge還是不給我過(TLE)，請問是我哪裡處理得不到位嗎?

import sys

class segTree():

    def __init__(self,arr,formula,identity_val):

        self.arr = arr

        self.formula = formula

        self.identity_val = identity_val

        self.n = len(arr)

        self.tree = [self.identity_val]*(4*self.n)

        if self.n > 0:

            self._build(0,0,self.n-1)

    def _build(self,node,start,end):

        if start == end:

            self.tree[node] = (self.arr[start],start)

            return

        mid = (start+end)//2

        self._build(2*node+1,start,mid)

        self._build(2*node+2,mid+1,end)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _update(self,node,start,end,idx,val):

        if start == end:

            self.tree[node] = (val,start)

            return

        mid = (start+end)//2

        if idx <= mid:

            self._update(2*node+1,start,mid,idx,val)

        else:

            self._update(2*node+2,mid+1,end,idx,val)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _query(self,node,start,end,left,right):

        if right < start or left > end:

            return self.identity_val

        if right >= end and left <= start:

            return self.tree[node]

        mid = (start+end)//2

        p1 = self._query(2*node+1,start,mid,left,right)

        p2 = self._query(2*node+2,mid+1,end,left,right)

        return self.formula(p1,p2)

    def update(self,idx,val):

        self._update(0,0,self.n-1,idx,val)

    def query(self,left,right):

        return self._query(0,0,self.n-1,left,right)

def mins(t1,t2):

    if t1[0] > t2[0]: return t2

    elif t1[0] < t2[0]: return t1

    else:

        if t1[1]>t2[1]: return t2

        else: return t1

def delete(idx,prev,next_):

    prev_index = prev[idx]

    next_index = next_[idx]

    if prev_index != -1:

        next_[prev_index] = next_index

    if next_index != -1:

        prev[next_index] = prev_index

n,t = list(map(int,sys.stdin.readline().split()))

data = list(map(int,sys.stdin.readline().split()))

prev = [-1]*n

next_ = [-1]*n

for i in range(n):

    if i > 0:

        prev[i] = i-1

    if i < n-1:

        next_[i] = i+1

score = 0

seg = segTree(data,formula=mins,identity_val=(float("inf"),float("inf")))

while True:

    challenge = seg.query(0,n-1)

    if challenge[0] > t:

        break

    score += challenge[0]

    seg.update(challenge[1],float("inf"))

    data[challenge[1]] = 0

    if next_[challenge[1]] != -1:

        target = data[next_[challenge[1]]]

        seg.update(next_[challenge[1]],target+challenge[0])

        data[next_[challenge[1]]] = target+challenge[0]

    delete(challenge[1],prev,next_) ###

print(score)

前4筆測資都能壓在20ms以內，但第五筆就tle了。

我是利用自己寫的segment_tree,和雙向鏈結串列來實作，理論上應該是O(n log n)

請求大神給點提示，告訴我哪裡有效能浪費。

Python 的線段樹常數超大，很容易TLE

這題n達到3e5

可以用heap+雙頭鏈結陣列實作

或者單調棧

import heapq,sys

n,t = list(map(int,sys.stdin.readline().split()))

data = list(map(int,sys.stdin.readline().split()))

heap = []

prev = [-1]*n

next_ = [-1]*n

score = 0

for i in range(n):

    heapq.heappush(heap,(data[i],i))

    if i > 0:

        prev[i] = i-1

    if i < (n-1):

        next_[i] = i+1

def delete(idx):

    prev_idx = prev[idx]

    next_idx = next_[idx]

    if prev_idx != -1:

        next_[prev_idx] = next_idx

    if next_idx != -1:

        prev[next_idx] = prev_idx

while heap:

    a = heapq.heappop(heap)

    if a[0] != data[a[1]]:

        continue

    if a[0] > t:

        break

    target = next_[a[1]]

    score += a[0]

    data[a[1]] = float("inf")

    if target != -1:

        data[target] += a[0]

        heapq.heappush(heap,(data[target],target))

    delete(a[1])

print(score)

我嘗試了heapq+雙向鏈結串列了，但zerojudge還是不給我過(TLE)，請問是我哪裡處理得不到位嗎?

如果你有看到下面那行說APCS 考試時Python 是3s的話，其實上面的code應該是有機會過的，但現在ZJ沒有3倍時限，要在1s內過O(nlogn)且n達到3e5是有難度的
而且這題會有更多資料進出heap

看來只能單調棧O(n)了

詳細解法可以參考超電的暴力又被TLE寫的詳解

import sys

class segTree():

    def __init__(self,arr,formula,identity_val):

        self.arr = arr

        self.formula = formula

        self.identity_val = identity_val

        self.n = len(arr)

        self.tree = [self.identity_val]*(4*self.n)

        if self.n > 0:

            self._build(0,0,self.n-1)

    def _build(self,node,start,end):

        if start == end:

            self.tree[node] = (self.arr[start],start)

            return

        mid = (start+end)//2

        self._build(2*node+1,start,mid)

        self._build(2*node+2,mid+1,end)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _update(self,node,start,end,idx,val):

        if start == end:

            self.tree[node] = (val,start)

            return

        mid = (start+end)//2

        if idx <= mid:

            self._update(2*node+1,start,mid,idx,val)

        else:

            self._update(2*node+2,mid+1,end,idx,val)

        self.tree[node] = self.formula(self.tree[2*node+1],self.tree[2*node+2])

    def _query(self,node,start,end,left,right):

        if right < start or left > end:

            return self.identity_val

        if right >= end and left <= start:

            return self.tree[node]

        mid = (start+end)//2

        p1 = self._query(2*node+1,start,mid,left,right)

        p2 = self._query(2*node+2,mid+1,end,left,right)

        return self.formula(p1,p2)

    def update(self,idx,val):

        self._update(0,0,self.n-1,idx,val)

    def query(self,left,right):

        return self._query(0,0,self.n-1,left,right)

def mins(t1,t2):

    if t1[0] > t2[0]: return t2

    elif t1[0] < t2[0]: return t1

    else:

        if t1[1]>t2[1]: return t2

        else: return t1

def delete(idx,prev,next_):

    prev_index = prev[idx]

    next_index = next_[idx]

    if prev_index != -1:

        next_[prev_index] = next_index

    if next_index != -1:

        prev[next_index] = prev_index

n,t = list(map(int,sys.stdin.readline().split()))

data = list(map(int,sys.stdin.readline().split()))

prev = [-1]*n

next_ = [-1]*n

for i in range(n):

    if i > 0:

        prev[i] = i-1

    if i < n-1:

        next_[i] = i+1

score = 0

seg = segTree(data,formula=mins,identity_val=(float("inf"),float("inf")))

while True:

    challenge = seg.query(0,n-1)

    if challenge[0] > t:

        break

    score += challenge[0]

    seg.update(challenge[1],float("inf"))

    data[challenge[1]] = 0

    if next_[challenge[1]] != -1:

        target = data[next_[challenge[1]]]

        seg.update(next_[challenge[1]],target+challenge[0])

        data[next_[challenge[1]]] = target+challenge[0]

    delete(challenge[1],prev,next_) ###

print(score)

前4筆測資都能壓在20ms以內，但第五筆就tle了。

我是利用自己寫的segment_tree,和雙向鏈結串列來實作，理論上應該是O(n log n)

請求大神給點提示，告訴我哪裡有效能浪費。

Python 的線段樹常數超大，很容易TLE

這題n達到3e5

可以用heap+雙頭鏈結陣列實作

或者單調棧

import heapq,sys

n,t = list(map(int,sys.stdin.readline().split()))

data = list(map(int,sys.stdin.readline().split()))

heap = []

prev = [-1]*n

next_ = [-1]*n

score = 0

for i in range(n):

    heapq.heappush(heap,(data[i],i))

    if i > 0:

        prev[i] = i-1

    if i < (n-1):

        next_[i] = i+1

def delete(idx):

    prev_idx = prev[idx]

    next_idx = next_[idx]

    if prev_idx != -1:

        next_[prev_idx] = next_idx

    if next_idx != -1:

        prev[next_idx] = prev_idx

while heap:

    a = heapq.heappop(heap)

    if a[0] != data[a[1]]:

        continue

    if a[0] > t:

        break

    target = next_[a[1]]

    score += a[0]

    data[a[1]] = float("inf")

    if target != -1:

        data[target] += a[0]

        heapq.heappush(heap,(data[target],target))

    delete(a[1])

print(score)

我嘗試了heapq+雙向鏈結串列了，但zerojudge還是不給我過(TLE)，請問是我哪裡處理得不到位嗎?

如果你有看到下面那行說APCS 考試時Python 是3s的話，其實上面的code應該是有機會過的，但現在ZJ沒有3倍時限，要在1s內過O(nlogn)且n達到3e5是有難度的
而且這題會有更多資料進出heap

看來只能單調棧O(n)了

詳細解法可以參考超電的暴力又被TLE寫的詳解

我研究了您提供的單調棧解法，我只能說....嘆為觀止。不過我很疑惑，這個解法在考試的時候真的有辦法當場想到嗎(畢竟他的邏輯比較特別)，還是有甚麼判斷的關鍵思路(還是只能憑經驗XD)，謝謝你願意提供我這麼多想法。