关于二分和双指针的使用

在某些题目中，我们需要去二分答案找到最优值，此时，集合一般满足[l,mid] [mid+1,r] 这种情况前半段满足或者后半段满足的时候，就可以去二分答案
某些时候我们需要使用双指针去check这个东西，
下面是使用双指针去check的题目

Binary String

二分使用双指针去check 区间，用双指针来固定一端，滑动另一段来达到检查某一段是否满足条件

#include <bits/stdc++.h>
typedef int INT;
#define int long long
#define sll(x) scanf("%lld", &x)
#define s(x) scanf("%d", &x)
using namespace std;
string s;
int _1;
int check(int x) {
    
    int a = 0, b = 0;
    for (int l = 0, r = 0; r < s.size(); r ++) {
    
        if (s[r] == '1') b ++;
        else a ++;
        while (a > x && l <= r) {
    
            if (s[l] == '1') b --;
            else a --;
            l ++;
        }
        if (_1 - b <= x) return true;
        
    }
    return false;
}
signed main() {
    
    int t;cin>> t;
    while (t --) {
    
        _1 = 0;
        cin >> s;
        for (int i = 0; i < s.size(); i ++) if (s[i] == '1') _1 ++;
        int l = 0, r = s.size();
        while (l < r) {
    
            int x = l + r >> 1;
            if (check(x)) r = x;
            else l = x + 1;
        }
        cout << r << endl;
    }
    return 0;
}

Difference

利用双指针去检查和法的区间，同样的地方就是在于固定一段，移动另一端，比如对于每一个r来说，去滑动l，即尾部确定，寻找合法的头部

#include <bits/stdc++.h>
typedef int INT;
// #define int long long
#define sll(x) scanf("%lld", &x)
#define s(x) scanf("%d", &x)
using namespace std;
const int N = 5e5 + 111;
long long n, m;
int g[N];
int ma[N][26], mi[N][26];
int p[N];
void init() {
    
    for (int i = 2; i < N; i ++) p[i] = p[i / 2] + 1;
    for (int i = 1; i <= n; i ++)
        ma[i][0] = mi[i][0] = g[i];
    for (int j = 1; j < 26; j ++)
    for (int i = 1; i + (1 << j) - 1 <= n; i ++)
        ma[i][j] = max(ma[i][j - 1], ma[i + (1 << j - 1)][j - 1]),
        mi[i][j] = min(mi[i][j - 1], mi[i + (1 << j - 1)][j - 1]);
}
long long q(int l, int r) {
    
    int k = p[r - l + 1];
    int a = max(ma[l][k], ma[r - (1 << k) + 1][k]);
    int b = min(mi[l][k], mi[r - (1 << k) + 1][k]);
    return ((long long)(r - l + 1)) * (a - b);
}
int check(long long x) {
    
    long long cnt = 0;
    for (int l = 1, r = 1; r <= n; r ++) {
    
        while (l <= r && q(l, r) >= x) l ++;
        cnt += r - l + 1;
    }
    cnt ++;
    return cnt > m;
}
signed main() {
    
    sll(n), sll(m);
    for (int i = 1; i <= n; i ++) s(g[i]);
    init();
    m = n * (n + 1) / 2 - m + 1;
    long long l = 0, r = q(1, n);
    while (l < r) {
    
        long long x = l + r + 1 >> 1;
        if (check(x)) r = x - 1;
        else l = x;
    }
    cout << l << endl;
    return 0;
}