# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
57867057 |
Practice:
lopare |
1117G
- 12
|
GNU C++11
|
Accepted
|
2012 ms
|
75348 KB
|
2019-07-28 00:53:39 |
2019-07-28 00:53:39 |
|
#include<bits/stdc++.h>
using namespace std;const int N=1e6+7;typedef long long ll;
ll bit[2][N],ans[N];int n,m,i,j,a[N],l[N],r[N],q[N],top;vector<int>e[N];
void add(int p,int x,int v){while(x<=n+3)bit[p][x]+=v,x+=x&-x;}
ll sum(int p,int x,ll res=0){while(x)res+=bit[p][x],x-=x&-x;return res;}
void go(){
for(i=1;i<=n;++i)e[i].clear();memset(bit,0,sizeof(bit));top=0;
for(i=1;i<=m;++i)e[l[i]].push_back(i);
for(i=n;i>=1;--i){
while(top&&a[q[top]]<a[i])top--;
j=n+1;if(top)j=q[top];
q[++top]=i;
add(0,i,-(i-1));
add(0,j,i-1);
add(1,i,1);
add(1,j,-1);
add(0,j,j-i);
for(auto&id:e[i])ans[id]+=sum(0,r[id]),ans[id]+=r[id]*sum(1,r[id]);
}
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;++i)scanf("%d",a+i);
for(i=1;i<=m;++i)scanf("%d",l+i);for(i=1;i<=m;++i)scanf("%d",r+i);
go();for(i=1;i<=m;++i)l[i]=n-l[i]+1,r[i]=n-r[i]+1,swap(l[i],r[i]);reverse(a+1,a+n+1);go();
for(i=1;i<=m;++i)printf("%lld%c",ans[i]-(r[i]-l[i]+1),i==m?'\n':' ');
}
Click to see test details