登录—专业IT笔试面试备考平台_牛客网

题目大意：给出一个长度为n的数组a，问有多少子串满足其可以用多个排列穿插构成

1<=n<=1e6

思路：因为每个排列的起点都是1，所以我们大致的策略就是对于每一个1，记录它往右最远到哪里可以构成合法的区间，因为1越多越好，1的数量是少于2的数量就不合法了，且我们发现越靠左的1，可能构成的区间就越长，所以如果出现不合法的情况，一定是最右边的1不合法，且它之后无论如何也不会变成合法的。

然后要判断不合法的情况，也就是a[i]的数量>a[i-1]的数量的情况，我们可以开n个栈，维护每个数字最后出现的位置，当出现a[i]的数量大于a[i-1]的数量时，最后的合法位置就是a[i-1]最后出现的位置，在那个位置右边到当前位置的1都不会再合法了，所以要单独开栈记录所有1的位置，如果出现不合法的情况，就将最后合法位置以外的1弹出，每遍历一个数就统计左边有多少个合法的1即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
vector<int>st[N];
int a[N];
vector<int>pos;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}ll ans = 0;for (int i = 1; i <= n; i++){if (a[i] == 1){pos.push_back(i);//记录每个1的位置st[1].push_back(i);//记录每个数字出现的位置}else{int r = 0;if (!st[a[i] - 1].empty()){r = st[a[i] - 1].back();//最后一次出现a[i]-1的位置st[a[i] - 1].pop_back();//维护可用的数字数量st[a[i]].push_back(i);}while (!pos.empty() && pos.back() > r){//最后一次合法位置右边的1都不合法pos.pop_back();}			}ans += pos.size();}cout << ans << endl;return 0;
}