后缀数组da3模板-白红宇

后缀数组da3模板

阅读量：7174 次

发布时间：2019-06-29

本文共 1037 字，大约阅读时间需要 3 分钟。

在做poj2406的时候。。。按论文给的rmq模板会超内存。。。然后网上找了http://blog.csdn.net/libin56842/article/details/46310425这位大爷的da3rmq就过了= =

1 #include 
     
          2 #include 
      
           3 #include 
       
            4 #include 
        
             5 #include 
         
              6 #include 
           7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 using namespace std; 14 15 #define LS 2*i 16 #define RS 2*i+1 17 #define UP(i,x,y) for(i=x;i<=y;i++) 18 #define DOWN(i,x,y) for(i=x;i>=y;i--) 19 #define MEM(a,x) memset(a,x,sizeof(a)) 20 #define W(a) while(a) 21 #define gcd(a,b) __gcd(a,b) 22 #define LL long long 23 #define N 1000005 24 #define MOD 1000000007 25 #define INF 0x3f3f3f3f 26 #define EXP 1e-8 27 28 #define F(x) ((x)/3+((x)%3==1?0:tb)) 29 #define G(x) ((x)
                 
                  =0; i--) b[--wsf[wv[i]]]=a[i]; 53 return; 54 } 55 void dc3(int *r,int *sa,int n,int m) 56 { 57 int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p; 58 r[n]=r[n+1]=0; 59 for(i=0; i