Insert 1, Insert 2, Insert 3, ...

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

H题，每次向序列插入1到k（必须从1开始累加，插入的可以间隔的，不要求插入连续）。现在给了一个大数组，求这个数组内有多少个区间[ l, r]是可以按照上述操作得到。

样例：

# input
6
1 2 1 2 1 3

#output
11

# 分别是
[1,1] [1,2] [1,3] [1,4] [1,5] [1,6]
[3,3] [3,4] [3,5] [3,6]
[5,5]
1
2
3
4
5
6
7
8
9
10
11

可以发现如果[l, r]区间可以按操作得到，那么

• 该区间一定存在1
• 该区间最多有r - l + 1个1，最少有1个1
• 有x(x != 1)，那么一定有x-1，且x的个数小于等于x-1
• x (x != 1)跟x-1有关

可以发现，对于这种样例：

1 2 1 1 1 1 1 3 3 1 2
1

到达3对应下标后，前面的都是不满足。

如果以下标j为右端点，且aj = x(x != 1)。那么前面一定要有对应的x-1才可能得到。而且有类似与上面的样例发现，在得知j前面的所有元素都是不可能再用上时，要进行删除，防止卡时间和空间。

具体思路是：将1放入一个栈中，同时将下标放入数组中。每次如果有大于1的数x，就找最近的x-1所指向x-2的…，这样得到的就是一个链，从x到x-1到…到1的一个链，这样可以得到每个右端点j有多少个是可能得到的。将大于右端点j的元素1的下标出栈，进而得到的就是右端点到左端可以得到的区间数。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
#define int long long
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;

void inpfile();
void solve() {
    int n; cin>>n;
    vector<vector<int>> a(n + 1);
    int ans = 0;
    // 用vector模拟stack
    vector<int> stk;
    for(int i = 0; i < n; ++i) {
        int t; cin>>t;
        // 如果是1，入栈，且向1后面插入1的坐标
        if(t == 1) stk.push_back(i), a[t].push_back(i);
        else {
            // 否则找x x-1 x-2 ... 1中最原始1的下标位置
            int cur = -1;
            if(a[t - 1].size()) {
                cur = a[t - 1].back();
                a[t - 1].pop_back();
                a[t].push_back(cur);
            }
            // 将大于上面最原始1的下标的出栈
            while(stk.size() && stk.back() > cur) stk.pop_back();
        }
        // 统计当前j的可行区间数
        ans += stk.size();
    }
    cout<<ans<<endl;
}
signed main()
{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77