【BZOJ4979】凌晨三点的宿舍（分治）

三点的宿舍（分治）"/>

【BZOJ4979】凌晨三点的宿舍（分治）

传送门

给定一个序列，每个位置一个值 h i h_i hi​
定义 2 2 2个位置 ( i , j ) , i &lt; j (i,j),i&lt;j (i,j),i<j的距离为 j − i + h i + h j − 2 ∗ m i n ( h [ k ] , k ∈ [ i , j ] ) j-i+h_i+h_j-2*min(h[k],k\in[i,j]) j−i+hi​+hj​−2∗min(h[k],k∈[i,j])
求有多少对节点的距离小于等于 k k k
n ≤ 2 e 5 n \le2e5 n≤2e5

考虑分治
对于当前区间 l , m i d , r l,mid,r l,mid,r
令 m n i mn_i mni​表示 i i i到 m i d mid mid的最小值
求有多少 i ∈ [ l , m i d ] , j ∈ [ m i d + 1 , r ] i\in[l,mid],j\in[mid+1,r] i∈[l,mid],j∈[mid+1,r]满足
j − i + h i + h j − 2 ∗ m i n ( m n i , m n j ) ≤ k j-i+h_i+h_j-2*min(mn_i,mn_j)\le k j−i+hi​+hj​−2∗min(mni​,mnj​)≤k
假设此时 m i n = m n i min=mn_i min=mni​，另一种会在相反的 i , j i,j i,j统计到
则 h i − i − 2 ∗ m n i ≤ k − j − h j h_i-i-2*mn_i\le k-j-h_j hi​−i−2∗mni​≤k−j−hj​
对每个 i i i插入树状数组后对 j j j查询就是了
复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mk make_pair
inline int read(){char ch=getchar();int res=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();return res*f;
}
const int N=200005;
const int Mr=600006;
const int M=1000005;
#define lowbit(x) (x&(-x))
struct Bit{int tr[M];inline void update(int p,int k){p+=Mr;for(;p<M;p+=lowbit(p))tr[p]+=k;}inline int query(int p,int res=0){p=min(p+Mr,M-1);for(;p;p-=lowbit(p))res+=tr[p];return res;}
}A,B;
int n,m,k,h[N];
ll ans;
vector<pii> q;
struct room{int x,y,val;room(int _x=0,int _y=0,int _val=0):x(_x),y(_y),val(_val){}friend inline bool operator <(const room &a,const room &b){return a.val<b.val;}
};
inline void calc(const vector<pii> &q){for(int 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<pii> &vec){if(!vec.size())return;if(l==r)return calc(vec);int mid=((l+r)>>1);vector<pii> ql,qr;for(int i=0;i<vec.size();i++){if(vec[i].first<=mid)ql.push_back(vec[i]);else qr.push_back(vec[i]);}solve(l,mid,ql),solve(mid+1,r,qr);vector<room> now;for(int i=ql.size()-1,p=mid,mn=h[p];~i;p--){mn=min(mn,h[p]);while(~i&&ql[i].first==p){now.push_back(room(p,ql[i].second,min(mn,ql[i].second)));i--;}}for(int i=0,p=mid+1,mn=h[p];i<qr.size();p++){mn=min(mn,h[p]);while(i<qr.size()&&qr[i].first==p){now.push_back(room(p,qr[i].second,min(mn,qr[i].second)));i++;}}sort(now.begin(),now.end());for(int i=0;i<now.size();i++){room &t=now[i];if(t.x<=mid){A.update(t.y-t.x-2*t.val,1);ans+=B.query(k+t.x-t.y);}else{B.update(t.y+t.x-2*t.val,1);ans+=A.query(k-t.x-t.y);}}for(int i=0;i<now.size();i++){room &t=now[i];if(t.x<=mid)A.update(t.y-t.x-2*t.val,-1);else B.update(t.y+t.x-2*t.val,-1);}
}
int main(){n=read(),k=read();for(int i=1;i<=n;i++)h[i]=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read();q.push_back(mk(x,y));}sort(q.begin(),q.end());solve(1,n,q);cout<<ans;
}