51Nod1962 区间计数

这题与之前那道区间最值的题非常类似,依旧是二分区间,然后统计跨过中间点的区间贡献。

我们要选出小于等于和小于的,这样就可以算出相等的区间长了。

复杂度O(nlogn)

By:大奕哥

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;int n;
const int N=;
void add(ll x){ans+=x;}
int a[][N],p[][],l[][N],r[][N];
void solve(int ll,int rr)
{
if(ll==rr){if(a[][ll]==a[][ll])add();return;}
int mid=ll+rr>>;
solve(ll,mid);solve(mid+,rr);
for(int k=;k<=;++k)
{
l[k][mid]=a[k][mid];for(int i=mid-;i>=ll;--i)l[k][i]=max(l[k][i+],a[k][i]);
r[k][mid]=a[k][mid];for(int i=mid+;i<=rr;++i)r[k][i]=max(r[k][i-],a[k][i]);
}
for(int k=;k<=;++k)for(int i=;i<=;++i)p[k][i]=mid;
for(int i=mid;i>=ll;--i)
{
for(int k=;k<=;++k)
{
while(p[k][]<rr&&r[k][p[k][]+]<=l[k][i])p[k][]++;
while(p[k][]<rr&&r[k][p[k][]+]<l[k^][i])p[k][]++;
while(p[k][]<rr&&r[k][p[k][]+]<=l[k^][i])p[k][]++;
}
if(l[][i]==l[][i])add(max(,min(p[][],p[][])-mid));
else if(l[][i]>l[][i])add(max(,min(p[][],p[][])-p[][]));
else add(max(,min(p[][],p[][])-p[][]));
}
int pos=mid+;
for(int i=mid+;i<=rr;++i)
{
while(pos>ll&&max(l[][pos-],l[][pos-])<max(r[][i],r[][i]))--pos;
if(r[][i]==r[][i])add(max(,mid-pos+));
}
}
int main()
{
scanf("%d",&n);
for(int k=;k<=;++k)
for(int i=;i<=n;++i)
scanf("%d",&a[k][i]);
solve(,n);
printf("%lld\n",ans);
return ;
}
上一篇:pt-osc改表导致数据不一致案例分析


下一篇:中国电梯行业运行前景与品牌竞争分析报告2022版