每周一题

二分搜索

$对于一个大小为N的数列, a_i，保证是这个数列是非递减，即a_i \le a_{i+1}, i \in [1,n)$
$1, 2,3,4,5,6$
$查找x=4$

int l = 1, r = n;
while(l <= r){   //[ ]
    int m = l + r >> 1;
    if(x > a[m]) l = m + 1;
    else r = m -1;
}

$N\le 3\times 10^5的序列，A_i = 0 或者1$
$k\le N次操作将0变成1，求最长的连续1序列长度，并打印方案$

$solution:$
$枚举2个端点,l,r,数一数这里面多少个0，r-l+1$
$r-l+1>ans$
$O(n^2)$

$枚举1个端点,l,找到尽量远的右端点r，[l,r]<=k个0$
$大家都会吧，维护一个前缀和, prefixSum[i]:=1\sim i有多少个0$
$Zero_{[l,r]}:=prefixSum[r] - prefixSum[l-1]$

//upper_bound > , -1  
int binarySearch(int l, int r){
    int L = l;
    while(l <= r){
        int m = l + r >> 1;
        int zero = prefixSum[m]-prefixSum[L-1]; //[L,m]
        if(zero <= k)  l = m + 1;
        else r = m - 1;
    }
    retrun l - 1;
}
//<
pair<int, int> ans = make_pair(-INF, -INF); //长度，左端点
for(int l = 1; l <= n; ++l){
    int r = binarySearch(l, n);
    ans = max(ans, make_pair(r - l + 1, l));
}
//correct some mistakes
for(int i = ans.second; ans.first--; ++i) a[i] = 1;
for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);

$two\ pointers$

• + 右端点
• - 左端点

int zero = 0;
pair<int, int> ans = make_pair(-INF, -INF); //长度，左端点
// [l, r)
for(int l = 1, r = 1; l <= n; ++l){
    while(r <= n && zero + (a[r] == 0) <= k) zero += a[r++] == 0;
    ans = max(ans, make_pair(r - l, l));
    zero -= a[l] == 0;
}
//correct some mistakes
for(int i = ans.second; ans.first--; ++i) a[i] = 1;
for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);

$N\le 10^5的序列，A_i\le 10^9$
$求连续区间中任意2个数差值不超过k的区间个数$

$最坏情况， 最大差值，[l,r]:= maxv - minv <=k$

multiset<int> s;  //erase(val), (iterator)
int ans = 0;
for(int l = 1, r = 1; l <= n; ++l){
    while(r <= n){
        if(!s.size()){ //空的
            s.insert(a[r++]);
        }
        else{
            //最大值                    最小值
            if(a[r] - *s.begin() > k || *s.rbegin() - a[r] > k) break;
            s.insert(a[r++]);
        }
        ans += r - l;
        if(ans >= MOD) ans -= MOD;
        s.erase(s.find(a[l]));
    }
}