hdu 5008 Boring String Problem(后缀数组+rmq)

题意：

给你一个字符串，有q个询问，每次询问该字符串所有的子串中字典序第k小的是哪个串，输出位置，如果有多个位置，输出最靠左的那个。

题解：

后缀数组求完height后，求一下字典序第i的后缀有多少个不同的子串，然后求一下前缀和。

然后就可以每对于一个k，可以二分求到排序后第一个字典序为k的后缀，然后用rmq求一下最小就行了。

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 4 #define ___ freopen("c:\code\in.txt","r",stdin);
 5 inline int RT(int l,int r){return l+r|l!=r;}
 6 using namespace std;
 7 typedef long long ll;
 8 typedef pair<int,int>P;
 9 
10 namespace suffixarray{    
11     #define FN(n) for(int i=0;i<n;i++)
12     const int N =1E5+7;
13     int rnk[N],sa[N],height[N],c[N];char s[N];
14     void getsa(int n,int m,int *x=rnk,int *y=height){
15         FN(m)c[i]=0;FN(n)c[x[i]=s[i]]++;FN(m)c[i+1]+=c[i];
16         for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
17         for(int k=1,p;p=0,k<=n;k=p>=n?N:k<<1,m=p){
18             for(int i=n-k;i<n;i++)y[p++]=i;
19             FN(n)if(sa[i]>=k)y[p++]=sa[i]-k;
20             FN(m)c[i]=0;FN(n)c[x[y[i]]]++;FN(m)c[i+1]+=c[i];
21             for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
22             swap(x,y),p=1,x[sa[0]]=0;
23             for(int i=1;i<n;i++)
24             x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
25         }
26         FN(n)rnk[sa[i]]=i;
27         for(int i=0,j,k=0;i<n-1;height[rnk[i++]]=k)
28         for(k=k?k-1:k,j=sa[rnk[i]-1];s[i+k]==s[j+k];k++);
29     }
30 }
31 using namespace suffixarray;
32 
33 int n,q;
34 ll k,sum[N],L,R;
35 
36 int a[N][18],b[N][18];
37 void rmq(int *a,int f[][18])
38 {
39     for(int i=1;i<=n;i++)f[i][0]=a[i];
40     for(int j=1;1<<j<n;j++)for(int i=1;i<=n;i++)
41     if(i+(1<<j)-1<= n)f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
42     else break;
43 }
44 inline int find(int l,int r,int f[][18])
45 {
46     int k=31-__builtin_clz(r-l+1);
47     return min(f[l][k],f[r-(1<<k)+1][k]);
48 }
49 
50 void getkth(ll k)
51 {
52     if(k>sum[n]){L=R=0;return;}
53     int l=0,r=n,ans,mid;
54     while(l<=r)
55     {
56         mid=l+r>>1;
57         if(sum[mid]>=k)ans=mid,r=mid-1;
58         else l=mid+1;
59     }
60     k=k-sum[ans-1]+height[ans];
61     int pos=ans;
62     l=2,r=n-pos+1,ans=1;
63     while(l<=r)
64     {
65         mid=l+r>>1;
66         if(find(pos+1,pos+mid-1,a)>=k)l=mid+1,ans=mid;
67         else r=mid-1;
68     }
69     L=find(pos,pos+ans-1,b)+1,R=L+k-1;
70 }
71 
72 int main(){
73     while(~scanf("%s",s))
74     {
75         L=R=0,getsa((n=strlen(s))+1,150);
76         F(i,1,n)sum[i]=n-sa[i]-height[i]+sum[i-1];
77         rmq(height,a),rmq(sa,b);
78         scanf("%d",&q);
79         while(q--)
80         {
81             scanf("%lld",&k);
82             k=(k^L^R)+1,getkth(k);
83             printf("%lld %lld
",L,R);
84         }
85     }
86     return 0;
87 }

View Code