登錄—專業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;
}