Victor and String HDU - 5421 双向回文树-白红宇

Victor and String HDU - 5421 双向回文树

阅读量：5030 次

发布时间：2019-06-12

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

题意：

有n种操作，开始给你一个空串，给你4中操作

1 c 在字符串的首部添加字符c

2 c 在字符串的尾部添加字符c

3 询问字符中的本质不同的回文串的个数

4 询问字符串中回文串的个数

思路：last[0]表示首部的操作的位置，last[1]表示尾部的操作的位置

模板提，用上双向的回文树就好了。

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 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                     = 0; --i)cnt[fail[i]] += cnt[i];101 //逆序累加，保证每个点都会比它的父亲节点先算完，于是父亲节点能加到所有子孙102 }103 } pam;104 char op[10];105 int n;106 int main() {107 //FIN;108 while(~sfi(n)){109 pam.init();110 LL ans=0;111 for (int i = 0,x; i < n; ++i) {112 sfi(x);113 if (x==1) {114 sfs(op);115 ans+=pam.add(op[0],0);116 }else if (x==2) {117 sfs(op);118 ans+=pam.add(op[0],1);119 }else if (x==3) printf("%d\n",pam.sz-2);120 else printf("%lld\n",ans);121 }122 }123 return 0;124 }