【题解】AT4502：[AGC029C] Lexicographic constraints

原题传送门
首先想到类似进制或是全排列一样的操作
假如$k=3$
可以

111
1111
1112
1113
1131
12
121
13
2
2111
2112

可以总结出一些规律

• 若$a_i>a_{i-1}$，就直接在$s_{i-1}$的末尾补1，补到当前长度为止
• 若$a_i=a_{i-1}$，$s_i$就是$s_{i-1}$的下一个排列
• 若$a_i<a_{i-1}$，先把$s_{i-1}$末尾砍掉一段，跟当前长度相同为止，再取下一个排列

取下一个排列可以暴力，但是太慢了

可以先二分答案，确定$k$
然后每一个字符串其实是继承上一个字符串的状态，再加以发展
第一种情况可以忽略
用一个单调栈维护当前状态所有数值上是大于1的位置
然后依然是暴力模拟，但是可以过了

Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct data{
	int u, v;
}stk[maxn];
int top, n, a[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void insert(int u, int v){
	while (top && stk[top].u > u) --top;
	if (stk[top].u == u) ++stk[top].v;
	else stk[++top] = (data){u, 1};
	if (stk[top].v == v) --top, insert(u - 1, v);
}

bool check(int mid){
	stk[top = 1] = (data){0, 0};
	for (int i = 2; i <= n; ++i)
		if (a[i] <= a[i - 1]) insert(a[i], mid);
	return stk[1].v == 0;
}

int main(){
	n = read();
	int flag = 0;
	for (int i = 1; i <= n; ++i){
		a[i] = read();
		if (a[i] <= a[i - 1]) flag = 1;
	}
	if (!flag) return puts("1"), 0;
	int l = 2, r = n, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, r = mid - 1; else l = mid + 1;
	}
	printf("%d\n", ans);
	return 0;
}