题解：
其实就是求三维偏序最长链。类似于三维逆序对，我们可以用树状数组套平衡树来实现。
DP方程 ：f[i]=max(f[j]+1) a[j]<a[i]
我们按一维排序，另一位建立树状数组，把第三维插入到每个树状数组的节点里。
除了权值之外每个节点还要保持一个mx，表示该子树内最大的f[i]。
这样就可以nlg^n了
UPD:试了下不带旋转的treap果然会被卡 orz
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 150000+5
#define maxm 4000000+5
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
#define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
#define mod 1000000007
using namespace std;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,tot,cnt,b[maxn],f[maxn],rt[maxn],c[maxn],d[maxn];
int h[maxm],mx[maxm],l[maxm],r[maxm],v[maxm],vv[maxm];
struct rec{int x,y,z;}a[maxn];
bool operator <(rec a,rec b){return a.x<b.x;}
inline void pushup(int k)
{
mx[k]=max(vv[k],max(mx[l[k]],mx[r[k]]));
}
inline void lturn(int &k)
{
int t=r[k];r[k]=l[t];l[t]=k;pushup(k);pushup(t);k=t;
}
inline void rturn(int &k)
{
int t=l[k];l[k]=r[t];r[t]=k;pushup(k);pushup(t);k=t;
}
inline void insert(int &k,int x,int y)
{
if(!k)
{
k=++tot;v[k]=x;h[k]=rand();vv[k]=mx[k]=y;
return;
}
if(x==v[k])vv[k]=max(vv[k],y);
else if(x<v[k]){insert(l[k],x,y);if(h[k]<h[l[k]])rturn(k);}
else {insert(r[k],x,y);if(h[k]<h[r[k]])lturn(k);}
pushup(k);
}
inline int getmx(int k,int x)
{
if(!k)return ;
if(v[k]==x)return max(mx[l[k]],vv[k]);
else if(x<v[k])return getmx(l[k],x);
else return max(max(mx[l[k]],vv[k]),getmx(r[k],x));
}
inline int query(int x,int y)
{
int ret=;
for(;x;x-=x&(-x)){ret=max(ret,getmx(rt[x],y));}
return ret;
}
inline void add(int x,int y,int z)
{
for(;x<=cnt;x+=x&(-x))insert(rt[x],y,z);
}
inline bool cmp(int x,int y){return b[x]<b[y];}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ll t=read(),p=read();n=read();b[]=;
for1(i,*n)b[i]=(ll)b[i-]*t%p,c[i]=i;
sort(c+,c+*n+,cmp);
cnt=;
for1(i,*n)
{
if(i==||b[c[i]]!=b[c[i-]])cnt++;
d[c[i]]=cnt;
}
for1(i,n)a[i].x=d[*i-],a[i].y=d[*i-],a[i].z=d[*i];
for1(i,n)
{
if(a[i].y>a[i].x)swap(a[i].x,a[i].y);
if(a[i].z>a[i].x)swap(a[i].x,a[i].z);
if(a[i].z>a[i].y)swap(a[i].z,a[i].y);
}
sort(a+,a+n+);
for(int l=,r=;l<=n;r++,l=r)
{
while(a[r+].x==a[l].x)r++;
for2(i,l,r)f[i]=query(a[i].y-,a[i].z-)+;//cout<<i<<' '<<f[i]<<endl;
for2(i,l,r)add(a[i].y,a[i].z,f[i]);
}
int ans=;
for1(i,n)ans=max(ans,f[i]);
cout<<ans<<endl;
return ;
} 2253: [2010 Beijing wc]纸箱堆叠
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 246 Solved: 96
[Submit][Status]
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。
2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000
【样例说明】
生产出的纸箱的三边长为(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