传送门

---

讲个故事：

这是一个悲伤的故事。

我一个人，由于做过一道弱化版的题目，看出了正解，从昨天半夜11：30开始肝这道题，一顿乱搞之后过了样例，然后一直$RE$，期间重构了一次。

这个故事告诉我们注意负数下标是多么的重要。

然后今天早上重构了三次，一直WA。。。

最后学习了$DZYO$的写法，结果一发就$A$了？？？？

这个故事告诉我们，选择一个编程复杂度不高的写法是多么的重要。

感谢$DZYO$在我绝望无助的时候对我的无私帮助%%%%%%%%%%%%%%%%%。

思路：

一看$O(n^2)$暴力其实是很好打的，枚举每一个宿舍$O(n)$，先把和它同一列在它下面的处理完，然后$O(n)$向右边扫一遍，更新遇到的最低的房顶$minn$，两个房间$i,j$之间的距离就是$h_i+h_j+j-i-2\ast minn$

那么考虑这个求出的$minn$能否帮助我们处理更多信息。

显然我们如果选择了某一个点为中心，处理出所有其他点到它路径上的$minn$。那么每一个它左边的点到它右边的点的路径上的$minn$都能够知道。就是两者取小就行了。

那么考虑分治，每次二分选择分治中心（实际上，我们的分治中心不是某一个点，而是某两栋建筑的分界线）。

计算出每个点到分治中心的$minn$，那么$i$能够达到$j$的条件就是$h_i+h_j+j-i-2\ast min\{min{n}_i,min{n}_j\}\le k$，我们只讨论当$min=min{n}_i$时的情况，另外的情况可以类似推导出来。

那么原式可化为$h_i-i-2\ast min{n}_i\le k-h_j-j$。 好的这道题差不多就要完了。

上面的式子告诉我们，每一个$j$在当前分治中能够到达多少个$minn$较小的$i$，就是查询有多少个$i$满足$h_i-i-2\ast min{n}_i\le k-h_j-j$。 即查询前缀个数和。

我们维护一左一右两个树状数组，支持单点加，查询前缀和就行了，为保证当前询问出来的所有$i$的$minn$都比$j$小，我们需要先对所有节点按照$minn$排个序。

然后就是实现上的一些细节，这个请读者自己照着代码体会一下吧。

---

代码：

#include<bits/stdc++.h> using namespace std; #define ll long long #define re register #define gc getchar #define pc putchar #define cs const inline int getint(){ re int num; re char c; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num<<1)+(num<<3)+(c^48); return num; } cs int B=200005; cs int N=B*5,L=B*3,R=B*5; #define lowbit(x) (x&(-x)) struct BIT{ int val[R]; inline void add(int pos,int v){ pos+=L; for(;pos<R;pos+=lowbit(pos))val[pos]+=v; } inline int query(int pos,int res=0){ pos=min(pos+L,R-1); for(;pos;pos-=lowbit(pos))res+=val[pos]; return res; } }b0,b1; int n,m,k,h[B]; struct node{ int x,y,val; node(cs int &_x=0,cs int &_y=0,cs int &_val=0):x(_x),y(_y),val(_val){} friend bool operator<(cs node &a,cs node &b){ return a.val<b.val; } }; ll ans; inline void work(vector<pair<int,int> > &q){ for(int re i=0,j=0;i<q.size();++i){ while(q[j].second+k<q[i].second)++j; ans+=i-j; } } inline void solve(int l,int r,vector<pair<int,int> > &q){ if(q.empty())return ; if(l==r)return work(q); int mid=(l+r)>>1; vector<pair<int,int> > ql,qr; for(int re i=0;i<q.size();++i) (q[i].first<=mid?ql:qr).push_back(q[i]); solve(l,mid,ql); solve(mid+1,r,qr); vector<node> data; for(int re i=ql.size()-1,now=mid,minn=h[now];~i;--now){ minn=min(minn,h[now]); while(~i&&ql[i].first==now){ data.push_back(node(now,ql[i].second,min(minn,ql[i].second))); --i; } } for(int re i=0,now=mid+1,minn=h[now];i<qr.size();++now){ minn=min(minn,h[now]); while(i<qr.size()&&qr[i].first==now){ data.push_back(node(now,qr[i].second,min(minn,qr[i].second))); ++i; } } sort(data.begin(),data.end()); for(int re i=0;i<data.size();++i){ node &t=data[i]; if(t.x<=mid){ b0.add(t.y-t.x-2*t.val,1); ans+=b1.query(k+t.x-t.y); } else{ b1.add(t.y+t.x-2*t.val,1); ans+=b0.query(k-t.x-t.y); } } for(int re i=0;i<data.size();++i){ node &t=data[i]; if(t.x<=mid)b0.add(t.y-t.x-2*t.val,-1); else b1.add(t.y+t.x-2*t.val,-1); } } vector<pair<int,int> > q; signed main(){ n=getint(); k=getint(); for(int re i=1;i<=n;++i)h[i]=getint(); m=getint(); for(int re i=1;i<=m;++i){ int u=getint(),v=getint(); q.push_back(make_pair(u,v)); } sort(q.begin(),q.end()); solve(1,n,q); cout<<ans; return 0; }