# 纸箱堆叠 bzoj 2253

2017-01-04 12:08:21来源:cnblogs.com作者:LoseYourTemper人点击

【问题描述】

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)

【输入格式】

【输出格式】

【样例输入】

10 17 4

【样例输出】

2

【样例说明】

【样例说明】

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

CDQ分治，以x为关键词排序

`  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 }`