题面简述

现在有一个序列 p1,p2,,pnp_1,p_2,\dots,p_n,你需要构建一个无向图,规则是:当 i<ji < jpi>pjp_i > p_j 时在 iijj 之间连一条无向边。问最后图中会有几个连通块。

题目传送门

思路

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

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

参考代码

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