BZOJ 3172([Tjoi2013]单词-后缀数组第一题+RMQ)

3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 268 Solved: 145
[Submit][Status]
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<