单调性专题（二）

算法设计策略中
和扫描法有关的，常常包括

前缀和与差分
前缀最大值，最小值维护

和单调性有关的，常常包括

单调队列与单调栈
滑动窗口，双指针
二分

二分法

整数二分

说到单调性的问题，很多二分可以解决的问题，往往也具有单调性
这里补充一些整数二分的模版

将区间 [l, r] 划分成为 [l, mid] 和 [mid+1, r]
更新操作是 r = mid 或者 l = mid + 1
最后的答案是新区间的 l

int bsearch(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

将区间 [l, r] 划分成为 [l, mid-1] 和 [mid, r]
更新操作是 l = mid 或者是 r = mid - 1
为了防止死循环，计算 mid = l + r + 1 >> 1;

int bsearch(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

两种二分，实际上是上取整和下取整的不同
实际上，中点都满足 $mid = (l+r) / 2$

第一种情况
$[l,r] \to [l,mid] \cup [mid+1, r]$

第二种情况
$[l,r] \to [l,mid-1] \cup [mid, r]$
边界条件是 $r = l+1$
此时 $mid = (2l+1)/2 = l$ 恒成立
$[l, r] \to [mid, r]=[l,r]$
区间没有发生变化，导致死循环
解决方法是 $mid = (l+r+1) / 2$ 进行上取整即可

1
2
3

为了简便记忆，当执行了
l = mid
二分条件就变成了 mid = (l+r+1) / 2

小数二分

小数二分答案，其实反而更简单

double bsearch(double l, double r) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    return l;
}

值得注意的是 PI 的定义

1	const double PI = acos(-1.0);

扫描法，二分维护历史集合

Acwing113

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> ans;
        ans.push_back(1);
        
        for (int i = 2; i <= N; i++) {
            // binary search
            int l = 0, r = ans.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (compare(ans[mid], i)) l = mid;
                else r = mid - 1;
            }
            // ans is r 
            
            ans.push_back(i);
            // bubble sort
            for (int j = ans.size() - 2; j > r; j--) swap(ans[j], ans[j+1]);
            if (compare(i, ans[r])) swap(ans[r], ans[r+1]);
        }
        return ans;
    }
};

环形双指针

Acwing2452

本例涉及的思想有：计算几何，转角法，双指针

constexpr int maxn = 800 + 10;
int m = 0;

int S[maxn<<2], Sd[maxn<<2], St[maxn<<2];
ll ans = 0;

class Point {
public:
    int x, y, fl;
    Point() = default;
    Point(int x, int y, int fl = 0) : x(x), y(y), fl(fl) {}
    int sgn() const {
        if (y > 0 || (y == 0 && x > 0)) return 1;
        else return -1;
    }
} a[maxn], b[maxn], c[maxn], vec[maxn<<2];
// a enemy, b source, c tower
int _D, _S, _T;

inline ll cross(const Point &a, const Point &b) {
    return 1ll*a.x*b.y - 1ll*a.y*b.x;
}

bool cmp(const Point &a, const Point &b) {
    if (a.sgn() != b.sgn()) return a.sgn() > b.sgn();
    return cross(a, b) > 0;
}

void work() {
    _rep(i, 1, m << 1) {
        S[i] = S[i-1], Sd[i] = Sd[i-1], St[i] = St[i-1];
        if (vec[i].fl == 0) {
            Sd[i]++;
        }
        else {
            S[i] += Sd[i], St[i]++;
        }
    }

    // double pointer
    int j = 1, k = 1;
    for (; j <= m; j++) if (vec[j].fl) {
        if (k < j) k = j;
        while (k+1 < j+m && cross(vec[j], vec[k+1]) >= 0 ) k++;
        ans += (S[k] - S[j]) - Sd[j] * (St[k]-St[j]);
    }
}

void solve() {
    _rep(i, 1, _S) {
        m = 0;
        _rep(j, 1, _D) vec[++m] = Point(a[j].x-b[i].x, a[j].y-b[i].y, 0);
        _rep(j, 1, _T) vec[++m] = Point(c[j].x-b[i].x, c[j].y-b[i].y, 1);
        sort(vec+1, vec+1+m, cmp);
        _rep(j, 1, m) vec[j+m] = vec[j];

        // then work
        work();
    }
    printf("%lld\n", ans);
}

void init() {
    memset(S, 0, sizeof(S));
    memset(Sd, 0, sizeof(Sd));
    memset(St, 0, sizeof(St));
    m = 0;
    ans = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    scanf("%d", &_D);
    _rep(i, 1, _D) scanf("%d%d", &a[i].x, &a[i].y);
    scanf("%d", &_S);
    _rep(i, 1, _S) scanf("%d%d", &b[i].x, &b[i].y);
    scanf("%d", &_T);
    _rep(i, 1, _T) scanf("%d%d", &c[i].x, &c[i].y);

    // then solve
    solve();
}

滑动窗口的单调性

Acwing1688 列车记录2
Acwing1688-01
Acwing1688-02
Acwing1688-03
Acwing1688-04

const int maxn = 1e5 + 10;
const int inf = 1e9;
const int mod = 1e9 + 7;
int N, K, c[maxn];

inline int solve(int v, int len) {
    int f[maxn];
    f[0] = f[1] = 1;

    int p = inf - v;
    for (int i = 2; i <= len + 1; i++) {
        f[i] = 1ll * (p+1) * f[i-1] % mod;
        if (i-K-1 >= 0) f[i] = (f[i] - 1ll * f[i-K-1] * ksm(p, K, mod) % mod + mod) % mod;
    }
    return f[len+1];
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d%d", &N, &K);
    _rep(i, 1, N+1-K) scanf("%d", &c[i]);

    // then solve
    int i = 1, j = 1, len = 1;
    ll ans = 1;
    for (; i <= N+1-K; i = j+1) {
        j = i;
        while (c[j+1] == c[i]) j++;
        len = j-i+K;
        if (i > 1 && c[i-1] > c[i]) len -= K;
        if (j < N+1-K && c[j+1] > c[i]) len -= K;

        ans = 1ll * ans * solve(c[i], len) % mod;
    }
    printf("%lld\n", ans);
}

连续子序列问题

连续子序列问题是典型的可以用滑动窗口维护的
必要时可借助其他数据结构维护滑动窗口区间 $[l, r]$

UVA11536
这是一个求“连续子区间长度最小”的问题

constexpr int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int x[maxn], N, M, K;

void prework() {
    _for(i, 0, N) {
        if (i < 3) x[i] = i+1;
        else x[i] = (x[i-1] + x[i-2] + x[i-3]) % M + 1;
    }
}

void add(int v, map<int, int> &mp) {
    if (1<= v && v <= K) mp[v]++;
}
void del(int v, map<int, int> &mp) {
    if (mp.count(v) == 0) return;
    mp[v]--;
    if (mp[v] < 1) mp.erase(v);
}

void solve() {
    int ans = inf;
    map<int, int> mp;
    int i = 0, j = 0;

    for (; i < N; i++) {
        while (j < N && mp.size() < K) add(x[j++], mp);
        if (mp.size() == K) {
            while (i < N && ( !mp.count(x[i]) || mp[x[i]] > 1 )) del(x[i++], mp);
            chmin(ans, j - i);
        }
        del(x[i], mp);
    }

    if (ans == inf) printf("sequence nai\n");
    else printf("%d\n", ans);
}

void init() {
    memset(x, 0, sizeof(x));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase, _ = 0;
    scanf("%d", &kase);

    while (kase--) {
        init();
        printf("Case %d: ", ++_);
        scanf("%d%d%d", &N, &M, &K);

        // then prework and solve
        prework();
        solve();
    }
}

单调栈模型

单调栈最常用的模型就是：找到左边第一个比 $A_i$ 小的元素
Gym101334F

根据单调栈模型，本例的算法就很简单了

预处理每一个 $A_i$ ，求出左边第一个比 $A_i$ 小的元素位置 $L(i)$
右边第一个比 $A_i$ 小的元素 $R(i)$
用区间 $[L(i)+1, R(i)-1]$ 部分和 $\times A_i$ 来更新全局的 $ans$

constexpr int maxn = 100000 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int N, a[maxn];

int s[maxn], top = 0;
ll S[maxn];
int l[maxn], r[maxn];

void prework() {
    _rep(i, 1, N) S[i] = S[i-1] + 1ll * a[i];

    top = 0;
    for (int i = 1; i <= N; i++) {
        while (top && a[s[top]] >= a[i]) top--;
        if (top == 0) l[i] = 0;
        else l[i] = s[top];
        s[++top] = i;
    }

    top = 0;
    for (int i = N; i >= 1; i--) {
        while (top && a[s[top]] >= a[i]) top--;
        if (top == 0) r[i] = N + 1;
        else r[i] = s[top];
        s[++top] = i;
    }
}

void solve() {
    int ansl = 0, ansr = 0;
    ll ans = -inf;
    for (int i = 1; i <= N; i++) {
        ll res = 1ll * (S[r[i]-1] - S[l[i]]) * a[i];
        if (chmax(ans, res)) {
            ansl =  l[i] + 1, ansr = r[i] - 1;
        }
    }

    printf("%lld\n", ans);
    printf("%d %d\n", ansl, ansr);
}

void init() {
    memset(s, 0, sizeof(s));
    memset(S, 0, sizeof(S));
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    top = 0;
}

int main() {
    freopen("feelgood.in", "r", stdin);
    freopen("feelgood.out", "w", stdout);
    init();
    scanf("%d", &N);
    _rep(i, 1, N) scanf("%d", &a[i]);

    // prework and solve
    prework();
    solve();
}