P5677

Aryper · 2021-07-29 13:20:59 · 个人记录

[GZOI2017]配对统计

这个真的蛮难想的。。。

本来想把不等式变形的。。。后来发现直接盯着不等式找性质就可以了。。。简单来说就是对于 a_x 来说，与其配对的 a_y 满足 |a_y-a_x| 最小。

然后排序检查相邻的两个数即可，可在 O(n) 下找到所有的数对。

那么现在处理这个计数。

最基本的原理是：将询问按照 r 从小到大排序，接着将数对按照较大的数从小到大排序后，用一个指针指着数对 “数对中较大的数” \le “询问中的 r ” 的数对的个数记为 cnt_1 ，“数对中较小的数” \le “询问中的 l-1 ” 的数对个数记为 cnt_2 ，那么对于第 i 个询问， Ans_i=cnt_1-cnt_2 。

那么根据这个原理，我们设计了一个离线算法，因为这个 cnt_1 的计数满足单调性，所以能在 O(n) 下完成。

然后比较棘手的是 cnt_2 ，我们就把已经计入 cnt_1 的数对的较小的数加入树状数组中，到时候再以单次 O(\log n) 的复杂度询问 cnt_2 即可。

代码：

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

const ll N=3e5;

struct node{
    ll v,id;
}a[N+5];

struct _node{
    ll l,r;
}pr[N*2+5];

struct __node{
    ll l,r,id;
}q[N+5];

ll n,m,tot,j,ans;

ll c[N+5];

void _add(ll x) {
    for(;x<=n;x+=x&-x) c[x]++;
}

ll ask(ll x) {
    ll res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}

void add(ll l,ll r) {
    if(l>r) swap(l,r);
    pr[++tot].l=l;pr[tot].r=r;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

bool cmp(node x,node y) {
    return x.v<y.v;
}

bool _cmp(_node x,_node y) {
    return x.r<y.r;
}

bool __cmp(__node x,__node y) {
    return x.r<y.r;
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        a[i].v=read();a[i].id=i;
    }

    sort(a+1,a+n+1,cmp);
    add(a[1].id,a[2].id);
    add(a[n-1].id,a[n].id);
    for(ll i=2;i<=n-1;i++) {
        if(a[i].v-a[i-1].v>=a[i+1].v-a[i].v) add(a[i].id,a[i+1].id);
        if(a[i].v-a[i-1].v<=a[i+1].v-a[i].v) add(a[i-1].id,a[i].id);
    }

    sort(pr+1,pr+tot+1,_cmp);

    for(ll i=1;i<=m;i++) {
        q[i].l=read();q[i].r=read();q[i].id=i;
    }

    sort(q+1,q+m+1,__cmp);

    j=1;
    for(ll i=1;i<=m;i++) {
        while(pr[j].r<=q[i].r&&j<=tot) {
            _add(pr[j].l);
            j++;
        }
        ans=ans+q[i].id*(j-1-ask(q[i].l-1));
    }

    write(ans);

    return 0;
}