蓝桥杯 灯笼大乱斗【算法赛】

问题描述

元宵佳节，一场别开生面的灯笼大赛热闹非凡。NN 位技艺精湛的灯笼师依次落座，每位师傅都有相应的资历值，其中第 ii 位师傅的资历值为 AiAi​。从左到右，师傅们的资历值逐级递增（即 A1<A2<⋯<ANA1​<A2​<⋯<AN​）。同时，每位师傅都带来了自己精心制作的灯笼，其亮度值依次为 B1,B2,⋯ ,BNB1​,B2​,⋯,BN​。

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

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

• 如果师傅 ii 的灯笼亮度 BiBi​ 小于师傅 jj 的灯笼亮度 BjBj​，则双方交换灯笼（相应地，如果 Bi≥BjBi​≥Bj​，则不交换）。
• 双方最终的得分计算方式为：资历值 + 持有灯笼的亮度。得分高者获胜，得分相同则平局。

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

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

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

输入格式

第一行包含一个整数 NN (1≤N≤105)(1≤N≤105)，表示灯笼师傅的数量。

第二行包含 NN 个整数 A1,A2,…,ANA1​,A2​,…,AN​ (1≤Ai≤109)(1≤Ai​≤109)，表示每位师傅的资历值，满足 A1<A2<⋯<ANA1​<A2​<⋯<AN​。

第三行包含 NN 个整数 B1,B2,…,BNB1​,B2​,…,BN​ (1≤Bi≤109)(1≤Bi​≤109)，表示每位师傅的灯笼亮度值。

输出格式

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

样例输入

3
1 3 5
3 4 1

样例输出

1

 [L,R]必胜，只需要看R+1和R的关系就好了，如果R+1能赢R，则R+1必胜[L,R]

具体证明不会

#include <iostream>
using namespace std;
int main()
{int n;cin>>n;int an[n], bn[n], cn[n];for(int i=0; i<n; i++){cin>>an[i];} for(int i=0; i<n; i++){cin>>bn[i];} long long int num = 1, res = 0;for(int i=1; i<n; i++){if(bn[i] > bn[i-1]){if(an[i] - bn[i] > an[i-1] - bn[i-1]){res += num;++num;}else{num = 1;}}else{if(an[i] + bn[i] > an[i-1] + bn[i-1]){res += num;++num;}else{num = 1;}}}cout<< res;return 0;
}

结果res类型必须为longlongint ，int是不行的