https://www.luogu.com.cn/problem/P5677
最开始读题的时候没有读的太懂，以为i是在选定区间内给的，实际上不是，这道题的意思应该是在l和r的区间内找出有多少个好的配对，这里好的配对是对于整个区间来说的，既然是对于整个区间，我们就不难想到找出好的配对的方法，所以我们可以先找出所有好的配对，然后用树状数组维护个数。
如何找出好的配对呢？我们先来分析什么叫好的配对，选定的两点间距离比其中一点到除对方外任意一点的距离都小，也就是说这两点差的绝对值最小，这样的话，这两个点在sort排序后一定相邻，这个很好推出，于是我们只要考虑这个点的另一个配对是左边的点还是右边的点，写一个判断就行了，注意特判1和n。
找出好的配对来，就又向答案接近了一步，现在我们只要进行更新就行了，这里的更新我们枚举左端点，上一步我们已经求出了好的配对（l，r）如果查询的左端点在l的左边，那么从r开始向右就一定至少存在一个好的配对，所以让树状数组中的r对应的位置更新就行。注意我们要倒序枚举左端点，因为我们加入r后所产生的配对只能是在询问区间包含l的情况下才有效。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 const int N=3e5+10; 7 #define ll long long 8 struct Node{ 9 ll val,id; 10 bool operator < (const Node&A)const{ 11 return val<A.val; 12 } 13 }a[N]; 14 vector<int> point[N],p1[N],p2[N]; 15 ll lowbit(ll x){ 16 return x&-x; 17 } 18 void Ins(ll x,ll y){ 19 point[min(x,y)].push_back(max(x,y));//min表示左端点，max表示右端点 20 } 21 ll m,n,c[N]; 22 void Add(ll x){ 23 while(x<=n){ 24 c[x]++; 25 x+=lowbit(x); 26 } 27 } 28 ll query(ll x){ 29 ll ans=0; 30 while(x){ 31 ans+=c[x]; 32 x-=lowbit(x); 33 } 34 return ans; 35 } 36 ll ans[N]; 37 int main(){ 38 scanf("%lld%lld",&n,&m); 39 for(int i=1;i<=n;i++){ 40 scanf("%lld",&a[i].val);a[i].id=i; 41 } 42 sort(a+1,a+n+1); 43 for(int i=1;i<=n;i++){ 44 int Min=0x3f3f3f3f; 45 if(i!=1&&a[i].val-a[i-1].val<Min){ 46 Min=a[i].val-a[i-1].val; 47 } 48 if(i!=n&&a[i+1].val-a[i].val<Min){ 49 Min=a[i+1].val-a[i].val; 50 } 51 if(i!=1&&a[i].val-a[i-1].val==Min)Ins(a[i].id,a[i-1].id); 52 if(i!=n&&a[i+1].val-a[i].val==Min)Ins(a[i+1].id,a[i].id);//取两个端点最小值 53 } 54 for(int i=1;i<=m;i++){ 55 int l,r; 56 scanf("%d%d",&l,&r); 57 p1[l].push_back(r); 58 p2[l].push_back(i);//记录坐标位置 59 } 60 for(int i=n;i>=1;i--){ 61 for(int j=0;j<(int)point[i].size();j++)Add(point[i][j]);//倒序查询 62 for(int j=0;j<(int)p1[i].size();j++)ans[p2[i][j]]=query(p1[i][j]); 63 } 64 ll sum=0; 65 for(int i=1;i<=m;i++) 66 sum+=ans[i]*i; 67 printf("%lld\n",sum); 68 }
原文：https://www.cnblogs.com/anyixing-fly/p/12461717.html