P5677 [GZOI2017]配对统计

测试点信息

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define int long long 
using namespace std;
typedef long long ll;

const int mod=1e9+7;
const int N=5e6+5;
int n,m,res,ans[N];

vector<pair<int,int> > v;

struct node
{
	int idx,value;
	bool operator<(const node& a)const{
		return value<a.value;
	}
}a[N];

struct question
{
	int left,right,idx;
	bool operator<(const question& a)const{
		if(left==a.left)return right<a.right;
		return left<a.left;
	}
}q[N];

struct NODE
{
	int sum;
}tr[N<<2];

inline int ls(int pos){return pos<<1;}
inline int rs(int pos){return pos<<1|1;}
inline void push_up(int pos){tr[pos].sum=tr[ls(pos)].sum+tr[rs(pos)].sum;}

void update(int pos,int l,int r,int k)
{
	if(l==r){tr[pos].sum++;return;}
	int mid=(l+r)>>1;
	if(k<=mid) update(ls(pos),l,mid,k);
	else update(rs(pos),mid+1,r,k);
	push_up(pos); return;
}

int query(int pos,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return tr[pos].sum;
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans+=query(ls(pos),l,mid,L,R);
	if(R>mid)  ans+=query(rs(pos),mid+1,r,L,R);
	return ans; 
}

inline int read()
{
	int a=0,f=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
		if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())
		a=(a<<3)+(a<<1)+ch-'0';
	return a*f;
}

signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		a[i].value=read();
		a[i].idx=i;
	}
	v.clear();
	sort(a+1,a+n+1);
	v.push_back(make_pair(min(a[2].idx,a[1].idx),max(a[1].idx,a[2].idx)));
	v.push_back(make_pair(min(a[n].idx,a[n-1].idx),max(a[n-1].idx,a[n].idx)));
	for(int i=2;i<n;i++)
	{
		int x=abs(a[i].value-a[i-1].value);
		int y=abs(a[i+1].value-a[i].value);
		if(x<=y) v.push_back(make_pair(min(a[i].idx,a[i-1].idx),max(a[i-1].idx,a[i].idx)));
		if(y<=x) v.push_back(make_pair(min(a[i+1].idx,a[i].idx),max(a[i].idx,a[i+1].idx)));
	}
	sort(v.begin(),v.end());
	for(int i=1;i<=m;i++)
	{
		q[i].left=read();
		q[i].right=read();
		q[i].idx=i;
	}
	sort(q+1,q+m+1);
	int now=(int)v.size()-1;
	for(int i=m;i>=1;i--)
	{
		while(v[now].first>=q[i].left)
			update(1,1,n,v[now--].second);
		ans[q[i].idx]=query(1,1,n,q[i].left,q[i].right);
	}
	for(int i=1;i<=m;i++)
		res+=ans[i]*i; 
	printf("%lld\n",res);
	return 0;
}