2916专题

【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II

算法可以发掘本质,如: 一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏的格子放足够多骨牌。 三,某个单色图,1表示前前景,0表示后景色。每次操作可以将一个1,变成0。如何在最少得操作情况下,使得没有两个1相邻(四连通)。 四,若干路人,有些人是熟人,如何选出最多的人参加实验。

leetcode 2916. 子数组不同元素数目的平方和 II(区间更新 + 区间查询 线段树第二个板子 双闭区间 避开0)

描述 偷了一个线段树板子 不知道为啥要避开0 然后这里的更新和查找都是用双闭区间的 ac code class SegmentTree:def __init__(self, n):self.n = n self.B1 = [0]*n self.B2 = [0]*n def add(self, b, idx, x):N = self.n while idx < N:b[idx] += xi