CF1638C Inversion Graph

题面简述

现在有一个序列 $p_1,p_2,\dots,p_n$，你需要构建一个无向图，规则是：当 $i < j$ 且 $p_i > p_j$ 时在 $i$ 和 $j$ 之间连一条无向边。问最后图中会有几个连通块。

题目传送门

思路

我们考虑什么时候会形成一块。

很显然，当 $\max\limits_{1\le j \le i}(p_j) = i$ 时前面的项就已经出现了 $p_1$ ~ $p_j$ ，对后面的块就没有影响了，这样答案就要加 $1$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e6 + 10;

int T , N;
int Ans;
int Num[MAXN];
int Max;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--) {
        cin >> N;
        Ans = 0;
        Max = 0;
        for(int i = 1; i <= N; i++) cin >> Num[i];
        for(int i = 1; i <= N; i++) {
            Max = max(Max , Num[i]);
            if(Max == i) Ans++;
        }
        cout << Ans << endl;
    }
    return 0;
}