Elearning CodePath – CTP Online Judge

Đèn trên vòng tròn

circlebit

Có `n` bóng đèn đặt trên một vòng tròn, đánh số từ `1` đến `n` theo chiều kim đồng hồ.  
Mỗi bóng đèn có trạng thái `0` hoặc `1`.

Có `q` thao tác:

```text
T i
```

Đổi trạng thái bóng đèn `i`: nếu đang tắt thì bật, nếu đang bật thì tắt.

```text
Q l r
```

Đếm số bóng đèn đang bật trên cung tròn đi từ `l` đến `r` theo chiều kim đồng hồ, tính cả hai đầu.

Nếu `l ≤ r`, cung là đoạn `[l, r]`.  
Nếu `l > r`, cung đi qua cuối vòng, tương ứng với:

```text
[l, n] và [1, r]
```

## Input

```text
n q
s1 s2 ... sn
q dòng thao tác
```

Trong đó `s_i` là trạng thái ban đầu của bóng đèn `i`.

## Output

Với mỗi thao tác `Q`, in kết quả trên một dòng.

## Subtasks

| Subtask | Ràng buộc gợi ý | Điểm | Hướng làm |
|---|---:|---:|---|
| 1 | Không có truy vấn `l > r` | 20 | Fenwick đoạn thường |
| 2 | Có ít truy vấn vòng | 30 | Tách đoạn |
| 3 | `n, q` lớn | 50 | Fenwick + tách đoạn đầy đủ |

## Ví dụ

### Input

```text
6 7
1 0 1 0 1 0
Q 1 6
Q 4 2
T 2
Q 1 3
T 5
Q 4 2
Q 5 5
```

### Output

```text
3
2
3
2
0
```

### Giải thích ví dụ

Ban đầu các đèn bật là `1, 3, 5`.

- `Q 1 6`: đếm toàn bộ vòng, có `3` đèn bật.
- `Q 4 2`: cung gồm `4, 5, 6, 1, 2`, có đèn `5` và `1`, kết quả `2`.
- Sau `T 2`, đèn `2` bật. `Q 1 3` có đèn `1, 2, 3`, kết quả `3`.
- Sau `T 5`, đèn `5` tắt. `Q 4 2` còn đèn `1, 2`, kết quả `2`.
- `Q 5 5` hỏi riêng đèn `5`, hiện đang tắt nên kết quả `0`.

✅ Đã AC: 1 / 1 submissions