P2870 [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold（加强版)(贪心+hash哈希）


洛谷上这道水题丧心病狂地把数据范围加到了500000
普通的做法肯定A不了了，所以用二分哈希去找第一个不同的地方。
在比较谁字典序小的时候，二分查找哈希值，找到最小元素使得哈希值不一样，然后比较就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define debugs(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
const ll N=5e5+7;
const ll base=137;//哈希base
const ll mod=2147483647;
template<typename T>inline T read(T &x)
{
    x=0;ll f=1;char c;
    while(!isdigit(c=getchar()))if(c=='-')f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
ll n,m,ha[N],hb[N],p[N],a[N],b[N],c[N];
char ch[3];
inline ll get_ha(ll l,ll r)//哈希正
{
    return ha[r]-ha[l-1]*p[r-l+1];
}
inline ll get_hb(ll l,ll r)//哈希逆
{
    return hb[r]-hb[l-1]*p[r-l+1];
}
inline ll find_distinct(ll i,ll j)
{
    ll L=0,R=n-j-i+2,mid;
    while(L<R)
    {
        mid=L+R>>1;
        if(get_ha(i,i+mid)^get_hb(j,j+mid))R=mid;//相同为0不同为1；
        else L=mid+1;
    }
    return L;
}
int main()
{
    read(n);p[0]=1;
    for(register ll i=1;i<=n;++i)
        scanf("%s",ch),a[i]=b[n-i+1]=ch[0]-'A';
    for(register ll i=1;i<=n;++i)
        p[i]=p[i-1]*base;
    for(register ll i=1;i<=n;++i)
        ha[i]=ha[i-1]*base+a[i];
    for(register ll i=1;i<=n;++i)
        hb[i]=hb[i-1]*base+b[i];
    ll i=1,j=1;
    while(i<=n-j+1)
    {
        ll len=find_distinct(i,j);
        if(a[i+len]<=b[j+len])c[++m]=a[i++];
        else c[++m]=b[j++];
    }
    for(register ll i=1;i<=m;++i)
    {
        printf("%c",c[i]+'A');
        i%80?0:puts("");
    }
    return 0;
}