将分治每一层内部用 $\log len$ 的复杂度实现。

是否可以去掉一个log。

具体思路就是现开vector做树状数组和离散化。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Data
{
    int x,a,L,R,f;
}q[N];
int n,m;

inline int lowbit(int x)
{
	return x&-x;
}

inline void init(vector<int> &tr,int M)
{
	tr.resize(M+1);
	for(int i=0;i<=M;i++) tr[i]=0;
}

inline void add(vector<int> &tr,int x,int M,int c)
{
	for(int i=x;i<=M;i+=lowbit(i)) tr[i]=max(tr[i],c);
}

inline int sum(vector<int> &tr,int x)
{
	int res=0;
	for(int i=x;i;i-=lowbit(i)) res=max(res,tr[i]);
	return res;
}

inline int find(vector<int> &nums,int x)
{
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1;
}

inline bool cmp1(Data A,Data B)
{
    return A.x<B.x;
}

inline bool cmp2(Data A,Data B)
{
    return A.a<B.a;
}

inline bool cmp3(Data A,Data B)
{
    return A.L<B.L;
}

void solve(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1,len=r-l+1;
    solve(l,mid);
    sort(q+l,q+1+mid,cmp2),sort(q+mid+1,q+1+r,cmp3);
    
    vector<int> tr,nums;
    for(int i=l;i<=mid;i++) nums.push_back(q[i].R);
    for(int i=mid+1;i<=r;i++) nums.push_back(q[i].a);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
	 
    init(tr,len);
    
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i].a<=q[j].L) add(tr,find(nums,q[i].R),len,q[i].f),i++;
        else q[j].f=max(q[j].f,sum(tr,find(nums,q[j].a))+1),j++;
    }
    while(i<=mid) add(tr,find(nums,q[i].R),len,q[i].f),i++;
    while(j<=r) q[j].f=max(q[j].f,sum(tr,find(nums,q[j].a))+1),j++;
    
    tr.clear(),nums.clear();
    
    sort(q+mid+1,q+1+r,cmp1);
    solve(mid+1,r);
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    
    cin>>n>>m;
    
    for(int i=1;i<=n;i++) 
    {
        q[i].x=i;
        cin>>q[i].a;
        q[i].L=q[i].R=q[i].a,q[i].f=1;
    }
    
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        q[x].L=min(q[x].L,y);
        q[x].R=max(q[x].R,y);
    }
    
    solve(1,n);
    
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,q[i].f);
    
    cout<<res<<"\n";
    
    return 0;
}