两个数列 ， ，请求出Ans, Ans定义如下：
注：[ ]内表达式为真，则为1，否则为0.
样例解释：
7个区间分别为：（1,4），（1,5），（2,4），（2,5），（3,3），（3,5），（4,5）
Input
第一行一个整数N 第二行N个整数Ai 第三行N个整数Bi
Output
一行，一个整数Ans
Input示例
5 1 4 2 3 4 3 2 2 4 1
Output示例
7
#include <iostream>
#include <stack>
#include <stdio.h>
using namespace std;
typedef long long int ll;
const int MAXN = 350005;
int a[MAXN];
int b[MAXN];
int n;
struct node
{
node()
{
val = 0;
num = 0;
}
node(int v, int n)
{
val = v;
num = n;
}
int val;
int num;
};
node prevMax[MAXN];
int bufA[MAXN];
int bufB[MAXN];
int find(int *p, int *q, int pos, int k)
{
int left = 0;
int right = pos;
int result = -1;
while (left < right-1)
{
int mid = left + (right-left)/2;
if (p[q[mid]] <= k)
{
right = mid;
}
else
{
left = mid;
}
}
if (p[q[right]] > k)
{
result = right;
}
else if (p[q[left]] > k)
{
result = left;
}
return result;
}
int main()
{
cin >> n;
ll result = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
}
ll sum = 0;
int p = -1;
int q = -1;
int r = -1;
for (int i = 0; i < n; i++)
{
int maxInput = max(a[i], b[i]);
while ((r >= 0) && (maxInput >= prevMax[r].val))
{
sum -= prevMax[r].num;
r--;
}
if ((p >= 0) && a[i] >= a[bufA[p]])
{
p = find(a, bufA, p, a[i]);
}
p++;
bufA[p] = i;
if ((q >= 0) && b[i] >= b[bufB[q]])
{
q = find(b, bufB, q, b[i]);
}
q++;
bufB[q] = i;
bool equal = false;
if (a[i] > b[i])
{
q = find(b, bufB, q, a[i]);
if (b[bufB[q+1]] == a[i])
{
q++;
equal = true;
}
}
else if (a[i] < b[i])
{
p = find(a, bufA, p, b[i]);
if (a[bufA[p+1]] == b[i])
{
p++;
equal = true;
}
}
else
{
equal = true;
}
if (equal)
{
int rightA = bufA[p];
int rightB = bufB[q];
int right = min(rightA, rightB);
int value = a[bufA[p]];
int leftA = (p == 0)? -1 : bufA[p-1];
int leftB = (q == 0)? -1 : bufB[q-1];
int left = max(leftA, leftB);
int num = (right-left);
sum += num;
r++;
prevMax[r] = node(value, num);
}
result += sum;
}
cout << result << endl;
return 0;
}
