题目描述
给定(n)个数(a_1,⋯ ,a_n)
对于一组配对((x,y))，若对于所有的(i=1,2,⋯ ,n)，满足(∣ax−ay∣)≤(∣ax−ai∣)((i≠x))，则称((x,y))为一组好的配对.
给出若干询问，每次询问区间([l,r])中含有多少组好的配对。
即，取(x,y(l≤x,y≤r且x≠y)) ，问有多少组((x,y))是好的配对。
思路
这道题只有查询操作，没有修改和强制在线，所以我们可以离线做。
要用到的方法：类似权值树状数组的，排序，还有一点莫队的思想
给原数组由小到大排序，询问数组左端点由大到小排序，方便我们统计答案时可以一直往左找。
预处理出所有好对的左端点和右端点。
询问一个区间([l,r])时，把所有左端点大于等于(l)的好对的右端点加入树状数组，统计右端点(le r)的数量就好了
由于询问的左端点一直向左扩展，所以加过的右端点不需要删。
Code
#include<bits/stdc++.h>
#define N (300010)
#define INF (2e9)
#define lb(x) (x&(-x))
#define ll long long
using namespace std;
struct Q{int l,r,v;}q[N];//询问数组
struct NUM{int v,id;}a[N];//值数组
struct P{int l,r;}p[N];//好对数组
int n,m,cnt;
ll ans,c[N];//树状数组
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline bool cmp2(P a,P b){return a.l<b.l;}
inline bool cmp1(NUM a,NUM b){return a.v<b.v;}
inline bool cmp(Q a,Q b){return a.l>b.l;}
inline void add(int x,ll v){for(int i=x;i<=n;i+=lb(i)) c[i]+=v;}
inline ll sum(int x){
ll res=0;
while(x){
res+=c[x];
x-=lb(x);
}
return res;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i].v=read(),a[i].id=i;
for(int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read();
q[i].v=i;
}
sort(q+1,q+1+m,cmp);
sort(a+1,a+1+n,cmp1);
a[0].v=-INF,a[n+1].v=INF;
for(int i=1;i<=n;i++){
if(a[i].v-a[i-1].v<=a[i+1].v-a[i].v) p[++cnt]=(P){min(a[i-1].id,a[i].id),max(a[i-1].id,a[i].id)};
if(a[i].v-a[i-1].v>=a[i+1].v-a[i].v) p[++cnt]=(P){min(a[i].id,a[i+1].id),max(a[i].id,a[i+1].id)};
}
//预处理好对
sort(p+1,p+1+cnt,cmp2);
for(int i=1;i<=m;i++){
while(p[cnt].l>=q[i].l) add(p[cnt].r,1),cnt--;//拓展左端点
ll now=sum(q[i].r);
ans+=q[i].v*now;
}
printf("%lld
",ans);
return 0;
}