纸箱堆叠
【问题描述】
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个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。
【输入格式】
输入文件的第一行三个整数，分别代表 a, p, n
【输出格式】
输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。
【样例输入】
10 17 4
【样例输出】
2
【样例说明】
生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有(4, 6, 9)可堆叠进(5, 16, 7)，故答案为 2。
【样例说明】
2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000
题解：
我们设长宽高为x，y，z
CDQ分治，以x为关键词排序
接下来递归分成两区间
假设左区间已经处理完了答案
将左右区间分别以y为关键字排序
那么就保证了任何左区间的x必定小于任何右区间的x
我们用两个指针分别从左右区间顺序向后扫
将左区间的z作为位置不断加入树状数组，值为当前点的答案
由于左右区间有序，可以手动保证右区间的扫到的点的y大于所有左区间扫到的点的y
就可以用树状数组更新右区间点的值：当前点的答案等于能转移到当前点的点的答案加一的最大值，这里用上了Dp的思想
然后清空树状数组，再将左右区间合并按第一维排序，恢复原状态， 保证处理的是最初的右区间，且此区间按第一维有序
接着递归处理右区间，继续更新答案
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = ;
char c = getchar();
while('' > c || c > '') c = getchar();
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x;
}
const int me = ;
struct box
{
int x, y, z, ans;
};
box c[me], s[me];
int a, p, n, m;
int tr[me];
int num[me];
inline bool rulex(box a, box b)
{
if(a.x != b.x) return a.x < b.x;
if(a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
inline bool rules(int a, int b)
{
if(s[a].z != s[b].z) return s[a].z < s[b].z;
if(s[a].x != s[b].x) return s[a].x < s[b].x;
return s[a].y < s[b].y;
}
inline bool ruley(box a, box b)
{
if(a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
inline int Max(int x)
{
int maxx = ;
while(x > )
{
maxx = max(tr[x], maxx);
x -= x & (-x);
}
return maxx;
}
inline void Ins(int x, int y)
{
while(x <= m)
{
tr[x] = max(tr[x], y);
x += x & (-x);
}
}
inline void Del(int x)
{
while(x <= m)
{
tr[x] = ;
x += x & (-x);
}
}
inline int Maxx(int x, int y)
{
return (x > y) ? x : y;
}
void Work(int l, int r)
{
if(l == r) return;
int mi = l + r >> ;
while(s[mi].x == s[mi - ].x) --mi;
if(mi < l) return;
Work(l, mi);
sort(s + l, s + mi + , ruley);
sort(s + mi + , s + r + , ruley);
int u = l, v = mi + ;
while(u <= mi && v <= r)
{
if(s[u].y < s[v].y)
{
Ins(s[u].z, s[u].ans);
++u;
}
else
{
s[v].ans = Maxx(s[v].ans, Max(s[v].z - ) + );
++v;
}
}
for(int i = v; i <= r; ++i)
s[i].ans = Maxx(s[i].ans, Max(s[i].z - ) + );
for(int i = l; i <= mi; ++i) Del(s[i].z);
sort(s + mi + , s + r + , rulex);
Work(mi + , r);
}
int cc[];
int main()
{
a = Get(), p = Get(), n = Get();
cc[] = ;
for(int i = ; i <= n; ++i)
{
cc[] = cc[] * a % p;
cc[] = cc[] * a % p;
cc[] = cc[] * a % p;
cc[] = cc[];
sort(cc + , cc + );
c[i].x = cc[], c[i].y = cc[], c[i].z = cc[];
c[i].ans = ;
}
sort(c + , c + + n, rulex);
for(int i = ; i <= n; ++i)
{
if(c[i].x != c[i - ].x || c[i].y != c[i - ].y || c[i].z != c[i - ].z)
{
s[++m] = c[i];
num[m] = m;
}
}
sort(num + , num + + m, rules);
int k = ;
for(int i = ; i <= m; ++i)
{
k = i;
while(s[num[i]].z == s[num[i + ]].z)
{
s[num[i]].z = k;
++i;
}
s[num[i]].z = k;
}
Work(, m);
int ans = ;
for(int i = ; i <= m; ++i)
if(s[i].ans > ans)
ans = s[i].ans;
printf("%d", ans);
}
