[BZOJ]2253: [2010 Beijing wc]纸箱堆叠

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}

ll p,a;
ll ycl[MAXN];
typedef struct node{
    ll x,y,z;int id,pos;
    friend bool operator<(node aa,node bb){return aa.x<bb.x;}
}node;
node d[MAXN],ed[MAXN];int tot;
vector<int>vec;
int base,ans[MAXN];

int maxx[MAXN<<2];

void built(int rt,int l,int r,int t){
    maxx[rt]=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(t<=mid)built(rt<<1,l,mid,t);
    else built(rt<<1|1,mid+1,r,t);
}

void update(int rt,int l,int r,int t,int k){
    maxx[rt]=max(maxx[rt],k);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(t<=mid)update(rt<<1,l,mid,t,k);
    else update(rt<<1|1,mid+1,r,t,k);
}

int ans1;
void query(int rt,int l,int r,int ql,int qr){
    if(ql>qr)return ;
    if(ql<=l&&r<=qr){ans1=max(ans1,maxx[rt]);return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(rt<<1,l,mid,ql,qr);
    if(qr>mid)query(rt<<1|1,mid+1,r,ql,qr);
}

bool cmp1(node aa,node bb){return aa.y<bb.y;}
bool cmp2(node aa,node bb){return aa.pos<bb.pos;}

void merge(int l,int mid,int r){
    int i=l;int j=mid+1;
    for(int k=mid+1;k<=r;k++)d[k].pos=k;
    sort(d+mid+1,d+r+1,cmp1);
    tot=0;
    while(i<=mid&&j<=r){
	while(i<=mid&&d[i].y<d[j].y){
	    update(1,1,base,d[i].z,ans[d[i].id]);
	    i++;
	}
	ans1=0;query(1,1,base,1,d[j].z-1);ans[d[j].id]=max(ans[d[j].id],ans1+1);
	j++;
    }
    for(;j<=r;j++){
	ans1=0;query(1,1,base,1,d[j].z-1);ans[d[j].id]=max(ans[d[j].id],ans1+1);
    }
    for(int i=l;i<=mid;i++)built(1,1,base,d[i].z);
    sort(d+mid+1,d+r+1,cmp2);
}

void cdq(int l,int r){
    if(l>=r)return ;
    int mid=(l+r)>>1;
    cdq(l,mid);
    merge(l,mid,r);
    cdq(mid+1,r);
    merge(l,mid,r);
    sort(d+l,d+r+1,cmp1);
}

int main(){
    a=read();p=read();int n=read();
    ycl[0]=1;
    inc(i,1,3*n)ycl[i]=ycl[i-1]*a%p;
    inc(i,1,n)ans[i]=1;
    inc(i,1,n){
	d[i].id=i;
	d[i].x=ycl[3*i-2],d[i].y=ycl[3*i-1],d[i].z=ycl[3*i];
	if(d[i].x>d[i].z)swap(d[i].x,d[i].z);
	if(d[i].y>d[i].z)swap(d[i].y,d[i].z);
	if(d[i].x>d[i].y)swap(d[i].x,d[i].y);
	vec.pb(d[i].z);vec.pb(d[i].z-1);
    }
    sort(vec.begin(),vec.end());
    base=unique(vec.begin(),vec.end())-vec.begin();
    inc(i,1,n)d[i].z=lower_bound(vec.begin(),vec.begin()+base,d[i].z)-vec.begin()+1;
    sort(d+1,d+n+1);
    cdq(1,n);
    int ans2=0;
    inc(i,1,n)ans2=max(ans2,ans[i]);
    printf("%d\n",ans2);
}