区间计数
基准时间限制：1.5 秒 空间限制：262144 KB 分值: 80
两个数列 {An} ， {Bn}
，请求出Ans, Ans定义如下：
Ans:=Σni=1Σnj=i[max{Ai,Ai+1,...,Aj}=max{Bi,Bi+1,...,Bj}]
注：[ ]内表达式为真，则为1，否则为0.
1≤N≤3.5×1051≤Ai,Bi≤N
样例解释：
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
题解：
第一种做法是 两个单调栈 + 二分
两个数都同时维护一个单调递减的 栈
当元素出栈是我们可以确定以其为最大值所能掌管的一段区间，那么 在对应另一个栈内通过二分找到此值也能掌管一段区间
求出区间交就可以了
第二种做法比较类似
枚举固定最大值为x 的区间有哪些
在A数组中 假设x 所在位置为 i ，利用单调栈可以求出 其掌管范围 [L1,R1]， 对应的
在B数组中 假设x 所在位置为 i ，利用单调栈可以求出 其掌管范围 [L2,R2]，
那么抽出 [L1,i] [i,R1], [L2,i] [i,R2], 在二维坐标系上就是两个矩阵，求出矩阵面积交就可以了
#include <bits/stdc++.h>
inline long long read(){long long x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;}
using namespace std;
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 4e5 + , M = 1e3, inf = 2e9; int n,a[N],b[N];
int l[],r[],q[][N],pos[][N];
LL cal(int x,int p,int i) {
int ll = l[p], rr = r[p],ok = ll;
while(ll <= rr) {
if(q[p][mid] > x) {
ll = mid + ;
} else ok = mid,rr = mid - ;
}
// cout<<i<<" "<<p<<" "<<ok<<" "<<q[p][ok]<<" "<<x<<endl;
int mmp1,mmp2;
mmp1 = max(pos[p][ok-]+,pos[p^][r[p^]-]+);
mmp2 = i-; if(q[p][ok] == x)
return 1LL * max(min(pos[p^][r[p^]],pos[p][ok]) - mmp1+,)
* max(mmp2 - max(pos[p^][r[p^]],pos[p][ok]) + ,);
else return ;
}
int main() {
cin >> n;
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
for(int i = ; i <= n; ++i) scanf("%d",&b[i]);
l[] = l[] = ;
r[] = r[] = ;
pos[][] = pos[][] = ;
LL ans = ;
for(int i = ; i <= n; ++i) {
LL ret = ;
while(l[] <= r[] && a[i] >= q[][r[]]) {
ret += cal(q[][r[]],,i);
r[]--;
}
q[][++r[]] = a[i];pos[][r[]] = i;
while(l[] <= r[] && b[i] >= q[][r[]]) {
ret += cal(q[][r[]],,i);
r[]--;
}
q[][++r[]] = b[i];pos[][r[]] = i;
//cout<<"fuck "<<i<<" " << ret<<endl;
ans += ret;
}
while(l[] <= r[]) {
ans += cal(q[][r[]],,n+);
r[]--;
}
cout<<ans<<endl;
return ;
}