纸箱堆叠

Time Limit: 30 Sec Memory Limit: 256 MB

Description

P 工厂是一个生产纸箱的工厂。
　　纸箱生产线在人工输入三个参数 n p a , 之后即可自动化生产三边边长为

(a mod P,a^2 mod p,a^3 mod P)
　　(a^4 mod p,a^5 mod p,a^6 mod P)
　　…
　　(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p)

的n个纸箱。
　　在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。
　　一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。
　　你的任务是找出这n个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。

Input

输入文件的第一行三个整数，分别代表 a,p,n

Output

输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。

Sample Input

10 17 4

Sample Output

2
【样例说明】
　生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。

其中只有(4, 6, 9)可堆叠进(5, 16, 7)，故答案为 2。

HINT

2<=P<=2000000000, 1<=a<=p-1, a^k mod p<>0, ap<=2000000000, 1<=N<=50000

Main idea

每一个元素有三个属性a,b,c，求出最大可连续堆叠个数（可堆叠条件是a1<a2,b1<b2,c1<c2）

Solution

题目显然是三维偏序问题，运用CDQ分治求解。

用排序处理a保证a有序，分治的时候满足左区间的b都小于右区间的b，再处理c，这样问题就转化为了求一个点在一个平面上横纵坐标都小于它的点有几个，用树状数组处理即可。

发现这样处理之后答案只能满足<=该点，考虑如何令答案严格小于。

首先b，c的严格小于处理显然，因为a是sort保证的那么如何要使得a的统计严格小于呢？只需要在b的sort前将分割的指针向左移动到第一个不等于的即可，结合分治考虑一下while(q[mid].a==q[mid-1].a) mid–，发现这样处理最后会影响到排序，所以做右区间的时候重新按照a排序一下即可。

考虑如何统计答案，发现显然有： q[j].ans=max(q[j].ans,Query(q[j].c-1)+1)。

Code

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;

const int ONE=1000001;

int n,MOD,a,m;
int PD[4];
int res;
int C[ONE];
int Ans,cnt;

struct power
{
    int a,b,c;
    int ans;
}q[ONE];

struct point
{
    int pos,value;
}Lisa[ONE];

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int cmp(const power &a,const power &b)
{
    if(a.a!=b.a) return a.a<b.a;
    if(a.b!=b.b) return a.b<b.b;
    return a.c<b.c;
}

int cdp(const power &a,const power &b)
{
    if(a.b!=b.b) return a.b<b.b;
    return a.c<b.c;
}

int rule(const power &a,const power &b)
{
    return (a.a==b.a && a.b==b.b && a.c==b.c);
}

int lowbit(int x)
{
    return x&-x;
}

int Add(int R,int x)
{
    for(int i=R;i<=cnt;i+=lowbit(i))
        C[i]=max(C[i],x);
}

int Query(int R)
{
    res=0;
    for(int i=R;i>=1;i-=lowbit(i))
        res=max(res,C[i]);
    return res;
}

int Clear(int R)
{
    for(int i=R;i<=cnt;i+=lowbit(i))
        C[i]=0;
}

int clis(const point &a,const point &b)
{
    return a.value<b.value;
}

void GetLisan()
{
    sort(q+1,q+n+1,cmp);
    n=unique(q+1,q+n+1,rule)-1-q;

    for(int i=1;i<=n;i++)
    {
        Lisa[i].pos=i;
        Lisa[i].value=q[i].c;
    }
    sort(Lisa+1,Lisa+n+1,clis);

    cnt=0;
    Lisa[0].value=-1;
    for(int i=1;i<=n;i++)
    {
        if(Lisa[i].value!=Lisa[i-1].value) cnt++;
        q[Lisa[i].pos].c=cnt;
    }

}

void Deal(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)/2;
    while(q[mid].a==q[mid-1].a) mid--;
    if(mid<l) return;
    Deal(l,mid);
    sort(q+l,q+mid+1,cdp);  sort(q+mid+1,q+r+1,cdp);

    int i=l,j=mid+1;
    while(j<=r)
    {
        while(i<=mid && q[i].b<q[j].b)
        {
            Add(q[i].c,q[i].ans);
            i++;
        }

        q[j].ans=max(q[j].ans,Query(q[j].c-1)+1);
        j++;
    }


    for(int T=l;T<=mid;T++)
    {
        Clear(q[T].c);
    }
    sort(q+mid+1,q+r+1,cmp);
    Deal(mid+1,r);
}

int main()
{
    a=get();    MOD=get();  n=get();
    int j=0;    res=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)
        {
            res=(long long)res*a%MOD;
            PD[j]=res;
        }
        sort(PD+1,PD+3+1);
        q[i].a=PD[1]; q[i].b=PD[2]; q[i].c=PD[3];
        q[i].ans=1;
    }

    GetLisan();

    Deal(1,n);
    for(int i=1;i<=n;i++)
        Ans=max(Ans,q[i].ans);

    printf("%d",Ans);
}