codeforces：E2. Array and Segments (Hard version)【线段树 + 区间修改】

分析

思路很简单
遍历每个作为最大值，然后区间不包含当前最大值的都可以减掉
easy version就可以这样暴力解决
然后求出最大差值

暴力解法

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
intervals = []
for _ in range(m):
    l, r = n, m = list(map(int, input().split()))
    intervals.append([l, r])

if m == 0:
    print(max(a) - min(a))
    print(0)
    print()
else:
    # fix max
    maxdiff = -0xffffffff
    chooseNum = 0
    chooseIdxs = []

    for maxIdx, maxn in enumerate(a):
        tmpNum = 0
        tmpIdxs = []
        tmp_a = a[:]
        cnt = 0
        for l, r in intervals:
            cnt += 1
            if l - 1 <= maxIdx <= r - 1:
                continue
            for i in range(l, r + 1):
                tmp_a[i - 1] -= 1
            tmpNum += 1
            tmpIdxs.append(cnt)
        if maxn - min(tmp_a) > maxdiff:
            maxdiff = maxn - min(tmp_a)
            chooseNum = tmpNum
            chooseIdxs = tmpIdxs

    print(maxdiff)
    print(chooseNum)
    print(*chooseIdxs)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

优化

如果n和m变大
这个方法就失效了
我们要用线段树进行区间修改
特别地，我们考虑全部都选择
然后遍历maxn节点（从左到右）
以它i为左端点的所有区间都可以加上（不选择）
然后所以i - 1（当前为i）为右区间的都可以删掉
对于那种横跨i的即l <= i = r的不用删
这样的算法有一个好处就是可以保证当前包含i的所有区间都没有选择
然后线段树查询即可

segTree solution

import sys
from functools import reduce
from collections import defaultdict
input = sys.stdin.readline


class SegTree:
    '''
    支持增量更新，覆盖更新，序列更新，任意RMQ操作
    基于二叉树实现
    初始化：O(1)
    增量更新或覆盖更新的单次操作复杂度：O(log k)
    序列更新的单次复杂度：O(n)
    '''

    def __init__(self, f1, f2, l, r, v=0):
        '''
        初始化线段树[left,right)
        f1,f2示例：
        线段和:
        f1=lambda a,b:a+b
        f2=lambda a,n:a*n
        线段最大值:
        f1=lambda a,b:max(a,b)
        f2=lambda a,n:a
        线段最小值:
        f1=lambda a,b:min(a,b)
        f2=lambda a,n:a
        '''
        self.ans = f2(v, r - l)
        self.f1 = f1
        self.f2 = f2
        self.l = l  # left
        self.r = r  # right
        self.v = v  # init value
        self.lazy_tag = 0  # Lazy tag
        self.left = None  # SubTree(left,bottom)
        self.right = None  # SubTree(right,bottom)

    @property
    def mid_h(self):
        return (self.l + self.r) // 2

    def create_subtrees(self):
        midh = self.mid_h
        if not self.left and midh > self.l:
            self.left = SegTree(self.f1, self.f2, self.l, midh)
        if not self.right:
            self.right = SegTree(self.f1, self.f2, midh, self.r)

    def init_seg(self, M):
        '''
        将线段树的值初始化为矩阵Matrx
        输入保证Matrx与线段大小一致
        '''
        m0 = M[0]
        self.lazy_tag = 0
        for a in M:
            if a != m0:
                break
        else:
            self.v = m0
            self.ans = self.f2(m0, len(M))
            return self.ans
        self.v = '#'
        midh = self.mid_h
        self.create_subtrees()
        self.ans = self.f1(self.left.init_seg(M[:midh - self.l]), self.right.init_seg(M[midh - self.l:]))
        return self.ans

    def cover_seg(self, l, r, v):
        '''
        将线段[left,right)覆盖为val
        '''
        if self.v == v or l >= self.r or r <= self.l:
            return self.ans
        if l <= self.l and r >= self.r:
            self.v = v
            self.lazy_tag = 0
            self.ans = self.f2(v, self.r - self.l)
            return self.ans
        self.create_subtrees()
        if self.v != '#':
            if self.left:
                self.left.v = self.v
                self.left.ans = self.f2(self.v, self.left.r - self.left.l)
            if self.right:
                self.right.v = self.v
                self.right.ans = self.f2(self.v, self.right.r - self.right.l)
            self.v = '#'
        # push up
        self.ans = self.f1(self.left.cover_seg(l, r, v), self.right.cover_seg(l, r, v))
        return self.ans

    def inc_seg(self, l, r, v):
        '''
        将线段[left,right)增加val
        '''
        if v == 0 or l >= self.r or r <= self.l:
            return self.ans
        # self.ans = '?'
        if l <= self.l and r >= self.r:
            if self.v == '#':
                self.lazy_tag += v
            else:
                self.v += v
            self.ans += self.f2(v, self.r - self.l)
            return self.ans
        self.create_subtrees()
        if self.v != '#':
            self.left.v = self.v
            self.left.ans = self.f2(self.v, self.left.r - self.left.l)
            self.right.v = self.v
            self.right.ans = self.f2(self.v, self.right.r - self.right.l)
            self.v = '#'
        self.pushdown()
        self.ans = self.f1(self.left.inc_seg(l, r, v), self.right.inc_seg(l, r, v))
        return self.ans

    def inc_idx(self, idx, v):
        '''
        increase idx by val
        '''
        if v == 0 or idx >= self.r or idx < self.l:
            return self.ans
        if idx == self.l == self.r - 1:
            self.v += v
            self.ans += self.f2(v, 1)
            return self.ans
        self.create_subtrees()
        if self.v != '#':
            self.left.v = self.v
            self.left.ans = self.f2(self.v, self.left.r - self.left.l)
            self.right.v = self.v
            self.right.ans = self.f2(self.v, self.right.r - self.right.l)
            self.v = '#'
        self.pushdown()
        self.ans = self.f1(self.left.inc_idx(idx, v), self.right.inc_idx(idx, v))
        return self.ans

    def pushdown(self):
        if self.lazy_tag != 0:
            if self.left:
                if self.left.v != '#':
                    self.left.v += self.lazy_tag
                    self.left.lazy_tag = 0
                else:
                    self.left.lazy_tag += self.lazy_tag
                self.left.ans += self.f2(self.lazy_tag, self.left.r - self.left.l)
            if self.right:
                if self.right.v != '#':
                    self.right.v += self.lazy_tag
                    self.right.lazy_tag = 0
                else:
                    self.right.lazy_tag += self.lazy_tag
                self.right.ans += self.f2(self.lazy_tag, self.right.r - self.right.l)
            self.lazy_tag = 0

    def query(self, l, r):
        '''
        查询线段[right,bottom)的RMQ
        '''
        if l >= r: return 0
        if l <= self.l and r >= self.r:
            return self.ans
        if self.v != '#':
            return self.f2(self.v, min(self.r, r) - max(self.l, l))
        midh = self.mid_h
        anss = []
        if l < midh:
            anss.append(self.left.query(l, r))
        if r > midh:
            anss.append(self.right.query(l, r))
        return reduce(self.f1, anss)



n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
ls = defaultdict(list)
intervals = []
for _ in range(m):
    l, r = list(map(int, input().split()))
    intervals.append([l, r])
    # fix l, get many r
    ls[l - 1].append(r - 1)

if m == 0:
    print(max(a) - min(a))
    print(0)
    print()
else:
    # fix max
    # use segTrees
    f1 = lambda a, b: min(a, b)
    f2 = lambda a, n: a
    segtree = SegTree(f1, f2, 0, n, 0)
    # init
    for i in range(n):
        segtree.inc_idx(i, a[i])


    # delete all intervals
    # if we later fix a maxn, we can add corresponding intervals
    for l, r in intervals:
        segtree.inc_seg(l - 1, r, -1)


    maxD, maxI = 0, 1
    rs = defaultdict(list)
    for i in range(n):
        # fix i
        for r in ls[i]:
            # add intervals back(not choose)
            segtree.inc_seg(i, r + 1, 1)
            rs[r].append(i)
        # delete useless intervals again
        # means that we choose these intervals
        for l in rs[i - 1]:
            segtree.inc_seg(l, i, -1)
        # find now d
        d = a[i] - segtree.query(0, n)
        if d > maxD:
            maxD, maxI = d, i

    ids = []
    for i, interval in enumerate(intervals):
        if interval[1] - 1 < maxI or interval[0] - 1 > maxI: # outside
            ids.append(i + 1)

    print(maxD)
    print(len(ids))
    print(*ids)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

总结

线段树 + 全删逆向 + 剔除包含当前节点的所有区间的ls + rs算法