On the use of bisection and double pointer

In some topics , We need to find the best value by dichotomy , here , Set generally satisfies [l,mid] [mid+1,r] In this case, the first half or the second half is satisfied , You can split the answer
Sometimes we need to use double pointers to check This thing ,
The following is the use of double pointers to check The subject of

Binary String

Bisection uses a double pointer to check Section , Fix one end with a double pointer , Slide another section to check whether a section meets the conditions

#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

Use double pointers to check the interval of sum method , The same thing is to fix a section , Move the other end , For example, for every r Come on , De sliding l, That is, the tail determines , Look for legal heads

#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;
}