Submission #63841454

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
class LazySegTree:
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.data = [-10**18] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
    
    def build(self, arr):
        for i in range(self.n):
            self.data[self.size + i] = arr[i]
        for i in range(self.n, self.size):
            self.data[self.size + i] = -10**18
        for i in range(self.size - 1, 0, -1):
            self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])
    
    def _apply(self, idx, val):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
class LazySegTree:
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.data = [-10**18] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
    
    def build(self, arr):
        for i in range(self.n):
            self.data[self.size + i] = arr[i]
        for i in range(self.n, self.size):
            self.data[self.size + i] = -10**18
        for i in range(self.size - 1, 0, -1):
            self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])
    
    def _apply(self, idx, val):
        self.data[idx] += val
        self.lazy[idx] += val

    def _push(self, idx):
        if self.lazy[idx]:
            self._apply(2 * idx, self.lazy[idx])
            self._apply(2 * idx + 1, self.lazy[idx])
            self.lazy[idx] = 0

    def _update(self, idx, l, r, ql, qr, val):
        if ql >= r or qr <= l:
            return
        if ql <= l and r <= qr:
            self._apply(idx, val)
            return
        self._push(idx)
        mid = (l + r) // 2
        self._update(2 * idx, l, mid, ql, qr, val)
        self._update(2 * idx + 1, mid, r, ql, qr, val)
        self.data[idx] = max(self.data[2 * idx], self.data[2 * idx + 1])
    
    def update_range(self, l, r, val):
        self._update(1, 0, self.size, l, r + 1, val)
    
    def _query(self, idx, l, r, ql, qr):
        if ql >= r or qr <= l:
            return -10**18
        if ql <= l and r <= qr:
            return self.data[idx]
        self._push(idx)
        mid = (l + r) // 2
        left_max = self._query(2 * idx, l, mid, ql, qr)
        right_max = self._query(2 * idx + 1, mid, r, ql, qr)
        return max(left_max, right_max)
    
    def query_range(self, l, r):
        return self._query(1, 0, self.size, l, r + 1)
    
    def update_point(self, pos, new_val):
        cur = self.query_range(pos, pos)
        diff = new_val - cur
        self.update_range(pos, pos, diff)

N = int(input())
A = list(map(int, input().split()))

prefix = [0] * N
seen = {}
cnt = 0
for i in range(N):
    if A[i] not in seen:
        seen[A[i]] = True
        cnt += 1
    prefix[i] = cnt

suffix = [0] * N
seen = {}
cnt = 0
for i in range(N - 1, -1, -1):
    if A[i] not in seen:
        seen[A[i]] = True
        cnt += 1
    suffix[i] = cnt

INF_NEG = -10**18
F = [INF_NEG] * N
F[0] = prefix[0]

seg = LazySegTree(N)
seg.build(F)
last_occ = {}
ans = 0
for j in range(1, N):
    v = A[j]
    prev = last_occ.get(v, -1)

    if max(prev, 0) <= j - 1:
        seg.update_range(max(prev, 0), j - 1, 1)
    seg.update_point(j, prefix[j])
    dp = seg.query_range(0, j - 1)
    if j <= N - 2:
        candidate = dp + suffix[j + 1]
        ans = max(ans, candidate)
    last_occ[v] = j

print(ans)

Submission Info

Judge Result