Subtask ~1~: Với mỗi truy vấn, ta có thể làm tham lam như bài tập sau Bedao Mini 18 A.

Subtask ~2~:

Ta tiếp tục sử dụng nhận xét: nếu dùng hai phần tử đầu tiên, ta luôn suy ra được toàn bộ dãy. Để thực hiện thao tác cập nhật, ta phải dùng cây phân đoạn (segment tree).

Ta sẽ đánh số các cặp phần tử:

• 00 đánh số ~0~.
• 01 đánh số ~1~.
• 11 đánh số ~2~.
• 10 đánh số ~3~.

Với mỗi nút ~u~ trên cây phân đoạn, ta lưu ~f(u, x)~: dãy con dài nhất nếu hai phần tử đầu tiên được đánh số là ~x~. Đáp số là ~max(f(1, 0), f(1, 1), f(1, 2), f(1, 3))~.

Bài toán giờ là với mỗi nút ~u~, ta có hai con trái ~L~ và con phải ~R~, ta cần tìm cách hợp hai con này.

Ta xét các bước chuyển trạng thái như sau: 00 ~\rightarrow~ 01 ~\rightarrow~ 11 ~\rightarrow~ 10.

Ta luôn cặp nhật theo cách sau: ~f(u, x) = f(L, x) + f(R, (f(L, x) + x) \mod 4)~.

Công thức trên là đúng. Thật vậy, khi tính ~f(u, x)~, ta biết chắc rằng con trái cũng sẽ bắt đầu bởi ~x~. Khi đó ta sẽ sinh ra được một dãy dài vô hạn và có thể làm tham lam như subtask ~1~. Lúc này ~f(L, x)~ đã được tính theo cách tham lam ở các bước đệ quy trước. Do đó ta lấy toàn bộ dãy theo ~f(L, x)~ luôn tối ưu. Ta chỉ cần xem dãy ~f(L, x)~ kết thúc bằng hai phần tử nào nhằm tìm hai phần tử bắt đầu của con phải ~R~. Khi đó ~f(u, x)~ sẽ được tính theo công thức trên.

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, q;
string s;
bool ok[N];
// 0: 00
// 1: 01
// 2: 11
// 3: 10
// 0 -> 1 -> 2 -> 3 -> 0 ...
struct SegmentTree{
    int val[4][N<<2];
    void Ghep(int x){
        int L = (x<<1), R = L|1;
        for(int i=0; i<4; i++)
            val[i][x] = val[i][L] + val[(i + val[i][L]) %4][R];

    }
    int getAns(){
        return max({val[0][1], val[1][1], val[2][1], val[3][1]});
    }
    void update(int pos, int x=1, int xl=1, int xr=n){
        if(xl == xr){
            val[0][x] = val[1][x] = !ok[pos];
            val[2][x] = val[3][x] = ok[pos];
            return;
        }
        int xm = (xl+xr) >> 1;
        if(pos <= xm) update(pos, x<<1, xl, xm);
        else update(pos, x<<1|1, xm+1, xr);
        Ghep(x);
    }
} IT;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>s;
    s = ' ' + s;
    for(int i=1; i<=n; i++){
        ok[i] = s[i] - '0';
        IT.update(i);
    }
    cin>>q;
    int x;
    while(q--){
        cin>>x;
        ok[x] ^= 1;
        IT.update(x);
        cout<<IT.getAns()<<'\n';
    }
    return 0;
}