NOI.AC

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#212190	#3816. 元素	Panjunnan	0	0ms	0kb	Python2.7	2.1kb	2024-10-13 11:58:11	2024-10-13 12:31:32

answer

class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def build(self, a, l, r, node):
        if l == r:
            self.tree[node] = a[l]
        else:
            mid = (l + r) // 2
            self.build(a, l, mid, 2 * node)
            self.build(a, mid + 1, r, 2 * node + 1)
            self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])

    def update(self, l, r, val, node):
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node]
            if l != r:
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0
        if l > r or l > r:
            return
        if l == r:
            self.tree[node] += val
        else:
            mid = (l + r) // 2
            self.update(l, mid, val, 2 * node)
            self.update(mid + 1, r, val, 2 * node + 1)
            self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])

    def query(self, l, r, node):
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node]
            if l != r:
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0
        if l > r or l > r:
            return -float('inf')
        if l == r:
            return self.tree[node]
        else:
            mid = (l + r) // 2
            left = self.query(l, mid, 2 * node)
            right = self.query(mid + 1, r, 2 * node + 1)
            return max(left, right)

def solve(n, q, a, queries):
    tree = SegmentTree(n)
    tree.build(a, 0, n - 1, 1)
    results = []
    for l, r in queries:
        max_element = tree.query(l - 1, r - 1, 1)
        results.append(max_element + 1)
    return results

n, q = map(int, input().split())
a = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
results = solve(n, q, a, queries)
for result in results:
    print(result)

Source code, Language: Python2.7

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 0

Dangerous Syscalls

input:

10 10
492 1887 1028 1209 252 1860 1527 699 1656 928
6 9
2 8
3 10
2 3
1 8
6 9
3 5
4 7
1 4
2 7

output:

result:

Test #2:

score: 0

Dangerous Syscalls

input:

50 50
413 1208 1780 279 1403 1706 11 1583 333 355 1068 1270 1835 1042 957 423 1140 1153 1709 284 281...

output:

result:

Test #3:

score: 0

Dangerous Syscalls

input:

50 50
407 1089 1459 1626 1917 555 1611 492 443 1149 406 1259 1729 1554 577 1310 1899 1578 1005 1459 ...

output:

result:

Test #4:

score: 0

Dangerous Syscalls

input:

50 50
1792 843 1272 547 698 1086 1174 1607 1277 1055 506 881 1445 372 1076 1770 647 1086 320 1912 18...

output:

result:

Test #5:

score: 0

Dangerous Syscalls

input:

50 50
44 1463 245 1177 1728 1335 768 475 790 623 1466 98 672 230 339 1428 872 1905 405 1260 1503 813...

output:

result:

Test #6:

score: 0

Dangerous Syscalls

input:

50 50
695 974 1078 231 500 498 1308 1666 1925 766 1994 1776 1955 1766 1191 1021 1581 1202 615 1230 1...

output:

result:

Test #7:

score: 0

Dangerous Syscalls

input:

200 200
403 329 389 1103 695 1865 818 671 750 1868 1422 422 1186 1431 172 1569 460 1580 406 1049 138...

output:

result:

Test #8:

score: 0

Dangerous Syscalls

input:

200 200
147 1386 1788 1493 1919 1136 861 871 1895 1006 1776 346 381 1666 296 289 568 1616 1535 531 2...

output:

result:

Test #9:

score: 0

Dangerous Syscalls

input:

2000 2000
1154 852 1088 1530 639 1318 1250 1222 1341 1070 205 656 903 1491 808 317 756 1962 102 1445...

output:

result:

Test #10:

score: 0

Dangerous Syscalls

input:

2000 2000
1232 731 1651 991 1681 1739 776 240 829 1337 493 248 214 1852 716 325 1280 1207 380 724 11...