2018.10.29【BZOJ4979】[Lydsy1708月赛]凌晨三点的宿舍（分治）（树状数组）

树状数组）"/>

2018.10.29【BZOJ4979】[Lydsy1708月赛]凌晨三点的宿舍（分治）（树状数组）

传送门

讲个故事：

这是一个悲伤的故事。

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

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

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

最后学习了 D Z Y O DZYO DZYO的写法，结果一发就 A A A了？？？？

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

感谢 D Z Y O DZYO DZYO在我绝望无助的时候对我的无私帮助%%%%%%%%%%%%%%%%%。

思路：

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

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

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

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

计算出每个点到分治中心的 m i n n minn minn，那么 i i i能够达到 j j j的条件就是 h i + h j + j − i − 2 ∗ m i n { m i n n i , m i n n j } ≤ k h_i+h_j+j-i-2*min\{minn_i,minn_j\}\leq k hi​+hj​+j−i−2∗min{minni​,minnj​}≤k，我们只讨论当 m i n = m i n n i min=minn_i min=minni​时的情况，另外的情况可以类似推导出来。

那么原式可化为 h i − i − 2 ∗ m i n n i ≤ k − h j − j h_i-i-2*minn_i\leq k-h_j-j hi​−i−2∗minni​≤k−hj​−j。
好的这道题差不多就要完了。

上面的式子告诉我们，每一个 j j j在当前分治中能够到达多少个 m i n n minn minn较小的 i i i，就是查询有多少个 i i i满足 h i − i − 2 ∗ m i n n i ≤ k − h j − j h_i-i-2*minn_i\leq k-h_j-j hi​−i−2∗minni​≤k−hj​−j。
即查询前缀个数和。

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

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

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc getchar
#define pc putchar
#define cs constinline 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;
}