class FenwickTree {
private final int[][] t;
public FenwickTree(int n) {
t = new int[n + 1][2];
}
// op=1，添加一个 size
// op=-1，移除一个 size
public void update(int size, int op) {
for (int i = t.length - size; i < t.length; i += i & -i) {
t[i][0] += op;
t[i][1] += op * size;
}
}
// 返回 >= size 的元素个数，元素和
public int[] query(int size) {
int cnt = 0, sum = 0;
for (int i = t.length - size; i > 0; i &= i - 1) {
cnt += t[i][0];
sum += t[i][1];
}
return new int[]{cnt, sum};
}
}
class Solution {
public List<Integer> numberOfAlternatingGroups(int[] a, int[][] queries) {
int n = a.length;
TreeSet<Integer> set = new TreeSet<>();
FenwickTree t = new FenwickTree(n);
for (int i = 0; i < n; i++) {
if (a[i] == a[(i + 1) % n]) {
add(set, t, n, i); // i 是一个结束位置
}
}
List<Integer> ans = new ArrayList<>();
for (int[] q : queries) {
if (q[0] == 1) {
if (set.isEmpty()) {
ans.add(n); // 每个长为 size 的子数组都符合要求
} else {
int[] res = t.query(q[1]);
ans.add(res[1] - res[0] * (q[1] - 1));
}
} else {
int i = q[1];
if (a[i] == q[2]) { // 无影响
continue;
}
int pre = (i - 1 + n) % n;
int nxt = (i + 1) % n;
// 修改前，先去掉结束位置
if (a[pre] == a[i]) {
del(set, t, n, pre);
}
if (a[i] == a[nxt]) {
del(set, t, n, i);
}
a[i] ^= 1;
// 修改后，添加新的结束位置
if (a[pre] == a[i]) {
add(set, t, n, pre);
}
if (a[i] == a[nxt]) {
add(set, t, n, i);
}
}
}
return ans;
}
// 添加一个结束位置 i
private void add(TreeSet<Integer> set, FenwickTree t, int n, int i) {
if (set.isEmpty()) {
t.update(n, 1);
} else {
update(set, t, n, i, 1);
}
set.add(i);
}
// 移除一个结束位置 i
private void del(TreeSet<Integer> set, FenwickTree t, int n, int i) {
set.remove(i);
if (set.isEmpty()) {
t.update(n, -1);
} else {
update(set, t, n, i, -1);
}
}
// op=1，添加一个结束位置 i
// op=-1，移除一个结束位置 i
private void update(TreeSet<Integer> set, FenwickTree t, int n, int i, int op) {
Integer pre = set.floor(i);
if (pre == null) {
pre = set.last();
}
Integer nxt = set.ceiling(i);
if (nxt == null) {
nxt = set.first();
}
t.update((nxt - pre + n - 1) % n + 1, -op); // 移除/添加旧长度
t.update((i - pre + n) % n, op);
t.update((nxt - i + n) % n, op); // 添加/移除新长度
}
}
from sortedcontainers import SortedList
class Solution:
def numberOfAlternatingGroups(self, a: List[int], queries: List[List[int]]) -> List[int]:
n = len(a)
sl = SortedList()
t = [[0, 0] for _ in range(n + 1)]
# op=1，添加一个 size
# op=-1，移除一个 size
def fenwick_update(size: int, op: int) -> None:
i = len(t) - size
while i < len(t):
t[i][0] += op
t[i][1] += op * size
i += i & -i
# 返回 >= size 的元素个数，元素和
def fenwick_query(size: int) -> (int, int):
cnt = s = 0
i = len(t) - size
while i > 0:
cnt += t[i][0]
s += t[i][1]
i &= i - 1
return cnt, s
# op=1，添加一个结束位置 i
# op=-1，移除一个结束位置 i
def update(i: int, op: int) -> None:
idx = sl.bisect_left(i)
pre = sl[idx - 1]
nxt = sl[idx % len(sl)]
fenwick_update((nxt - pre - 1) % n + 1, -op) # 移除/添加旧长度
fenwick_update((i - pre) % n, op)
fenwick_update((nxt - i) % n, op) # 添加/移除新长度
# 添加一个结束位置 i
def add(i: int) -> None:
if not sl:
fenwick_update(n, 1)
else:
update(i, 1)
sl.add(i)
# 移除一个结束位置 i
def remove(i: int) -> None:
sl.remove(i)
if not sl:
fenwick_update(n, -1)
else:
update(i, -1)
for i, c in enumerate(a):
if c == a[(i + 1) % n]:
add(i) # i 是一个结束位置
ans = []
for q in queries:
if q[0] == 1:
if not sl:
ans.append(n) # 每个长为 size 的子数组都符合要求
else:
cnt, s = fenwick_query(q[1])
ans.append(s - cnt * (q[1] - 1))
else:
i, c = q[1], q[2]
if a[i] == c: # 无影响
continue
pre, nxt = (i - 1) % n, (i + 1) % n
# 修改前，先去掉结束位置
if a[pre] == a[i]:
remove(pre)
if a[i] == a[nxt]:
remove(i)
a[i] = c
# 修改后，添加新的结束位置
if a[pre] == a[i]:
add(pre)
if a[i] == a[nxt]:
add(i)
return ans
from sortedcontainers import SortedList
class FenwickTree:
def __init__(self, n: int):
self.t = [[0, 0] for _ in range(n + 1)]
# op=1，添加一个 size
# op=-1，移除一个 size
def update(self, size: int, op: int) -> None:
i = len(self.t) - size
while i < len(self.t):
self.t[i][0] += op
self.t[i][1] += op * size
i += i & -i
# 返回 >= size 的元素个数，元素和
def query(self, size: int) -> (int, int):
cnt = s = 0
i = len(self.t) - size
while i > 0:
cnt += self.t[i][0]
s += self.t[i][1]
i &= i - 1
return cnt, s
class Solution:
def numberOfAlternatingGroups(self, a: List[int], queries: List[List[int]]) -> List[int]:
n = len(a)
sl = SortedList()
t = FenwickTree(n)
# op=1，添加一个结束位置 i
# op=-1，移除一个结束位置 i
def update(i: int, op: int) -> None:
idx = sl.bisect_left(i)
pre = sl[idx - 1]
nxt = sl[idx % len(sl)]
t.update((nxt - pre - 1) % n + 1, -op) # 移除/添加旧长度
t.update((i - pre) % n, op)
t.update((nxt - i) % n, op) # 添加/移除新长度
# 添加一个结束位置 i
def add(i: int) -> None:
if not sl:
t.update(n, 1)
else:
update(i, 1)
sl.add(i)
# 移除一个结束位置 i
def remove(i: int) -> None:
sl.remove(i)
if not sl:
t.update(n, -1)
else:
update(i, -1)
for i, c in enumerate(a):
if c == a[(i + 1) % n]:
add(i) # i 是一个结束位置
ans = []
for q in queries:
if q[0] == 1:
if not sl:
ans.append(n) # 每个长为 size 的子数组都符合要求
else:
cnt, s = t.query(q[1])
ans.append(s - cnt * (q[1] - 1))
else:
i, c = q[1], q[2]
if a[i] == c: # 无影响
continue
pre, nxt = (i - 1) % n, (i + 1) % n
# 修改前，先去掉结束位置
if a[pre] == a[i]:
remove(pre)
if a[i] == a[nxt]:
remove(i)
a[i] = c
# 修改后，添加新的结束位置
if a[pre] == a[i]:
add(pre)
if a[i] == a[nxt]:
add(i)
return ans
