[AGC063B] Insert 1, 2, 3, ... 题解

· · 题解

先来考虑怎样的区间是合法的。合法的区间 [L,R] 一定满足以下条件：

把上面的第二点转化一下，你就会发现——如果可以给每个 A_x>1 找一个再它左侧且离它最近的 A_x-1 匹配（每个 A_x-1 仅仅能匹配一次），那么这个区间就是合法的。也就是说，每个 A_x 都必须找到一个值为 A_x-1 的前驱——它的前驱与它之间的那一段区间就是后来插入的。

举个例子，序列 \{1,2,\color{Red}{1,2,3,4}\color{Black},3\}，假设已经考虑到最后一个 3，中间标红的部分已经完成匹配，3 只能找到离它最近的且没有匹配的 A_2=2 作为前驱——可以视为在一个序列 \{1,2,3\} 中插入了一个 \{1,2,3,4\}。

这个过程十分类似栈维护括号匹配，可以借助栈来完成类似的操作。

考虑枚举右端点 R，借助一个栈来完成操作的维护，栈内的一个元素 x 表示合成该序列的子序列的其中一个是 \{1,2,\ldots,x\}，栈的大小就是合法的左端点个数（为什么？根据栈内元素的意义可知，以 R 为右端点的合法区间是由若干个形如 \{1,2,\ldots,x\} 的子序列构成的，显然栈的大小就是子序列的个数，有几个子序列就有几个 1，而这里面每个 1 都可以作为一个合法的左端点）。

如果 A_R=1 那么直接把 1 放入栈内（在一个合法序列的末尾加上一个 1 它依然合法）；否则不断将栈顶弹出直到找出值为 A_R-1 的前驱——假设此时栈顶为 A_R-1，那么将其设为 A_R，表示把以 A_R-1 结尾的子序列长度增加 1；如果栈空了那么直接 continue（找不到前驱该元素不可能合法）。

每次答案加上栈的大小即可。时间复杂度 O(N)，足以通过。

放代码（代码精悍短小）：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; long long c=0; cin>>n;
  stack<int> s;
  for(int i=1;i<=n;i++){
    int a; cin>>a;
    if(a==1)s.emplace(1); // 如果是 1 就把它放进去
    else{
      while(!s.empty()&&s.top()+1!=a)s.pop();
      // 不断弹出栈顶找前驱的过程
      if(!s.empty())s.top()++; // 将栈顶改为 A[r]
    }
    c+=s.size(); // 答案加上合法左端点个数
  }
  cout<<c<<endl;
  return 0;
}