C ++: (LIS) самая длинная возрастающая подпоследовательность с использованием дерева сегментов

Учитывая массив N элементы, мне нужно найти длину самой длинной увеличивающейся подпоследовательности для T разные значения L а также р. Я пробовал деревья сегментов, у меня превышен лимит времени.

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;
}

Теперь мне нужно выяснить LIS для каждой пары L, R. Может ли кто-то помочь импровизировать сложность времени для T запросы?

Есть ли способ рассчитать ответ на каждый запрос, используя отдельные для цикла и удалите вложенный для цикла и использовать внутренний цикл рассчитать LIS для всего массива сразу?

Обновить : Предыдущая ошибка разбирается, поэтому я обновил вопрос.