[cf1458D]Flip and Reverse

将$s$中的01分别变为$1,-1$，即得到一个序列$a_{i}$（设其长度为$n$，下标范围为$[1,n]$）

对$a_{i}$建立一张有向图，其点集合为$Z$，并对$forall 0le k<n$从$sum_{i=1}^{k}a_{i}$向$sum_{i=1}^{k+1}a_{i}$连边（允许重边），那么$a_{i}$即对应于其中一条以0为起点的欧拉路

若对区间$[l,r]$操作，记操作后的序列为$a'_{i}$，则有$sum_{i=l}^{r}a_{i}=0(=sum_{i=l}^{r}a'_{i})$且$forall lle ile r,a'_{i}=-a_{r-(i-l)}$

根据此性质，简单来分析前缀和的变化：

1.对于$k otin [l,r),sum_{i=1}^{k}a'_{i}=sum_{i=1}^{k}a_{i}$

2.对于$kin [l,r),sum_{i=1}^{k}a'_{i}=sum_{i=1}^{l-1}a_{i}-sum_{i=l}^{k}a_{r-(i-l)}=sum_{i=1}^{r-(k-l)-1}a_{i}$

进一步的，再来分析这条欧拉路的变化，结合前缀和的变化即是将原本从$sum_{i=1}^{l-1}a_{i}$到$sum_{i=1}^{r}a_{i}$这一个环（注意两值相同）反转（将所有边变为反向边）并倒序经过

另一方面，显然每一个环（包括非简单环）都可以以此法操作（注意这里的操作是对欧拉路）

换言之，问题即通过这样的操作最小化这条欧拉路的字典序

实际上，问题也可以看作：将图中的边看作无向边后，最小化以0为起点的欧拉路字典序

注意到操作只是反转边的方向，那么得到的欧拉路一定是新问题中的欧拉路

另一方面，即要通过这条欧拉路（通过操作）构造出所有新问题中的欧拉路

对其归纳，若其第一步与这条欧拉路方向不同，分类讨论：

1.若该边仅存在一条（指无向边），那么起点的另一个方向即必然不存在边（否则这不是欧拉路），进而显然方向不会不同

2.若该边存在多条，之后总有一次从该边返回起点，从最初到该位置全部反转后方向即相同

进一步的，将两者第一步均删除后即变为归纳的问题（边数减少），也即得证

而对于这个新问题，可以利用图的特殊性直接贪心：初始$x=0$，每一次优先向$x-1$移动（除非该边仅存在一条且$x$到$x+1$仍有边，此时向$x+1$移动），最终显然字典序最小

时间复杂度为$o(n)$，可以通过

#include<bits/stdc++.h>
using namespace std;
#define N 500005
int t,n,x,sum,cnt[N<<1];
char s[N];
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%s",s+1);
        n=strlen(s+1),x=sum=n;
        for(int i=0;i<=(n<<1);i++)cnt[i]=0;
        for(int i=1;i<=n;i++){
            if (s[i]=='0')cnt[--sum]++;
            else cnt[sum++]++;
        }
        for(int i=1;i<=n;i++){
            if ((cnt[x-1]>1)||(!cnt[x])){
                putchar('0');
                cnt[--x]--;
            }
            else{
                putchar('1');
                cnt[x++]--;
            }
        }
        putchar('
');
    }
    return 0;
}