3172: [Tjoi2013]单词

Time Limit: 10 Sec  

Memory Limit: 512 MB

Submit: 268  

Solved: 145

[ ][ ]

Description

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文 

中出现多少次。

Input

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

Output

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

 

 

上一次写RMQ是什么时候？(喂，离题了）

好吧……

第一题后缀数组

不想写下去了……（快哭了TNT)

这题在BZOJ上内存很容易开过（5人组-》TLE/CE/MLE/RE/AC）

大家要是这题RE把数组开小点。别忘了[RMQ*20]数组+数组之和 //省空间

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Rep(i,n) for(int i=0;i
            
             =0;i--)#define MEM(a) memset(a,0,sizeof(a))#define MEMI(a) memset(a,127,sizeof(a))#define MEMi(a) memset(a,128,sizeof(a))#define INF (2139062143)#define F (1000000009)#define MAXN (300+10)#define MAXL (1000200+10)#define eps (1e-9)typedef long long ll;char s[MAXL];int n,pre[MAXN],tai[MAXN];int w[MAXL],sa[MAXL],wa[MAXL*2]={0},wb[MAXL*2]={0};// x-->上一行 y->下一行sa右值 wv-->y的左值 sa-->上次排名(求) bool cmp(int *a,int x,int y,int l){return (a[x]==a[y]&&a[x+l]==a[y+l]);}void suffix_array(int n,int m){ int *x=wa,*y=wb; For(i,m) w[i]=0; For(i,n) w[x[i]=s[i]]++; Fork(i,2,m) w[i]+=w[i-1]; ForD(i,n) sa[w[x[i]]--]=i; for(int j=1,p=0;p
             
              >1; if (lcp(m,j-1)>=tai[i]) ans=m,r=m-1; else l=m+1; } if (ans) ans=j-1-ans+1; tot+=ans; } { int l=j,r=pre[n+1]-1,ans=0; while (l<=r) { int m=l+r>>1; if (lcp(j,m)>=tai[i]) ans=m,l=m+1; else r=m-1; } if (ans) ans=ans-j+1; tot+=ans; } cout<
              
               <