CDQ分治TLE10分求助

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+10,M=505,A=5005,inf=A+M;
struct segmenttree{
	int root,pcnt;
	struct node{
		int mx,ls,rs;
	}t[inf<<2];
	int new_node(){
		int p=++pcnt;t[p].ls=t[p].rs=t[p].mx=0;
		return p;
	}
	void clear(){
		root=pcnt=0;
	}
	void push_up(int p){
		if(!t[p].ls)t[p].ls=new_node();
		if(!t[p].rs)t[p].rs=new_node();
		t[p].mx=max(t[t[p].ls].mx,t[t[p].rs].mx);
	}
	void modify(int l,int r,int x,int d,int &p){
		if(!p)p=new_node();
		if(l==r){t[p].mx=max(t[p].mx,d);return ;}
		int mid=l+r>>1;
		if(mid>=x)modify(l,mid,x,d,t[p].ls);
		else modify(mid+1,r,x,d,t[p].rs);
		push_up(p);
	}
	int query(int l,int r,int L,int R,int p){
		if(!p)return 0;
		if(l>=L&&r<=R)return t[p].mx;
		int mid=l+r>>1,ret=0;
		if(mid>=L)ret=max(ret,query(l,mid,L,R,t[p].ls));
		if(mid<R)ret=max(ret,query(mid+1,r,L,R,t[p].rs));
		return ret;
	}
}s;
int n,m;
int cnt;
struct node{
	int x,y,z,f,id;
	/*
	转移要求：
	a.x<b.x
	a.y<=b.y
	a.z<=b.z
	*/
}a[N*M];
bool cmpid(node a,node b){
	return a.id<b.id;
}
bool cmpy(node a,node b){
	return (a.y==b.y)?(a.id<b.id):(a.y<b.y);
}
void solve(int l,int r){
	if(l>=r||a[l].x==a[r].x)return ;
	int mi=a[l+r>>1].x;
	int mid;
	for(int i=l;i<=r;i++)if(a[i].x<=mi)mid=i;
	solve(l,mid);
	sort(a+l,a+r+1,cmpy);
	s.clear();
	for(int i=l;i<=r;i++){
		if(a[i].id<=mid){
			s.modify(0,inf,a[i].z,a[i].f,s.root);
		}
		else{
			a[i].f=max(a[i].f,s.query(0,inf,0,a[i].z,s.root)+1);
		}
	}
	sort(a+l,a+r+1,cmpid);
	solve(mid+1,r);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int A;cin>>A;
		for(int j=0;j<=m;j++){
			cnt++;
			a[cnt].x=i;
			a[cnt].y=j;
			a[cnt].z=A+j;
			a[cnt].id=cnt;
			a[cnt].f=1;
		}
	}
	solve(1,cnt);
	int ans=0;
	for(int i=1;i<=cnt;i++)ans=max(ans,a[i].f);
	cout<<ans<<"\n";
	return 0;
}