前言
这场 CF 是我赛后打的，vp 赛时没做出来，后来发现是有个地方理解错了，有一些细节没有考虑到。现在换了一种思路来写，感觉更清晰了。
做法
首先需要动态维护三个变量，\(cnt\) 和 \(finishsort\) 和 \(unfinishsort\)。这三个变量分别表示当前数字的个数，已经排好序的最后一个位置，和没有排好序的最前一个位置。首先我们知道如果序列要从有序的变为无序的，那么我们一定会贪心地将序列的最后一个位置变为无序的，因为这样才能更快地变回有序的，证明显然。接下来看四种操作：
- 在末尾新添加一个数
这时直接让 \(cnt\) 加一就可以了，其它的变量的值都不需要改变。因为此时我们还不能判断出当前这个数应该排序还是不排序，需要参考之后的询问来判断。
- 删去末尾的一个数
首先要让 \(cnt\) 减一。其次还要计算删去的这个数对整个序列的贡献，如果删去这个数之后 \(finishsort > cnt\)，那么要将 \(finishsort\) 变为 \(cnt\)；如果 \(unfinishsort > cnt\)，即整个序列已经全部有序，那么直接将 \(unfinishsort\) 变为 \(0\)。
- 判断这个序列无序
如果 \(finishsort=cnt\) 或者 \(cnt<2\)，即整个序列有序，那么直接判断为不合法。否则如果 \(unfinishsort\) 等于 \(0\)，就将 \(unfinishsort\) 设置为当前位置。
- 判断这个序列有序
如果 \(unfinishsort\) 不等于 \(0\) 的话，那么一定是不合法的。否则将 \(finishsort\) 设置为当前位置。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define re register
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
int T,n,cnt,unfinish_sort,finish_sort;
char c[MAXN];
signed main()
{
cin >> T;
while(T--)
{
cin >> (c + 1);
int len = strlen(c + 1),flag = true;
cnt = finish_sort = unfinish_sort = 0;
for(int i = 1;i <= len;i++)
{
if(c[i] == '0')
{
if(cnt == finish_sort || cnt < 2){flag = false;break;}
if(!unfinish_sort) unfinish_sort = cnt;
}
if(c[i] == '1')
{
if(unfinish_sort != 0){flag = false;break;}
finish_sort = cnt;
}
if(c[i] == '+') cnt++;
if(c[i] == '-')
{
cnt--;
if(cnt < unfinish_sort) unfinish_sort = 0;
if(cnt < finish_sort) finish_sort = cnt;
}
}
if(flag == true) puts("YES");
else puts("NO");
}
return 0;
}