TLE了,大佬求助

题目是这样的:
微信图片_20250621223809
限制是:
微信图片_20250621223812
输入格式是:
微信图片_20250621223815
输出格式是:
微信图片_20250621224054
输入样例1:
微信图片_20250621223818
输出样例1:
微信图片_20250621223821
输入样例2:
微信图片_20250621223825
输出样例2:
微信图片_20250621223827
输入样例3:
微信图片_20250621223832
输出样例3:
微信图片_20250621223835
我的代码是这样的:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    bool a[5000005] = {};
    long long n,q,b[5000005] = {};
    cin >> n >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> b[i];
        a[b[i]] = !a[b[i]];
        long long cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            if(i == n && a[i] == true)
            {
                cnt++;
                continue;
            }
            if((i == 1 && a[i] == true) || (a[i - 1] == false && a[i] == true))
            {
                long long l = 1;
                for(int j = i; j <= n; j++)
                {
                    if(a[j + 1] == false || j == n)
                    {
                        l = 2;
                        i = j + 1;
                        break;
                    }
                }
                if(l == 2)
                {
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

因为是暴力的,所以想让大家帮我优化一下,只AC了11个样例,TLE了18个样例,各位大佬帮帮忙啊!求求了 :loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face::loudly_crying_face:

额,那个题目建议自己用AI翻译,这个翻译有点矛盾的地方和表达错误的地方

有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?
有人吗?

把数组放外面,然后你这个代码是 O(qn^2) 的。正解是分类讨论。

  • 如果修改后的 a_{b_i}=0
    • a_{b_i-1}=1a_{b_i+1}=1 连续块数增加 1
    • a_{b_i-1}=0a_{b_i+1}=0 连续块数减少 1
  • 如果修改后的 a_{b_i}=1
    • a_{b_i-1}=1a_{b_i+1}=1 连续块数减少 1
    • a_{b_i-1}=0a_{b_i+1}=0 连续块数增加 1
2 个赞

perf 1757 的大蛇啊 %%%%%%%%%%%%

膜啥啊我才绿名

所以在输入的时候只需要看看是增加一对数,还是减少一对数,还是把一对数分成两对数,还是把两对数分成一对数,对吗?

\Large不要刷屏!! 不要刷屏!! 不要刷屏!!