hdu 4436 str2int 后缀数组

#include   
#include   
#include   
#include   
#include   
using namespace std;  
const int maxn=1e5+1e5+9,mod=2012;  
char a[maxn];  
int r[maxn];  
int next[maxn];  
long long dp[maxn];  
int prel[maxn],sum[maxn],pp[maxn],ff[maxn];  
int minrmq[maxn][20];  
int *rank,height[maxn],sa[maxn];  
int wx[maxn],wy[maxn],cnt[maxn];//后缀数组使用的过程数组  
//height排名为i和i-1的后缀的最长前缀，rank后缀的排名，sa排名为i的后缀的起始位置。  
inline bool cmp(int *r,int a,int b,int l)  
{  
    return r[a]==r[b]&&r[a+l]==r[b+l];  
}  
//n为字符串长度，m为最大的字符的值。  
void da(int *r,int n,int m)//r数组不能出现0  
{  
    r[n+1]=0;  
    int i,l,p,*x=wx,*y=wy,*t;  
    memset(cnt,0,sizeof(int)*(m+1));  
    for(int i=1;i<=n;i++) cnt[x[i]=r[i]]++;  
    for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];  
    for(int i=n;i>=1;i--) sa[cnt[x[i]]--]=i;  
    for(l=1,p=1;pl)  
        y[p++]=sa[i]-l;  
        memset(cnt,0,sizeof(int)*(m+1));  
        for(i=1;i<=n;i++) cnt[x[i]]++;  
        for(i=1;i<=m;i++) cnt[i]+=cnt[i-1];  
        for(i=n;i>=1;i--) sa[cnt[x[y[i]]]--]=y[i];  
        for(t=x,x=y,y=t,p=1,x[sa[1]]=1,i=2;i<=n;i++)  
        x[sa[i]]=cmp(y,sa[i-1],sa[i],l) p:++p;  
    }  
    rank=x;  
    int j,k=0;  
    for(i=1;i<=n;height[rank[i++]]=k)  
    for(k k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);  
    return;  
}  
  
void getrmq(int n)//n为数据大小  
{  
    for(int i=1;i<=n;i++)  
    minrmq[i][0]=height[i];  
    for(int i=1;(1< s;  
    s.clear();  
    for(int i=1;i<=n;i++)  
    {  
       set  :: iterator p=s.lower_bound(rank[n-i+1]);  
  
       if(p!=s.end())  
       {  
           prel[i]=askrmq(rank[n-i+1]+1,*p);  
       }  
  
       if(p!=s.begin())  
       {  
           p--;  
           prel[i]=max(prel[i],askrmq((*p)+1,rank[n-i+1]));  
       }  
        s.insert(rank[n-i+1]);  
    }  
  
    next[1]=1;  
    for(int i=2;i<=n;i++)  
    {  
        if(a[i-1]=='0')  
        {  
            next[i]=next[i-1];  
        }  
        else  
        next[i]=i;  
    }  
  
//    for(int i=1;i<=n;i++)  
//    {  
//        if(prel[i]!=0)  
//        prel[i]+=i-prel[i]+1-next[i-prel[i]+1];  
////        else  
////        prel[i]+=i-next[i]+1;  
//    }  
  
}  
  
int zero[maxn];  
void solve(int n)  
{  
    dp[0]=0;  
    sum[0]=0;  
    ff[0]=0;  
  
    bool flag=false;  
    a[0]='#';  
    for(int i=0,k=1,m=(a[i]!=0);i<=n;i++)  
    {  
        if(a[i]=='#')  
        {  
            zero[i]=0;  
            sum[i]=0;  
            dp[i]=dp[i-1];  
            k=0;  
            m=0;  
            ff[i]=0;  
            flag=false;  
            while(a[i+1]=='0')  
            {  
                ff[i]=0;  
                sum[i]=0;  
                i++;  
                dp[i]=dp[i-1];  
                zero[i]=0;  
            }  
        }  
        else  
        {  
            k++;  
            sum[i]=(sum[i-1]*10+(a[i]-'0')*(k-m))%mod;  
            ff[i]=(ff[i-1]*10+a[i]-'0')%mod;  
            dp[i]=(dp[i-1]+sum[i])%mod;  
  
            int tmp=(ff[i]-ff[i-prel[i]]*pp[prel[i]]+mod*mod)%mod;  
  
            dp[i]-=sum[i]-(sum[i-prel[i]]*pp[prel[i]]+tmp*(k-prel[i]-zero[i-prel[i]]));  
            dp[i]=(dp[i]+(long long)2012000000*10)%mod;  
  
            zero[i]=zero[i-1];  
            if(a[i]=='0')  
            {  
                m++;  
                zero[i]++;  
            }  
//            else m=0;  
  
        }  
    }  
    cout<