紙箱堆疊 (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 }
