灯笼大乱斗 | Decade

问题描述

元宵佳节，一场别开生面的灯笼大赛热闹非凡。N 位技艺精湛的灯笼师依次落座，每位师傅都有相应的资历值，其中第 i 位师傅的资历值为 A_i。从左到右，师傅们的资历值逐级递增（即 A₁ < A₂ < ⋯ < A_N）。同时，每位师傅都带来了自己精心制作的灯笼，其亮度值依次为 B₁, B₂, ⋯, B_N。

大赛中，主持人会选择一个区间 [L, R]（1 ≤ L < R ≤ N），让这个区间内的师傅们进行两两比拼，构成一场“灯笼大乱斗”。

比拼规则如下：假设在区间 [L, R] 中，由师傅 i 和师傅 j（L ≤ i < j ≤ R）进行对决。对决双方分别持有自己的灯笼。

如果师傅 i 的灯笼亮度 B_i 小于师傅 j 的灯笼亮度 B_j，则双方交换灯笼（相应地，如果 B_i ≥ B_j，则不交换）。
双方最终的得分计算方式为：资历值 + 持有灯笼的亮度。得分高者获胜，得分相同则平局。

由于在比赛中，资历深的师傅输给资历浅的师傅，将会有损颜面。因此，为了避免这种情况发生，主持人需要选择必胜区间。

必胜区间：如果一个区间内任意两位师傅进行比赛，资历值高的师傅都必定能够获胜，则称该区间为必胜区间。

现在，请你帮主持人算算，必胜区间共有多少个？

输入格式

第一行包含一个整数，表示灯笼师傅的数量。

第二行包含个整数，表示每位师傅的资历值，满足 A₁ < A₂ < ⋯ < A_N。

第三行包含个整数，表示每位师傅的灯笼亮度值。

输出格式

输出一个整数，表示必胜区间的总数量。

样例输入

1
2
3

3
1 3 5
3 4 1

样例输出

思路

首先思考对于任意两个人(i < j)之间进行对决的情况，题目的意思就是在计算得分时，下标大的灯笼亮度要变成两者间小的那个，也就是最终要满足： a_i + max(b_i, b_j) < a_j + min(b_i, b_j) 分两种情况：

b_i < = b_j：此时有a_j − b_j > a_i − b_i。
b_i > b_j：此时有a_j + b_j > a_i + b_i。

但对于第一种情况，我们可以得到以下恒等变化：同理对于第二种情况也有：a_j − b_j > a_i − b_i。

也就是说无论b_i, b_j大小如何，都需要同时满足：然后，题目中需要求出满足条件的区间数量，我们只需要保证区间里相邻下标满足上述等式即可（因为可以传递）。

一旦相邻下标不满足，说明区间就断开了，这时候我们可以得到满足条件的区间长度k。那么此时我们可以选取区间长度为2的k − 1个，长度为3的k − 2个…长度为k的1个，总共(k − 1) * k/2个。

代码

void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    ll ans = 0, x = a[1] + b[1], y = a[1] - b[1], cnt = 1; 
    ll cx, cy;
    for (int i = 2;i <= n;i++) {
        cx = a[i] + b[i], cy = a[i] - b[i];
        if (cx > x && cy > y) {
            x = cx, y = cy;
            ++cnt;
        } else {
            ans += (cnt - 1) * cnt / 2;
            cnt = 1;
        }
    }
    pl(ans);
}

复杂度

时间：O(n)
空间：O(1)