蒟蒻有一种用 set 的乱搞（？）做法。
将题目中的连边要求反着说一遍：\(i>j\) 且 \(a_i<a_j\)。
考虑遍历 \(a\) 时，遍历到的 \(a_i\) 编号一定要比它前面的大，只需要将前面比它大的元素都和它连起来。
将每个连通块看作一个整体，只要 \(a_i\) 比其中任意一个小，\(a_i\) 就可以加入这个连通块。
因此可以用 set 维护每个连通块的最大值（因为只需要小于最大值即可），在其中 lower_bound 或 upper_bound 出第一个大于 \(a_i\) 的位置。由于所有比 \(a_i\) 大的连通块都要和 \(a_i\) 相连成为同一个，因此将 set 中所有大于 \(a_i\) 的元素都删除，只保留最大的一个代表这个连通块。
剩下的一些细节看代码：
#include<bits/stdc++.h>
using namespace std;
set<int>st;
int main(){
int t;cin>>t;
while(t--){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);//干脆在线搞，x即为上文a[i]
auto it=st.upper_bound(x);
if(it==st.end())st.insert(x);//it==st.end()说明没有比x大的，因此x独立成为一个连通块
else while(++it!=st.end())//判断当前是否最大的元素
it=st.erase(--it);//由于刚才++了，现在要--回来。erase的返回值为下一个元素的迭代器
}
printf("%d\n",st.size());
st.clear();
}
return 0;
}
时间复杂度：
一次 upper_bound 的时间复杂度为 \(O(\log n)\)，共执行 \(n\) 次，bound 总复杂度 \(O(n\log n)\)。
一次 erase 的时间复杂度为 \(O(\log n)\)，每个元素最多被删除 \(1\) 次，一共最多删除 \(n\) 次，erase 总复杂度 \(O(n\log n)\)。
总复杂度 \(O(n\log n)\)，可过。