c++ - C++: (LIS) セグメント ツリーを使用した最長増加サブシーケンス

Question

N要素の配列が与えられた場合、 LとRのT個の異なる値について、最長増加サブシーケンスの長さを見つける必要があります。セグメント ツリーを試しましたが、Time Limit Exceeded になっています。

using namespace std;


  int a[1000001],ans[1000001],out;
  int T[1000001];
  int query(int v,int tl,int tr,int l,int r){
      if (l>r) return 0;
      if (tl==l && tr==r){
          return T[v];
      };
      int tm=(tl+tr)/2;
      return max(query(2*v,tl,tm,l,min(tm,r)),query(2*v+1,tm+1,tr,max(tm+1,l),r));
  };
  void update(int v,int tl,int tr,int pos,int val)
  {
       if (tl==tr){
          T[v]=val;
          return;
       };
       ll tm=(tl+tr)/2;
       if (tm>=pos) update(2*v,tl,tm,pos,val); else update(2*v+1,tm+1,tr,pos,val);
       T[v]=max(T[2*v],T[2*v+1]);
  };
int main()
{

        int n,i,t;
        cin>>n>>t;
       for (i=1;i<=n;i++)
          cin>>a[i];

        for(int j=0;j<t;j++)
        {
            int l,r;
           cin>>l>>r;
            for (i=l;i<=r;i++)
           { 
               ans[a[i]]=query(1,1,n,1,a[i]-1)+1;
               update(1,1,n,a[i],ans[a[i]]);
               out=max(out,ans[a[i]]);
           }

           cout<<out;
           out=0;

        }

    }


 return 0;
}

ここで、与えられたL, Rのペアごとに LIS を見つける必要があります。誰かがTクエリの時間の複雑さを改善するのを助けることができますか?

個別の for ループを使用して各クエリの答えを計算し、ネストされた forループを削除し、内側の for ループを使用して配列全体の LIS を一度に計算する方法はありますか?

更新:以前のエラーが整理されたため、質問を更新しました。