数点,偏序,

· · 算法·理论

简单记录一下基础的数点,

二维数点偏序

P10814(二维数点模板)

原题我们转化一下,

我们将问题变成在一个平面内,对于每一个询问,求出在 [l,r]\times[0,k] 的这样一个矩形内的点的个数,对于 [l,r] 我们简单差分成两个询问,求 [0,r]\times[0,k]-[0,l-1]\times[0,k],对于一个询问 (x,k) 问题变成求满足 (a,b)\le(x,k) 的点的个数,我们将 x 当成一维依次遍历,跑扫描线进行加点,当碰到 (x,k) 的询问时,就可以查询出满足情况的点对数量了,最后再左右一加一减就能算出贡献了,具体实现考虑树状数组进行单点加,前缀和查询。

当然你也可以 CDQ 分治,这个在下面讲。

三位数点偏序

P3810(三位数点模板)

这个题询问本质求满足 (a,b,c)\le(x,y,z) 的点的个数,也就是在 P10814 的基础上再加一维,

CDQ 分治

我们考虑对于 a 先进行个排序,我们直接把 a 给消掉了,不用管他。然后问题变成了 (b,c) 上的二维数点,这个时候可定会有人觉得我再把 b 排个序跑二维数点就做完了,恭喜你的做法飞起来了。我们考虑到前提是 a 是有序的,而你再暴力排 b 必然会破坏 a 的顺序,不够鲜活,而我们需要思考一种鲜活的做法,可以在 (b,c) 的二维数点的时候消除 a 的影响,我们考虑 CDQ 分治。

我们对于整个区间 [l,r] 先按 a 排序,我们将区间分成 [l,mid],(mid,r] 这两部分,每一部分的贡献自己算一遍,这样对于这一个函数里,我们需要考虑的贡献就是左边区间和右边区间配对而产生的答案了,我们注意到,左边区间的 a 是必然不大于右边区间的 a,也就是对于跨区间的贡献,我们可以消掉 a 的影响。

我们既然已经把 a 的影响给消除了,在这个区间内我们就可以对于 (b,c) 爽二维数点了,考虑按照 b 在两个区间内分别排序,用双指针保证 b 的顺序性,然后树状数组记录并统计 c 统计,这个题就做完了。

有一个坑点在于对于完全相同的点,在将其分到两个区间的时候会少算情况,少算情况的原因无疑是因为这个点在里面放了很多,因此我们直接离散化将其缩到一个点上即可,对于每一次贡献,从原本的加 1 改为加实际的点数即可,当询问不等于任何点的时候,我们将询问当成特殊的点压入来处理,当存在下界的时候,我们再额外进行一个容斥,将其拆成多个系数为 1 或 -1 的独立询问,计算贡献。

CDQ 分治本质通过类似归并的操作人为地消掉一维的影响,是一种算是常见的手段,你也可以直接用 CDQ 二维数点来去掉数据结构(貌似会更劣),也可以 CDQ 套二维数点 CDQ 来实现三维数点,还可以 CDQ 套 CDQ 实现四维数点。

在复杂度方面 CDQ 内部处理是 O(n\log n) 的,对于整体 CDQ 是 T(n)=2T(\frac{n}{2})+O(n\log n) 的,总体就是 O(n\log^2 n) 的,算是比较优秀的求解方式。 ::::info[代码实现]

#include<bits/stdc++.h>
#define lowbit x&(-x)
#define ll long long
using namespace std;
const int N=3e5+5;
struct points{
    int a,b,c;
    int ARIS,KEI;
}a[N],b[N];
struct bits{
    int tr[N];
    void update(int x,int k){
        while(x<=N){
            tr[x]+=k;
            x+=lowbit;
        }
    }
    int query(int x){
        int ans=0;
        while(x){
            ans+=tr[x];
            x-=lowbit;
        }
        return ans;
    }
}tr;
bool cmp(points x,points y){
    if(x.a==y.a){
        if(x.b==y.b){
            return x.c<y.c;
        } 
        return x.b<y.b;
    }
    return x.a<y.a;
}
bool cmpp(points x,points y){
    return x.b<y.b;
}
int n,m,k,f[N];
void CDQ(int pl,int pr){
    if(pl==pr){
        return ;
    }
    int mid=(pl+pr)>>1;
    CDQ(pl,mid);CDQ(mid+1,pr);
    sort(a+pl,a+1+mid,cmpp);sort(a+1+mid,a+1+pr,cmpp);
    int l=pl,r=mid+1;
    for(;r<=pr;r++){
        while(a[l].b<=a[r].b&&l<=mid){
            tr.update(a[l].c,a[l].KEI); 
            l++;
        }
        a[r].ARIS+=tr.query(a[r].c); 
    }
    for(int i=pl;i<l;i++){
        tr.update(a[i].c,-a[i].KEI);
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); 
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>b[i].a>>b[i].b>>b[i].c;
    }
    sort(b+1,b+1+n,cmp);
    int tot=0,q=0;
    for(int i=1;i<=n;i++){
        q++;
        if(b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c){
            a[++tot]=b[i];
            a[tot].KEI=q;
            q=0;
        }
    }
    m=n;
    n=tot;
    CDQ(1,n);
    for(int i=1;i<=n;i++){
        f[a[i].ARIS+a[i].KEI-1]+=a[i].KEI;
    }
    for(int i=0;i<m;i++){
        cout<<f[i]<<'\n';
    }
    return 0;
}/*
再见了,王女 
*/

::::

分块

这类计数题目基本都存在分块做法/咦,

这一部分参考了 NATURAL6 的 这篇题解。

我们跟前面的思路一样,我们考虑先消掉 a 的影响,很明显我们考虑动态地去加点,对于点,我们按照 a 先进行排序后再加,这样每加入一个点,问题变成了对于 (b,c) 的二位数点问题,n=10^5 所以肯定是可以使用根号算法来过掉这道题的。

我们有一个最简单的暴力算法,对于每一个点,加入以后我们计算二位前缀和,实现 n^2 插入,这肯定是劣完了的。我们对于排完序后的序列进行分块,对于每一个询问,在块内进行暴力查找,在块外前缀和维护,对于每一个块,我们对他前面的点进行二位前缀和,我们注意到此时我们更新的是当前的块的答案,也就是说我们并不关心前面的点的 b,c 实际是哪个数,我们只关心其相对于块内的点的 b,c 的大小关系,也就是哪些点的 b,c 是满足这个条件的,我们就可以离散化块内的 b,c,然后再用离散化后的数去代替原本实际的数进行二维前缀和即可,对于每一个块内部的元素直接暴力,我们定义块长为 B,单次重构的复杂度是一个 B^2+n,一共 \frac{n}{B} 次,暴力计算是 \frac{B^2}{2} 的,我们在块长 B=\sqrt n 的时候最优,整体复杂度是一个 O(n\sqrt n)。 ::::info[代码实现]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+5;
struct points{
    int a,b,c;
    int ARIS,KEI;
}a[N],b[N];
bool cmp(points x,points y){
    if(x.a==y.a){
        if(x.b==y.b){
            return x.c<y.c;
        } 
        return x.b<y.b;
    }
    return x.a<y.a;
}
int n,m,k,B,tot,d[N],c[N],L[N],R[N],s[505][505],tob[N],toc[N],x,y,f[N];
void refresh(int p){
    int w=0;
    tot=0;
    memset(s,0,sizeof(s));
    for(int i=L[p];i<=R[p];i++){
        tot++;
        d[tot]=a[i].b;
    }
    sort(d+1,d+1+tot);
    tot=unique(d+1,d+1+tot)-d-1;
    w=0;
    for(int i=1;i<=k;i++){
        if(i>d[w]&&w<=tot){
            w++;
        }
        tob[i]=w;
    }
    x=tot;
    tot=0;
    for(int i=L[p];i<=R[p];i++){
        tot++;
        d[tot]=a[i].c;
    }
    sort(d+1,d+1+tot);
    tot=unique(d+1,d+1+tot)-d-1;
    w=0;
    for(int i=1;i<=k;i++){
        if(i>d[w]&&w<=tot){
            w++;
        }
        toc[i]=w;
    }
    y=tot;
    for(int i=1;i<L[p];i++){
        s[tob[a[i].b]][toc[a[i].c]]+=a[i].KEI; 
    }
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            s[i][j]+=(s[i][j-1]+s[i-1][j]-s[i-1][j-1]);
        }
    }
} 
int main(){
    ios::sync_with_stdio(0);cin.tie(0); 
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>b[i].a>>b[i].b>>b[i].c;
    }
    sort(b+1,b+1+n,cmp);
    int tot=0,q=0;
    for(int i=1;i<=n;i++){
        q++;
        if(i==n||b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c){
            a[++tot]=b[i];
            a[tot].KEI=q;
            q=0;
        }
    }
    m=n;
    n=tot;
    B=sqrt(n);
    for(int i=1;i<=n;i++){
        c[i]=(i-1)/B+1;
    }
    for(int i=1;i<=B;i++){
        L[i]=(i-1)*B+1;
        R[i]=i*B;
    }
    if(R[B]!=n){
        B++;
        L[B]=R[B-1]+1;
        R[B]=n;
    }
    for(int p=1;p<=B;p++){
        refresh(p);
        for(int i=L[p];i<=R[p];i++){
            for(int j=L[p];j<i;j++){
                if(a[j].b<=a[i].b&&a[j].c<=a[i].c){
                    a[i].ARIS+=a[j].KEI;
                }
            }
            a[i].ARIS+=s[tob[a[i].b]][toc[a[i].c]];
        }
    }
    for(int i=1;i<=n;i++){
        f[a[i].ARIS+a[i].KEI-1]+=a[i].KEI;
    }
    for(int i=0;i<m;i++){
        cout<<f[i]<<'\n';
    }
    return 0;
}/*
再见了,王女 
*/

::::

树套树

我们还是那个思路,先按 a 排序,将问题变成 (b,c) 上的二维数点,我们写一个树套树,外层线段树每一个节点存满足 b\in[pl,pr] 的所有的c 的值,注意到我们直接用静态的 k^2 是绝对会飞起来的,我们考虑将内层的线段树变成一个动态开点线段树,如果常数巨大的话还可以进行其他的优化。

P10281 Grass Segments G

模拟赛题目,做的时候死亡了/fn

注意到我们对于 j 当其满足条件能够贡献 i 的时候,有 \min(r_i,r_j)-\max(l_i,l_j)\ge k_i 这个明显的我们可以将其每一种可能性都拆出来:

\begin{cases}r_i-l_i\ge k_i \\r_j-l_i\ge k_i\\ r_j-l_j\ge k_i \\ r_i-l_j \ge k_i\end{cases}

我们可以轻松注意到只有当四个东西都成立的时候上面的总的式子才成立,我们注意到 r_i-l_i\ge k_i 属于题目已知条件,我们可以直接,删去,然后进行简单移项:

\begin{cases}r_j\ge k_i+l_i\\ r_j-l_j\ge k_i \\ -l_j \ge k_i-r_i\end{cases} \begin{cases}-r_j\le -k_i-l_i\\ -r_j+l_j\le -k_i \\ l_j \le -k_i+r_i\end{cases}

然后我们直接三维数点,复杂度 O(n\log^2 n) 注意进行离散化,否则原本的坐标会有负数或者超出去,实现的有点难看,因为是模拟赛的时候打的。 ::::info[代码实现]

#include<bits/stdc++.h>
#define ll long long
#define lowbit x&-x
using namespace std;
const int N=1.6e6;
map<pair<int,int>,int> mp;
struct bits{
    int tr[N+50];
    void add(int x,int k){
        while(x<=N){
            tr[x]+=k;
            x+=lowbit;
        }
    }
    int query(int x){
        int res=0;
        while(x){
            res+=tr[x];
            x-=lowbit;
        }
        return res;
    }
}tr;
struct ops{
    int l,r,k;
}b[N];
struct node{
    int a,b,c,ans,cnt,id;
}a[N],q[N];
int n,ans[N];
bool cmp2nd(node x,node y){
    if(x.id==y.id){
        if(x.a==y.a){
            if(x.b==y.b){
                return x.c<y.c;
            }
            return x.b<y.b;
        }
        return x.a<y.a;
    }
    return x.id<y.id;
}
bool cmpp2nd(node x,node y){
    if(x.a==y.a){
        if(x.b==y.b){
            if(x.c==y.c){
                return x.id<y.id;
            }
            return x.c<y.c;
        }
        return x.b<y.b;
    }
    return x.a<y.a;
}
bool cmppp2nd(node x,node y){
    if(x.b==y.b){
        return x.c<y.c;
    }
    return x.b<y.b;
}
void CDQ(int pl,int pr){
    if(pl==pr){
        return ;
    }
    int mid=(pl+pr)>>1;
    CDQ(pl,mid);CDQ(mid+1,pr);
    sort(a+pl,a+mid+1,cmppp2nd);sort(a+mid+1,a+pr+1,cmppp2nd);
    int l=pl;
    for(int r=mid+1;r<=pr;r++){
        while(a[l].b<=a[r].b&&l<=mid){
            if(!a[l].id){
                tr.add(a[l].c,a[l].cnt); 
            } 
            l++;
        }
        if(a[r].id){
            ans[a[r].id]+=tr.query(a[r].c); 
        }
    }
    for(int i=pl;i<l;i++){
        if(!a[i].id){
            tr.add(a[i].c,-a[i].cnt);
        }
    }
}
int A[N],B[N],C[N];
int tota,totb,totc;
bool cmpa(node x,node y){
    return x.a<y.a;
}
bool cmpb(node x,node y){
    return x.b<y.b;
}
bool cmpc(node x,node y){
    return x.c<y.c;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>b[i].l>>b[i].r>>b[i].k;
        mp[{b[i].l,b[i].r}]++;
    }
    int tot,m,w,now;
    tot=tota=totb=totc=0;
    for(int i=1;i<=n;i++){
        q[++tot].a=b[i].l;
        q[tot].b=-b[i].r+N;
        q[tot].c=-(b[i].r-b[i].l)+N;
        q[tot].cnt=1;
        q[tot].id=0;
        A[++tota]=q[tot].a;B[++totb]=q[tot].b;C[++totc]=q[tot].c;
        q[++tot].a=b[i].r-b[i].k;
        q[tot].b=-b[i].l-b[i].k+N;
        q[tot].c=-b[i].k+N;
        q[tot].cnt=0;
        q[tot].id=i;
        A[++tota]=q[tot].a;B[++totb]=q[tot].b;C[++totc]=q[tot].c;
    }
    sort(A+1,A+1+tota);
    sort(B+1,B+1+totb);
    sort(C+1,C+1+totc);
    tota=unique(A+1,A+1+tota)-A-1;
    totb=unique(B+1,B+1+totb)-B-1;
    totc=unique(C+1,C+1+totc)-C-1;
    now=1;
    sort(q+1,q+1+tot,cmpa);
    for(int i=1;i<=tot;i++){
        while(q[i].a!=A[now]){
            now++;
        }
        q[i].a=now;
    }
    now=1;
    sort(q+1,q+1+tot,cmpb);
    for(int i=1;i<=tot;i++){
        while(q[i].b!=B[now]){
            now++;
        }
        q[i].b=now;
    }
    now=1;
    sort(q+1,q+1+tot,cmpc);
    for(int i=1;i<=tot;i++){
        while(q[i].c!=C[now]){
            now++;
        }
        q[i].c=now;
    }
    sort(q+1,q+1+tot,cmp2nd);
    w=m=0;
    for(int i=1;i<=tot;i++){
        if(q[i].id){
            a[++m]=q[i];
            continue;
        }
        if(q[i].a!=q[i+1].a||q[i].b!=q[i+1].b||q[i].c!=q[i+1].c||q[i].id!=q[i+1].id){
            a[++m]=q[i];
            a[m].cnt=i-w;
            w=i;
        }
    }
    sort(a+1,a+1+m,cmpp2nd);
    CDQ(1,m);
    for(int i=1;i<=n;i++){
        cout<<ans[i]-1<<'\n';
    }
    return 0;
}/*
再见了,王女 
*/

::::

补充思路

我们讨论一下,对于 i,可行的 j 的大致以下几种情况:

我们不难发现,情况 1 是与剩下三种情况无关的,我们直接算即可,对于情况 2,3 我们刻意地忽略了它们的另一个界的限制,只保证其分别控制的界和交的部分的大小,这样会出现问题,也就是 4 的情况同时被 2,3 给贡献到,我们容斥一下,答案就是 1+2+3-4。

对于 1,除了左右界以外存在无法消去的 len_j\ge k_i,使用三维偏序,对于 2,3,4 因为 2,3 我们只关心一个界和不用分讨的交大小,4 只有两个界,所以我们都可以写成二维偏序,最后就是一个三维偏序和三个二维偏序,注意对于界重的慎重处理。

容斥无疑是简单的,边界无疑是难办的。

P11197赛狗游戏

我们看到这个问题给的两个限制,我们假设有一个点对 (a,b),当 (a,b) 满足 2 的时候,(b,a) 也一定满足 2,而 (a,b)(b,a) 必然只有一个能满足 1,所以我们可以将 1 扔掉,问题变成一个纯粹的三维偏序计数问题。

我们可以直接写 CDQ,很明显 O(n\log^2 n) 有点不太可做,实际上是可做的,你需要卡常,但是我不想卡常,所以我就不讲卡常了。

我们提供一种 O(n\log n) 的做法,我们把问题变成二维偏序的时候我们是可以轻松求出的,我们考虑怎么容斥出来三维偏序,我们将满足二维偏序的对分成两种:

  1. 只满足二维偏序,也就是反着来只满足一维偏序。
  2. 满足三维偏序,也就是反着来不满足任何偏序。

那么我们的答案就是三种满足二维偏序的点对集合大小之和减去中间三个集合之交的大小再除去 2。我们可以整个图来方便理解:

对的,就是容斥最经典的那个图,我们将三个偏序分别关系满足的集合画出来,我们的答案是中间的 1\land2\land3,可以容斥成 (1\land2),(2\land3),(1\land3) 的大小和减去交集大小,再除以二,看一下图应该是能理解的。

根据我们上面的性质我们发现对于 (i,j),(j,i) 这两对肯定有且仅有一对包含在这个交集里,所以我们可以发现这个的大小直接就是 \frac{n(n-1)}{2},所以这个东西直接就是三个二维数点,然后再减去这个东西除以二就好了。 ::::info[代码实现]

#include<bits/stdc++.h>
#define lowbit x&(-x)
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,k,a[N],b[N],c[N],KEI[N],ARIS;
struct bits{
    ll tr[N];
    void add(ll x,ll k){
        while(x<=N){
            tr[x]+=k;
            x+=lowbit;
        }
    }
    ll query(ll x){
        ll ARIS=0;
        while(x){
            ARIS+=tr[x];
            x-=lowbit;
        }
        return ARIS;
    }
}tr1,tr2,tr3;
int main(){
    ios::sync_with_stdio(0);cin.tie(0); 
    cin>>n;
    for(ll i=1;i<=n;i++){
        ll x;
        cin>>x;
    }
    for(ll i=1;i<=n;i++){
        ll x;
        cin>>x;
        a[x]=i;
    }
    for(ll i=1;i<=n;i++){
        ll x;
        cin>>x;
        b[x]=i;
    }
    for(ll i=1;i<=n;i++){
        ll x;
        cin>>x;
        c[x]=i;
    }
    for(ll i=1;i<=n;i++){
        KEI[a[i]]=b[i];
    }
    for(ll i=1;i<=n;i++){
        ARIS+=tr1.query(KEI[i]);
        tr1.add(KEI[i],1);
    }
    for(ll i=1;i<=n;i++){
        KEI[c[i]]=b[i];
    }
    for(ll i=1;i<=n;i++){
        ARIS+=tr2.query(KEI[i]);
        tr2.add(KEI[i],1);
    }
    for(ll i=1;i<=n;i++){
        KEI[a[i]]=c[i];
    }
    for(ll i=1;i<=n;i++){
        ARIS+=tr3.query(KEI[i]);
        tr3.add(KEI[i],1);
    }
    cout<<(ARIS-(n-1)*n/2)/2;
    return 0;
}/*
再见了,王女 
*/

::::