题解 [ABC379F] Buildings 2
cjh20090318
·
·
题解
题意
有 N 幢楼房，第 i 幢楼房的高度为 H_i。
能从建筑 i 看到建筑 j 需要满足的条件是 \nexists k \in (i,j) \cap \mathbb{Z}, H_k > H_j。
有 Q 次询问，每次询问给定 (l,r)，求 (r+1,n] 中有多少个建筑物可以同时被 l 和 r 看到。
分析
将看到的定义转化成 \forall k\in(i,j), H_k \le H_j，也就是说 \max\limits_{k=i+1}^{j-1} H_k \le H_j。
因为 l<r，所以 \max\limits_{k=l+1}^{j-1} H_k \ge \max\limits_{k=r+1}^{j-1} H_k，也就是说能被 l 看到的 r 一定也能看到，所以就只需要考虑 l。
设 a_i 表示最后一个在 i 之前且这个位置的高度大于 H_i，只有当 a_i \le l 时这个位置才能被 l 看见。
于是问题就变成了 (r,N] 中有多少个 a_i \le l，可以离线下来用树状数组求解。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<vector>
#define MAXN 200002
using namespace std;
typedef pair<int,int> PII;
int n,q;
int h[MAXN],a[MAXN],t[MAXN],p=0;
int ans[MAXN];
vector<PII> G[MAXN];
template<typename T>
struct fenwick_tree{
public:
fenwick_tree(int _SIZE=0):SIZE(_SIZE){dt=new T[SIZE+1]();memset(dt,0,sizeof(T)*(SIZE+1));}
~fenwick_tree(){delete[] dt;}
void add(int x,const T&v){for(;x<=SIZE;x+=x&-x)dt[x]+=v;}
inline T sum(int x)const{T ret(0);for(;x;x^=x&-x)ret+=dt[x];return ret;}
private:
T*dt;
int SIZE;
};
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&h[i]);
while(p&&h[t[p]]<=h[i]) --p;//维护单调栈找到最后一个比他大的。
a[i]=t[p],t[++p]=i;
}
for(int i=1,l,r;i<=q;i++) scanf("%d%d",&l,&r),G[r].emplace_back(l,i);//将询问加入。
fenwick_tree<int> T(n);//树状数组。
p=0;
for(int i=n;i>0;--i){
for(const PII&x:G[i]) ans[x.second]=T.sum(x.first)+p;//树状数组中查询小于等于 l 的个数，还要加上 a 等于 0 的数量。
if(a[i]) T.add(a[i],1);else ++p;//树状数组单点加。
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
```