纸箱堆叠 bzoj 2253
纸箱堆叠 (1s 128MB) box
【问题描述】
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
题解：
主要算法：CDQ分治（快速排序，树状数组）；动态规划（Dp）；
我们设长宽高为x，y，z
CDQ分治，以x为关键词排序
接下来递归分成两区间
假设左区间已经处理完了答案
将左右区间分别以y为关键字排序
那么就保证了任何左区间的x必定小于任何右区间的x
我们用两个指针分别从左右区间顺序向后扫
将左区间的z作为位置不断加入树状数组，值为当前点的答案
由于左右区间有序，可以手动保证右区间的扫到的点的y大于所有左区间扫到的点的y
就可以用树状数组更新右区间点的值：当前点的答案等于能转移到当前点的点的答案加一的最大值，这里用上了Dp的思想
然后清空树状数组，再将左右区间合并按第一维排序，恢复原状态， 保证处理的是最初的右区间，且此区间按第一维有序
接着递归处理右区间，继续更新答案
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #include<cmath>
7 using namespace std;
8 inline int Get()
9 {
10 int x = 0;
11 char c = getchar();
12 while('0' > c || c > '9') c = getchar();
13 while('0' <= c && c <= '9')
14 {
15 x = (x << 3) + (x << 1) + c - '0';
16 c = getchar();
17 }
18 return x;
19 }
20 const int me = 100233;
21 struct box
22 {
23 int x, y, z, ans;
24 };
25 box c[me], s[me];
26 int a, p, n, m;
27 int tr[me];
28 int num[me];
29 inline bool rulex(box a, box b)
30 {
31 if(a.x != b.x) return a.x < b.x;
32 if(a.y != b.y) return a.y < b.y;
33 return a.z < b.z;
34 }
35 inline bool rules(int a, int b)
36 {
37 if(s[a].z != s[b].z) return s[a].z < s[b].z;
38 if(s[a].x != s[b].x) return s[a].x < s[b].x;
39 return s[a].y < s[b].y;
40 }
41 inline bool ruley(box a, box b)
42 {
43 if(a.y != b.y) return a.y < b.y;
44 return a.z < b.z;
45 }
46 inline int Max(int x)
47 {
48 int maxx = 0;
49 while(x > 0)
50 {
51 maxx = max(tr[x], maxx);
52 x -= x & (-x);
53 }
54 return maxx;
55 }
56 inline void Ins(int x, int y)
57 {
58 while(x <= m)
59 {
60 tr[x] = max(tr[x], y);
61 x += x & (-x);
62 }
63 }
64 inline void Del(int x)
65 {
66 while(x <= m)
67 {
68 tr[x] = 0;
69 x += x & (-x);
70 }
71 }
72 inline int Maxx(int x, int y)
73 {
74 return (x > y) ? x : y;
75 }
76 void Work(int l, int r)
77 {
78 if(l == r) return;
79 int mi = l + r >> 1;
80 while(s[mi].x == s[mi - 1].x) --mi;
81 if(mi < l) return;
82 Work(l, mi);
83 sort(s + l, s + mi + 1, ruley);
84 sort(s + mi + 1, s + r + 1, ruley);
85 int u = l, v = mi + 1;
86 while(u <= mi && v <= r)
87 {
88 if(s[u].y < s[v].y)
89 {
90 Ins(s[u].z, s[u].ans);
91 ++u;
92 }
93 else
94 {
95 s[v].ans = Maxx(s[v].ans, Max(s[v].z - 1) + 1);
96 ++v;
97 }
98 }
99 for(int i = v; i <= r; ++i)
100 s[i].ans = Maxx(s[i].ans, Max(s[i].z - 1) + 1);
101 for(int i = l; i <= mi; ++i) Del(s[i].z);
102 sort(s + mi + 1, s + r + 1, rulex);
103 Work(mi + 1, r);
104 }
105 int cc[4];
106 int main()
107 {
108 a = Get(), p = Get(), n = Get();
109 cc[0] = 1;
110 for(int i = 1; i <= n; ++i)
111 {
112 cc[1] = cc[0] * a % p;
113 cc[2] = cc[1] * a % p;
114 cc[3] = cc[2] * a % p;
115 cc[0] = cc[3];
116 sort(cc + 1, cc + 4);
117 c[i].x = cc[1], c[i].y = cc[2], c[i].z = cc[3];
118 c[i].ans = 1;
119 }
120 sort(c + 1, c + 1 + n, rulex);
121 for(int i = 1; i <= n; ++i)
122 {
123 if(c[i].x != c[i - 1].x || c[i].y != c[i - 1].y || c[i].z != c[i - 1].z)
124 {
125 s[++m] = c[i];
126 num[m] = m;
127 }
128 }
129 sort(num + 1, num + 1 + m, rules);
130 int k = 0;
131 for(int i = 1; i <= m; ++i)
132 {
133 k = i;
134 while(s[num[i]].z == s[num[i + 1]].z)
135 {
136 s[num[i]].z = k;
137 ++i;
138 }
139 s[num[i]].z = k;
140 }
141 Work(1, m);
142 int ans = 0;
143 for(int i = 1; i <= m; ++i)
144 if(s[i].ans > ans)
145 ans = s[i].ans;
146 printf("%d", ans);
147 }