题意：
给定长度为n的排列p， 问有多少个子区间[l,r]，满足区间最小值=l，且区间最大值=r
数据范围：n<=1e6
解法：
对于每个i
,如果a
[i
]<=i
,那么位置i有可能作为某些fair区间的右端点
.
对于每个i
,如果a
[i
]>=i
,那么位置i有可能作为某些fair区间的左端点
.
计算出i作为最大值时能扩展的最左位置ma
[i
].
计算出i作为最小值时能扩展的最右位置mi
[i
].
---
对于位置i
:
1.如果pos
[i
]>=i且mi
[i
]>=pos
[i
],则i作为左端点的合法区间为
[pos
[i
],mi
[i
]],在这个区间内i可以作为左端点
.
2.如果pos
[i
]<=i且ma
[i
]<=pos
[i
],则i作为右端点的合法区间为
[ma
[i
],pos
[i
]]
对于每个右端点区间
[ma
[i
],pos
[i
]],统计里面可以有多少个左端点即可
.
可以将左端点区间设为若干操作
,离线之后排序
,
即枚举右端点r
,用树状数组
+扫描线计算对于每个r
,[ma
[r
],pos
[r
]]内有多少个满足的l
.
(可以用树状数组
+扫描线做是因为可以抽象为求计算二维平面上的子矩阵权值和
)
---
参考
:
https
://www
.cnblogs
.com
/Willems
/p
/13661520.html
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e6+5;
struct BIT
{
int c
[maxm
];
int lowbit(int i
){return i
&-i
;}
void add(int i
,int t
){while(i
<maxm
)c
[i
]+=t
,i
+=lowbit(i
);}
int ask(int i
){int ans
=0;while(i
){ans
+=c
[i
],i
-=lowbit(i
);}return ans
;}
}T
;
struct QQ
{
int pos
,idx
,op
;
}q
[maxm
<<1];
int a
[maxm
];
int ma
[maxm
];
int mi
[maxm
];
int pos
[maxm
];
int n
;
bool cmp(QQ a
,QQ b
){
return a
.pos
<b
.pos
;
}
signed main(){
ios
::sync_with_stdio(0);cin
.tie(0);
cin
>>n
;
for(int i
=1;i
<=n
;i
++)cin
>>a
[i
];
for(int i
=1;i
<=n
;i
++)pos
[a
[i
]]=i
;
for(int i
=1;i
<=n
;i
++){
ma
[i
]=i
;
if(a
[i
]<=i
){
while(ma
[i
]>1&&a
[ma
[i
]-1]<=i
){
ma
[i
]=ma
[ma
[i
]-1];
}
}
}
for(int i
=n
;i
>=1;i
--){
mi
[i
]=i
;
if(a
[i
]>=i
){
while(mi
[i
]<n
&&a
[mi
[i
]+1]>=i
){
mi
[i
]=mi
[mi
[i
]+1];
}
}
}
int m
=0;
for(int i
=1;i
<=n
;i
++){
if(pos
[i
]>=i
&&mi
[i
]>=pos
[i
]&&ma
[i
]<=pos
[i
]){
q
[++m
]={pos
[i
],i
,1};
q
[++m
]={mi
[i
]+1,i
,-1};
}
}
sort(q
+1,q
+1+m
,cmp
);
int ans
=0;
int k
=1;
for(int i
=1;i
<=n
;i
++){
while(k
<=m
&&q
[k
].pos
<=i
){
T
.add(q
[k
].idx
,q
[k
].op
);
k
++;
}
if(pos
[i
]<=i
&&ma
[i
]<=pos
[i
]){
ans
+=T
.ask(pos
[i
])-T
.ask(ma
[i
]-1);
}
}
cout
<<ans
<<endl
;
return 0;
}
