前言
【题目传送门】
难度：上蓝有余，上紫不足。
做题用时：(1h 45min)。（还因为一个符号写反的下饭问题调了一会)
一开始没有看到数字两两不同的限制条件，直接 gg 了，看了题解。
感觉不是特别难，但是也有点绕，主要是排序的东西太多了。
题解
首先根据数字从小到大排序，就能找到每一个数字的配对数字。（排序 1）
配对之后把每一对数字的位置按照右端点排序。（排序 2）
把询问离线，按照右端点排序。（排序 3）
接下来的操作大概和“HH 的项链”异曲同工了。
不断按照询问把当前区间右端点向右更新。
似乎就切掉了...?
代码
看着很长但是千万不要害怕，理清思路也就是一遍的事。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 3e5+10;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,m;
ll ans;
struct node //用来找好对
{
int val,id;
bool operator <(const node &oth) const
{return val<oth.val;}
}w[N];//n
int tot;
struct Pair//存好对
{
int l,r;
bool operator <(const Pair &oth) const
{return r<oth.r;}
}a[N<<1];//tot
struct ask//询问离线
{
int l,r,id;
bool operator <(const ask &oth) const
{return r<oth.r;}
}q[N];//m
struct BIT//树状数组
{
int c[N];
inline void update(int x,int v)
{
for(int i=x;i<=n;i+=i&-i) c[i]+=v;
}
inline int query(int x)
{
int ret=0;
for(int i=x;i;i-=i&-i) ret+=c[i];
return ret;
}
}tr;
void find_pair()//找好对
{
sort(w+1,w+n+1);
for(int i=1;i<=n;i++)
{
if(i==1) a[++tot]=(Pair){min(w[i].id,w[i+1].id),max(w[i].id,w[i+1].id)};
else if(i==n) a[++tot]=(Pair){min(w[i].id,w[i-1].id),max(w[i].id,w[i-1].id)};
else
{
if(abs(w[i].val-w[i-1].val)==abs(w[i].val-w[i+1].val))
{
a[++tot]=(Pair){min(w[i].id,w[i+1].id),max(w[i].id,w[i+1].id)};
a[++tot]=(Pair){min(w[i].id,w[i-1].id),max(w[i].id,w[i-1].id)};
}
else if(abs(w[i].val-w[i-1].val)>abs(w[i].val-w[i+1].val))
a[++tot]=(Pair){min(w[i].id,w[i+1].id),max(w[i].id,w[i+1].id)};
else a[++tot]=(Pair){min(w[i].id,w[i-1].id),max(w[i].id,w[i-1].id)};
}
}
sort(a+1,a+tot+1);
//for(int i=1;i<=tot;i++) printf("Pair(%d,%d)
",a[i].l,a[i].r);
}
void work()
{
int pl=1;
for(int i=1;i<=m;i++)
{
while(pl<=tot&&a[pl].r<=q[i].r)
{
tr.update(a[pl].l,1);
pl++;
}
// printf("query(%d,%d) : return %d
",q[i].l,q[i].r,tr.query(q[i].r)-tr.query(q[i].l-1));
ans+=1LL*q[i].id*(pl-1-tr.query(q[i].l-1));
}
printf("%lld
",ans);
return;
}
int main()
{
n=read(),m=read();
if(n==1) return puts("0"),0;//特判
for(int i=1;i<=n;i++) w[i].val=read(),w[i].id=i;
find_pair();
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1);
work();
return 0;
}
/*
5 2
1 2 3 4 5
2 4
1 5
*/