[HDOJ3553 Just a String]【后缀数组搞的像Treap一样的伪后缀树】★★

【题目大意】
一个串的子串定义为其中连续的某一段。
给定一个串，问他的所有子串中，字典序为m的是哪一个子串？
【算法分析】
这个是典型的后缀树问题。只需深度优先遍历一下后缀树就很容易得到这个解。
现在问题来了。。。我不会O(n)构造后缀树。
好吧。那么退一步，我搞个后缀数组。
然后把height建好。然后可以发现。。。其实我们可以在这个搞好的后缀树上模拟后缀树的DFS遍历。。。
好吧，说说这种从Suffix Array->Suffix Tree的沙茶做法。
考虑现在我们已经建好height的ST表，那么我们每次取一个height最小的地方，按这个点划分成两半。然后两半在各自划分下去。
然后现在搞成了一棵heap的关键字是 height ，平衡树的关键字是 某后缀 的“Treap”。
好了。。我们现在可以在这颗“伪后缀树”上搞了。
显然，如果是真的后缀树的话，我们的做法应当是从小到大判断每个叉加起来的子串数量够不够m。然后每次只需选一个叉前进即可。
当然，有可能不前进，那就是后缀树的这个点所压缩的东西，已经足够m了。
然后现在我们来看看这颗伪后缀树和真后缀树的差别。
其实他们所不同的地方就是，假如当前节点有2个以上分叉，
那么后缀树会搞出相等数量的分叉在弄下去。
而对于现在这颗伪后缀树，我们会选择任意一个叉，然后再将它们划分成两边。
然后这样就会造成本身是同深度的叉，变成深度不同了。其实将这些叉合回来就是真后缀树了。
但是对这个题目，我们并不需要把他合回来。现在的信息已经足够我们执行上面红色的算法了。
具体就是搞一个Len_Sum[i]表示后缀数组中前i个后缀的总长度。然后就可以O(1)判断那个叉是对的。然后跑下去。并用cut这个变量表示已经算好了ans的多少长度。
最后有一些琐碎的问题，就是那个后缀树的压缩连续的冗余结点，在这个伪后缀树里体现为假设每次取的那个height最小值!=cut的情况。这时这个伪后缀树中，height最小值-cut,就是那个压缩值的长度。
【其它】2Y。T_T。那个计算要用int64。读入也要。
【CODE】
#include #include #include #include #include using namespace std;
typedef long long lld;
const int N=105555;
int n;
lld m;
char S[N];
char ans[N];
int sa[N];
int lg[N];
int Sum[N];
int rank[N];
int List[N];
int a[N][3];
int b[N][3];
int height[N];
int rmq[18][N];
int pos[18][N];
lld Len_Sum[N];

bool cmp(int i,int j){return S[i]

void Radix_sort(){
     int i,k;
     for (k=1;k>=0;k–){
         for (i=0;i<=n;i++) Sum[i]=0;
         for (i=1;i<=n;i++) Sum[a[i][k]+1]++;
         for (i=1;i<=n;i++) Sum[i]+=Sum[i-1];
         for (i=1;i<=n;i++) memcpy(b[++Sum[a[i][k]]],a[i],12);
         for (i=1;i<=n;i++) memcpy(a[i],b[i],12);
     }
}

void make_suffix_arr(){
     int i,cnt,k,s;
     for (i=1;i<=n;i++) List[i]=i;
     sort(List+1,List+n+1,cmp);
     for (cnt=0,i=1;i<=n;i++)
       rank[List[i]]=( cnt+=(i==1 || S[List[i]]!=S[List[i-1]]) );
     for (k=1;cnt!=n;k++){
         s=1<<(k-1);
         for (i=1;i<=n;i++){
             a[i][0]=rank[i];
             a[i][1]=(i+s>n)?0:rank[i+s];
             a[i][2]=i;
         }
         Radix_sort();
         for (cnt=0,i=1;i<=n;i++)
           rank[a[i][2]]=( cnt+=(i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) );
     }
     for (i=1;i<=n;i++) sa[rank[i]]=i;
}

void make_height(){
     memset(height,0,sizeof(height));
     int i,j,k,st;
     for (i=1;i<=n;i++){
         if (rank[i]==1) continue;
         st=max(0,height[rank[i-1]]-1);
         j=i+st; k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && S[j]==S[k]){j++; k++; st++;}
         height[rank[i]]=st;
     }
}

void build_rmq(){
     int i,k;
     for (i=1;i<=n;i++){
         rmq[0][i]=height[i];
         pos[0][i]=i;
     }
     for (k=1;1<       for (i=1;i+(1<         if (rmq[k-1][i]<=rmq[k-1][i+(1<           rmq[k][i]=rmq[k-1][i];
           pos[k][i]=pos[k-1][i];
         }
         else{
           rmq[k][i]=rmq[k-1][i+(1<           pos[k][i]=pos[k-1][i+(1<         }
}

int Get_Min_Pos(int l,int r){
    if (l>r) swap(l,r);
    int k=lg[r-l+1];
    return rmq[k][l]<=rmq[k][r-(1<}

void Output(int i,int Len){
     int j;
     for (j=0;j       putchar(S[sa[i]+j]);
     putchar(‘n’);
}

void solve(){
     lld cnt=0,cut=0,l=1,r=n,i,res;
     Len_Sum[0]=0;
     for (i=1;i<=n;i++)
       Len_Sum[i]=Len_Sum[i-1]+(n-sa[i]+1);
     while (l           i=Get_Min_Pos(l+1,r);
           res=height[i]-cut;
           if (cnt+res*(r-l+1)>=m){
             Output(l,(m-cnt-1)/(r-l+1)+1+cut);
             return;
           }
           cnt+=res*(r-l+1);
           cut+=res;
           if (Len_Sum[i-1]-Len_Sum[l-1]-(i-l)*cut+cnt>=m)
             r=i-1;
           else{
             cnt+=Len_Sum[i-1]-Len_Sum[l-1]-(i-l)*cut;
             l=i;
           }
     }
     Output(l,m-cnt+cut);
}

int main(){
    int Tc,i;
    lg[1]=0;
    for (i=2;i      if (i==1<                      else lg[i]=lg[i-1];
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        scanf("%s %I64d",S+1,&m);
        printf("Case %d: ",i);
        n=strlen(S+1);
        make_suffix_arr();
        make_height();
        build_rmq();
        solve();
    }
}