高维偏序问题

最近做了几道高维偏序的简单题。

对于这类题目一般有三种通用方法，一是cdq分治，维数越多嵌套次数就越多，总体来说思路就是对时间分治，每次统计出左半区间的贡献点对右半区间的询问点的贡献，这样对于每个询问点来说，它前面的所有对它造成影响的点就都会被算到。二是用bitset优化暴力，应该只能处理计数问题，但优点是好写，适合做高维偏序。三是KDtree，emmmm，这个没怎么写过，多校训练十分艰难的写过一次，通过了90%的数据然后TLE了。

1.LOJ#112 三维偏序

计数题，对其中一维排序后，cdq分治套树状数组，时间复杂度O(nlog2n)O(nlog^{2}n)。

2.[COGS 2479HZOI 2016] 偏序

计数题，四维偏序，cdq分治套cdq分治套树状数组，时间复杂度O(nlog3n)O(nlog^{3}n)。

怎么理解这个分治套分治呢。假设属性为a,b,c，第一次分治的时候我们将区间[l,mid]的点标记成贡献点，[mid+1,r]的点标记成询问点，然后区间[l,r]按a属性排序，消去a的影响，这样问题就变成了有n次操作，每次要么插入一个点(b,c)，要么查询之前插入的点中有多少点在(b,c)左下方，这样问题就降了一维化成了三维偏序了。

3.[COGS 2580 HZOI 2015]偏序 II

计数题，五维偏序，在上一题的基础上外面再套一次cdq分治，时间复杂度十分感人O(nlog4n)O(nlog^{4}n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
struct node
{
    int w,x,y,z;
    bool t,s;
} a[N],b[N],c[N],d[N];
int n;
ll ans;
struct BIT
{
    int c[N];
    void add(int x,int y)
    {
        for(; x<=n; x+=x&(-x)) c[x]+=y;
    }
    int ask(int x)
    {
        int ans=0;
        for(; x; x-=x&(-x)) ans+=c[x];
        return ans;
    }
} bit;
void cdq3(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq3(l,mid);
    cdq3(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        if(c[i].y<c[j].y)
        {
            if(!c[i].s && !c[i].t) bit.add(c[i].z,1);
            d[k++]=c[i++];
        }
        else
        {
            if(c[j].s && c[j].t) ans+=bit.ask(c[j].z);
            d[k++]=c[j++];
        }
    }
    while(i<=mid)
    {
        if(!c[i].s && !c[i].t) bit.add(c[i].z,1);
        d[k++]=c[i++];
    }
    while(j<=r)
    {
        if(c[j].s && c[j].t) ans+=bit.ask(c[j].z);
        d[k++]=c[j++];
    }
    for(int i=l; i<=mid; ++i) if(!c[i].s && !c[i].t) bit.add(c[i].z,-1);
    for(int i=l; i<=r; ++i) c[i]=d[i];
}
void cdq2(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq2(l,mid);
    cdq2(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        if(b[i].x<b[j].x) c[k]=b[i++],c[k++].s=false;
        else c[k]=b[j++],c[k++].s=true;
    }
    while(i<=mid) c[k]=b[i++],c[k++].s=false;
    while(j<=r) c[k]=b[j++],c[k++].s=true;
    for(int i=l; i<=r; ++i) b[i]=c[i];
    cdq3(l,r);
}
void cdq1(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq1(l,mid);
    cdq1(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        if(a[i].w<a[j].w) b[k]=a[i++],b[k++].t=false;
        else b[k]=a[j++],b[k++].t=true;
    }
    while(i<=mid) b[k]=a[i++],b[k++].t=false;
    while(j<=r) b[k]=a[j++],b[k++].t=true;
    for(int i=l; i<=r; ++i) a[i]=b[i];
    cdq2(l,r);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1; i<=n; i++)scanf("%d",&a[i].w);
        for(int i=1; i<=n; i++)scanf("%d",&a[i].x);
        for(int i=1; i<=n; i++)scanf("%d",&a[i].y);
        for(int i=1; i<=n; i++)scanf("%d",&a[i].z);
        ans=0;
        cdq1(1,n);
        printf("%lld\n",ans);
    }
}

4.[COGS 2639. HZOI 2015] 偏序++

计数题，七维偏序。只能bitset了，每个元素开一个bitset表示哪些点比它小，一维一维的考虑，从小到大枚举值，然后对每个元素and一下就行了。时间复杂度O(kn2/64)O(kn^2/64)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=40005;
bitset<N> bs[N],tmp;
int n,k,ans;
int pos[N],a[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) bs[i]=bs[i-1],bs[i][i-1]=1;
    while(k--)
    {
        for(int i=1;i<=n;++i) scanf("%d",a+i),pos[a[i]]=i;
        tmp.reset();
        for(int i=1;i<=n;++i) bs[pos[i]]&=tmp,tmp[pos[i]]=1;
    }
    ll ans=0;
    for(int i=1;i<=n;++i) ans+=bs[i].count();
    printf("%lld\n",ans);
}

5.SPOJ LIS2 Another Longest Increasing Subsequence Problem

求最优解，即最长上升子序列的长度，每个元素有两个属性。回忆一下一个属性的话，我们可以用树状数组求前缀最大值的方法优化dp的转移，再加一维就用cdq分治套一下就行了。

与之前计数题不同的地方在于，计数题中贡献对询问的影响是独立的，没有先后顺序的问题，但是做这个dp的过程就必须是从前往后了，比如说序列1,2,3,4，如果用3去更新4的话，3的dp值就必须在之前就已经算出来是3。稍微改一下分治的顺序就可以了，先递归到[l,mid]，然后用左半区间更新右半区间的dp值，然后递归到右半区间。

6.2018 牛客网暑期ACM多校训练营（第九场）Longest Common Subsequence

求四个序列的最长公共子序列，保证值范围1-n，前三个序列中每一种值出现次数不超过2次。

先考虑四个序列都是排列的情况，假设对于值x来说pa[x],pb[x],pc[x],pd[x]在四个序列中的位置，那么最长公共子序列就转化成了求四维偏序的最长链。对于这个题目我们可以2的3次方枚举每个值的位置三元组，这样总点数就是8n的，还是求四维偏序的最长链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=80005;
int n;
int dp[N],vis[N];
int pos[N][3][2];
struct node
{
    int x,y,z,t,o;
    void show()
    {
        printf("%d:(%d,%d,%d)  %d\n",o,x,y,z,dp[o]);
    }
} a[N],b[N],c[N];


bool cmpx(const node &a,const node &b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y>b.y;
}
bool cmpy(const node &a,const node &b)
{
    if(a.y!=b.y) return a.y<b.y;
    return a.z>b.z;
}
struct BIT
{
    int c[N];
    void change(int x,int y)
    {
        for(; x<=n; x+=x&(-x)) c[x]=max(c[x],y);
    }
    void clear(int x)
    {
        for(; x<=n; x+=x&(-x)) c[x]=0;
    }
    int ask(int x)
    {
        int ans=0;
        for(; x; x-=x&(-x)) ans=max(ans,c[x]);
        return ans;
    }
} bit;
void cdq2(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq2(l,mid);

    for(int i=l; i<=r; ++i) c[i]=b[i];
    sort(c+l,c+mid+1,cmpy);
    sort(c+mid+1,c+r+1,cmpy);
    int i=l,j=mid+1;
    for(; j<=r; ++j)
    {
        for(; i<=mid && c[i].y<c[j].y; ++i)
        if(c[i].t==0)
            bit.change(c[i].z,dp[c[i].o]);
        if(c[j].t==1)
            dp[c[j].o]=max(dp[c[j].o],bit.ask(c[j].z-1)+1);
    }
    for(i=l; i<=mid; ++i)
        if(c[i].t==0) bit.clear(c[i].z);

    cdq2(mid+1,r);
}
void cdq1(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq1(l,mid);

    for(int i=l; i<=r; ++i) b[i]=a[i],b[i].t=(i>mid);
    sort(b+l,b+r+1,cmpx);
    cdq2(l,r);

    cdq1(mid+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<3; ++i)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1; j<=n; ++j)
        {
            int x;
            scanf("%d",&x);
            if(!vis[x]) pos[x][i][0]=pos[x][i][1]=j,vis[x]=1;
            else pos[x][i][1]=j;
        }
    }
    int cnt=0;
    for(int i=1; i<=n; ++i)
    {
        int x;
        scanf("%d",&x);
        if(!pos[x][0][0]||!pos[x][1][0]||!pos[x][2][0]) continue;
        for(int j=7; j>=0; --j)
        {
            ++cnt;
            a[cnt].o=cnt;
            a[cnt].x=pos[x][0][j&1];
            a[cnt].y=pos[x][1][j>>1&1];
            a[cnt].z=pos[x][2][j>>2&1];
            a[cnt].t=0;
            //a[cnt].show(cnt);
            dp[cnt]=1;
        }
    }

    cdq1(1,cnt);
    int ans=0;
    for(int i=1; i<=cnt; ++i)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}
/*
(1,1,2)
(2,2,3)
(3,4,4)
(4,5,5)
*/
算法学习
#偏序
高维偏序问题
https://izard.space/2018/08/30/高维偏序问题/
作者
forever_you
发布于
2018年8月30日
许可协议