1.双指针暴力超时，优化方案
当数组中只存在1和2的值的时候我们可以考虑用二分去优化,我们可以找到数组中最后一个1的值，前面都是1和2的话
我们可以通过最后一个1去灵活地凑出 第一个数到最后一个1的数的和中间的任意一个值(划重点）
当然我们要尽可能凑出来最大的值，如果最后一个1后面的2比第一个1前面的2多，我们用后缀和表示 总和
反之，我们用前缀和表示出我们能表示出的总和的最大值(代码用t来表示）
在此之前，我们需要用一个set来记录每一个1出现的位置，即a数组的下标，每次出现就插入；如果set为空，那么表示
全都为偶数，所以要求我们表示v必须也是偶数才能yes；我们根据set数组也能找到第一个1之前和最后一个1之后的2的个数
用我们的数组总和减去 我们找到的最小的2个数那个区间，得到的就是我们能表示出来的最大的数字t；
在后面的表示中，如果小于我们能表示的数，表示我们能凑出来，为yes；如果大于，我们再用剩余那段2去表示，能表示的
前提就是v和t要是同奇同偶，且v - t 差值要小于我们这段2的个数*2 ，否则表示失败
如果替换的话，就用set去动态维护即可,每次根据v的数字去决定插入还是消除
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N = 3e5 + 10; 5 6 int t,m,n; 7 int a[N],b[N],c[N],ans[N]; 8 9 int main() 10 { 11 scanf("%d", &t); 12 while(t --) 13 { 14 cin >> n >> m; 15 set<int> se; 16 17 int s = 0; 18 for (int i = 1; i <= n; i ++ ) 19 { 20 scanf("%d", &a[i]); 21 s += a[i]; //s用来记录总和 22 if(a[i] == 1) se.insert(i); //把每一个数字1 的位置丢到set中 23 } 24 25 while (m -- ){ 26 int op,x,v; 27 scanf("%d", &op); 28 if(op == 1) 29 { 30 scanf("%d", &v); //读入要判断的数 31 if(se.empty()) puts(v % 2 == 0 ? "YES" : "NO"); //如果se为空，表示全都是2,那么v是偶数就可以凑出来 32 else 33 {//判断是第一个1出现之前的2少还是最后一个1出现之后的2少 34 int cnt = min(*se.begin() - 1,n - *se.rbegin()); 35 int t = s - cnt * 2; //表示除开较少2的那段的数字和 36 if(v <= t ||(v % 2 == t % 2 && (v - t) / 2 <= cnt)) puts("YES"); 37 //如果 要凑的那个值小于我能表示的值，为yes，如果大于，则用后面的或者前面那段较少的2去维护 38 // 所以这个前提是 要凑的数和我能表示的最大数同奇同偶,然后大的差值要小于我能凑出的2个数*2,否则凑不了 39 else puts("NO"); 40 } 41 } 42 else { 43 scanf("%d%d", &x, &v); 44 if(a[x] == 1) se.erase(x); //等于1 换掉之后要出set 45 if(v == 1) se.insert(x); //换的值为1 换之后要进set 46 s += v- a[x]; //维护s的值 47 a[x] = v; 48 } 49 } 50 } 51 return 0; 52 }