Reverse the String

题目传送门

题意

给出一个字符串，有一种操作，将其中一个子串反转，我们可以进行最多一次这样的操作，需要使得这个字符串字典序最小。

$T$ 组数据， $1 \leq |s| \leq 10^5$ ， $\sum|s| \leq 1.5 * 10^6$

思路

这里又要用到字符串哈希了。

我们使用一个 $pair$ 数组 $suf[]$ 来存下标 $i$ 之后的最小的字母及其最后出现的位置。

容易想到，如果每个位置上的字母都不比后面的字母大，那么这个字符串就已经是字典序最小的了，这时候直接输出就行。

如果对于一个位置 $i$ ， $suf[i].first$ 要小于 $s[i]$ ，那么这时，我们找到这个最小的 $i$ ，说明这时的 $i$ 就是我们需要进行反转操作的子串的起点。我们可以遍历后面的每一个点作为字串的终点，找出一个最优解即可。

那么我们如何进行比较两个终点哪个更优呢，我们可以考虑使用字符串哈希加二分，初始化两个哈希，一个正着，一个反着，对于两个终点，我们使用二分查找反转后的子串的 $lcp$ ，那么比较这个 $lcp$ 后面的那个字母大小关系即可。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<char,int> P;
const int MAXX=100005;

int n;
char a[MAXX],s[MAXX];

typedef unsigned long long ull;
//prim 是自己设置的一个素数,具体数值根据情况而定
ull p[MAXX],hasha[MAXX],hashs[MAXX],prim=233;

inline void init(){
    p[0]=1ull;
    for(int i=1;i<MAXX;++i)
        p[i]=p[i-1]*prim;
}
inline ull gethasha(int l,int r){
    return hasha[r]-hasha[l-1]*p[r-l+1];
}
inline ull gethashs(int l,int r){
    return hashs[l]-hashs[r+1]*p[r-l+1];
}
// for(int i=1;i<=n;++i)
//     hash[i]=hash[i-1]*prim+a[i];

P suf[MAXX];

inline bool xiao(int st,int en,int enn){
    int l=0,r=enn-st+1,mid;
    while(l<r){
        mid=(l+r)/2;
        if(mid==l){
            ++mid;
            ull jj,kk;
            if(mid>en-st+1){
                jj=gethashs(st,en)*p[mid-(en-st+1)]+gethasha(en+1,en+mid-(en-st+1));
            }
            else
                jj=gethashs(en-mid+1,en);
            kk=gethashs(enn-mid+1,enn);
            if(jj==kk)
                l=mid;
            break;
        }
        else{
            ull jj,kk;
            if(mid>en-st+1){
                jj=gethashs(st,en)*p[mid-(en-st+1)]+gethasha(en+1,en+mid-(en-st+1));
            }
            else
                jj=gethashs(en-mid+1,en);
            kk=gethashs(enn-mid+1,enn);
            if(jj==kk)
                l=mid;
            else
                r=mid-1;
        }
    }

    if(l>=en-st+1)
        return a[st+l]<a[enn-l];
    return a[en-l]<a[enn-l];
}

inline void solve(){
	getchar();scanf("%s",a+1);
    n=strlen(a+1);
    a[n+1]='z';
    hashs[n+1]=0;
    for(int i=1;i<=n;++i)
        hasha[i]=hasha[i-1]*prim+a[i];
    for(int i=n;i>=1;--i)
        hashs[i]=hashs[i+1]*prim+a[i];
    
    suf[n]=P(a[n],n);
    for(int i=n-1;i>=1;--i){
        if(a[i]<suf[i+1].first)
            suf[i]=P(a[i],i);
        else
            suf[i]=suf[i+1];
    }
    
    int st=0,en=0;
    for(int i=1;i<=n;++i){
        if(a[i]>suf[i].first){
            st=i,en=suf[i].second;
            break;
        }
    }
    if(st==0){
        for(int i=1;i<=n;++i)
            printf("%c",a[i]);
        printf("\n");
        return;
    }
    
    for(int i=en-1;i>st;--i)
        if(xiao(st,i,en))
            en=i;

    // printf("*%d %d\n",st,en);//

    for(int i=1;i<st;++i)
        printf("%c",a[i]);
    for(int i=en;i>=st;--i)
        printf("%c",a[i]);
    for(int i=en+1;i<=n;++i)
        printf("%c",a[i]);
    printf("\n");
}

signed main(){
    init();
	int t;scanf("%d",&t);
	while(t--)
		solve();
	
	return 0;
}