题目描述

You are given a permutation p1,p2,…,pn. Then, an undirected graph is constructed in the following way: add an edge between vertices i, j such that i < j if and only if pi > pj. Your task is to count the number of connected components in this graph.

Two vertices u and v belong to the same connected component if and only if there is at least one path along edges connecting u and v.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Input
Each test contains multiple test cases. The first line contains a single integer t (1≤t≤10^5) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤10^5) — the length of the permutation.

The second line of each test case contains n integers p1,p2,…,pn (1≤pi≤n) — the elements of the permutation.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

Output
For each test case, print one integer k — the number of connected components.

样例

input

6
3
1 2 3
5
2 1 4 3 5
6
6 1 4 2 5 3
1
1
6
3 2 1 6 5 4
5
3 1 5 2 4

output

3
3
1
1
2
1

大致题意

共有t组数据，每组数据给定一个长度为n的序列，该序列为1 ~ n的一个排列。
在序列中，互为逆序的两个数同属一个集合，求序列中集合的数量。

思路

本题数据范围为2*10^5,首先想到暴力筛查找出每个逆序对，然后使用并查集合并集合，最后求出集合数量，这样的方式时间复杂度为O(n^2)，肯定会超出数据范围。

经过观察，会发现仅需从头遍历，维护最大值即可，此时，每遍历到一个数都会有以下两种情况：

1. 当一个数小于当前最大值时，与最大值同属一个集合，集合数量不变
2. 当一个数大于当前最大值时，两数不能形成逆序对，但如果两数后方存在一个数同时小于这两个数，则两者依旧属于同一个集合，集合数量不变，否则集合数量+1。

对于情况1，简单判断即可，单次操作时间复杂度为O(1)
对于情况2，如果我们选择从当前位置遍历一遍数组，找出有没有一个数小于当前最大值，整体时间复杂度会回到O(n^2)，所以我们应该找到一个快速判断的方法。
不难发现，由于整个数列是1 ~ n的一个排列，假设当前我们遍历至第i个数，则前i-1个数的最大值为当前最大值maxx
如果i-1 == maxx,则1 ~ i-1中的所有数都已经出现，否则必定会有一个数比当前最大值maxx小的出现在第i个数字之后。
这样一来，我们就能在O(n)的时间内准确判断所遍历的每一个数会不会产生一个新的集合，从而计算出集合的数量

时间复杂度

O(n)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t, x;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int cnt=0, maxx = 0;
        for(int i=1;i<=n;i++)
        {
            cin >> x;
            if(x>maxx)
            {
                if(maxx==i-1) cnt++;
                maxx = x;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}