双指针问题

1.双指针暴力超时，优化方案

Problem - D - Codeforces

当数组中只存在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 }