hdu 4125 Moles(kmp+树状数组)

题目链接：hdu 4125 Moles

题意：

给你n个数，让你按键值建一个平衡二叉树，然后奇数为0，偶数为1，然后可以遍历这颗树得到一个欧拉序列，现在给你一个串，问你出现了几次。

题解：

建树的时候要引用一个结论：就是新插入的数的父亲，要么是比它大的最小的那个元素，要么是比它小的最大的那个元素。

这样才能nloglogn建树，其实可以用set nlogn建树，但是空间要被卡，然后换用树状数组来替代set。

我这份代码没用KMP跑了4000+，用了kmp只会跑2000+。kmp还是在大串上比较有优势。

  1 #include<bits/stdc++.h>
  2 #define F(i,a,b) for(int i=a;i<=b;i++)
  3 using namespace std;
  4 const int N=6e5+7;
  5 int t,n,cas,a[N],l[N],r[N],S[N],top,len,C[N],root,mi,mx;
  6 char s[N*2],b[N],vis[N];
  7 
  8 void add(int x){while(x<=n)C[x]++,x+=x&-x;}
  9 inline int sum(int x){int an=0;while(x)an+=C[x],x-=x&-x;return an;}
 10 
 11 void insert(int x)
 12 {
 13     add(x);
 14     int tt=sum(x);
 15     if(!root)
 16     {
 17         root=mi=mx=x;
 18         return;
 19     }
 20     if(x>mx)
 21     {
 22         r[mx]=x,mx=x;
 23         return;
 24     }
 25     if(x<mi)
 26     {
 27         l[mi]=x,mi=x;
 28         return;
 29     }
 30     mi=min(mi,x),mx=max(mx,x);
 31     int ll=1,rr=x-1,mid;
 32     while(ll<rr)
 33     {
 34         mid=ll+rr>>1;
 35         if(sum(mid)==tt-1)rr=mid;
 36         else ll=mid+1;
 37     }
 38     if(!r[rr])
 39     {
 40         r[rr]=x;
 41         return;
 42     }
 43     ll=x+1,rr=n;
 44     while(ll<rr)
 45     {
 46         mid=ll+rr>>1;
 47         if(sum(mid)!=tt)rr=mid;
 48         else ll=mid+1;
 49     }
 50     l[rr]=x;
 51 }
 52 
 53 void init()
 54 {
 55     root=0;
 56     F(i,0,n)C[i]=0;
 57     F(i,1,n)l[i]=r[i]=0;
 58     F(i,1,n)insert(a[i]);
 59 }
 60 
 61 void dfs()
 62 {
 63     F(i,0,n)vis[i]=0;
 64     top=1,S[1]=a[1];
 65     while(top)
 66     {
 67         int now=S[top];
 68         s[len++]='0'+(now&1);
 69         if(l[now]&&!vis[l[now]]){S[++top]=l[now];continue;}
 70         if(r[now]&&!vis[r[now]]){S[++top]=r[now];continue;}
 71         top--;
 72         vis[now]=1;
 73     }
 74 }
 75 
 76 int main()
 77 {
 78     scanf("%d",&t);
 79     while(t--)
 80     {
 81         scanf("%d",&n);
 82         F(i,1,n)scanf("%d",a+i);
 83         scanf("%s",b);
 84         int lenb=strlen(b);
 85         init();
 86         len=0;
 87         dfs();
 88         int ans=0;
 89         F(i,0,len-1)
 90         {
 91             if(s[i]==b[0])
 92             {
 93                 int p=i,fg=1;
 94                 F(j,0,lenb-1)if(p+j>=len||s[p+j]!=b[j]){fg=0;break;}
 95                 ans+=fg;
 96             }
 97         }
 98         printf("Case #%d: %d
",++cas,ans);
 99     }
100     return 0;
101 }

View Code