[文章目录]
Description
求最长三维严格LIS的长度，即对于答案有a[i] < a[i+1],b[i] < b[i+1],c[i] < c[i+1]。个数<=50000 a,b,c<=2 * 10^9
改变一下CDQ分治的方式：
对于第一维，由于CDQ的复杂度第一维是只跟分治层数有关的，所以我们可以按照a的种类分治，相同的a看做一组进行分治，保证右区间可以接到左区间元素后面。
对于第二维，归并排序的时候将条件改为b[l] <= b[r]-1 即b[l] < b[r]。转化为<=
对于第三维，直接在树状数组中查询c[i]-1即可。
时间复杂度O(nlog^2n)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,f[51000],lim;
struct node
{
int a,b,c,dp;
node(){a=b=c=0; dp=1;}
}a[51000];
bool cmpa(node x,node y){return x.a<y.a;}
bool cmpb(node x,node y){return x.b<y.b;}
bool cmpc(node x,node y){return x.c<y.c;}
inline int Max(int x,int y){return x>y ? x:y;}
inline void fix(int x,int y) {while(x<=lim) f[x]=Max(f[x],y),x+=-x&x;}
inline void clear(int x){while(x<=lim) f[x]=0,x+=-x&x;}
inline int query(int x){int re=0; while(x>0) re=Max(re,f[x]),x-=-x&x; return re;}
void solve(int l,int r)
{
if(a[l].a==a[r].a) return;
int mid=(a[l].a+a[r].a)>>1;
for(int i=l;i<=r;++i) if(a[i].a>mid) {mid=i-1; break;}
solve(l,mid); sort(a+mid+1,a+r+1,cmpb);
int t1=l,t2=mid+1;
for(int i=l;i<=r;++i)
{
if(t2>r||(t1<=mid&&a[t1].b<a[t2].b)) fix(a[t1].c,a[t1].dp),t1++;
else a[t2].dp=Max(a[t2].dp,query(a[t2].c-1)+1),t2++;
}
for(int i=l;i<=mid;++i) clear(a[i].c);
sort(a+mid+1,a+r+1,cmpa); solve(mid+1,r); sort(a+l,a+r+1,cmpb);
}
int main()
{
ll now=1,w,p;
scanf("%lld%lld%d",&w,&p,&n);
for(int i=1;i<=n;++i)
{
now=now*w%p; a[i].a=now;
now=now*w%p; a[i].b=now;
now=now*w%p; a[i].c=now;
if(a[i].b>a[i].c) swap(a[i].b,a[i].c);
if(a[i].a>a[i].b) swap(a[i].a,a[i].b);
if(a[i].b>a[i].c) swap(a[i].b,a[i].c);
}
sort(a+1,a+n+1,cmpb);
now=a[1].b; a[1].b=1; w=1;
for(int i=2;i<=n;++i)
(a[i].b==now) ? a[i].b=w : (now=a[i].b,a[i].b=++w);//问号表达式和逗号表达式一定要加括号。
sort(a+1,a+n+1,cmpc);
now=a[1].c; a[1].c=1; w=1;
for(int i=2;i<=n;++i)
(a[i].c==now) ? a[i].c=w : (now=a[i].c,a[i].c=++w);
lim=w;
sort(a+1,a+n+1,cmpa);
now=a[1].a; a[1].a=1; w=1;
for(int i=2;i<=n;++i)
(a[i].a==now) ? a[i].a=w : (now=a[i].a,a[i].a=++w);
solve(1,n);
int ans=0; for(int i=1;i<=n;++i) ans=Max(ans,a[i].dp);
printf("%d",ans);
return 0;
}