题意：
给出n个鼹鼠的编号（打乱顺序）排成一列，从第一个（非编号）鼹鼠开始挖洞，第2-n个鼹鼠在第一个鼹鼠挖洞的基础上挖洞，如果编号比之前的大就往右边走，否则往左边走，如果走不通（即左边或者右边没有洞），就自己挖洞，每只鼹鼠都会挖恰好一个洞。最终会形成一个二叉搜索树，得到这个树的dfs序列，把每一项都%2，最终得到一个01序列，与输入序列匹配，求输入序列在dfs序列中出现过多少次。
（貌似说的不太清楚，看不懂的话可以去读原题，很容易看懂，我这英语水平都读懂了。。。就是表达不出来）
思路：
笛卡尔树，鼹鼠的排列顺序满足小根堆的性质，编号满足二叉搜索树的顺序，就可以构造了~
最后kmp就可以了~
PS：
dfs和建树必须是非递归的，递归会暴栈（想想60万层）
rmq其实更好，只不过我没能开下。就写了线段树
笛卡尔树可以有O(n)的建树方法（除去排序），也非常简短，但是我不会。。。
吐槽：
这题递归三行改成非递归就成60行了。。。
G++ wa，c++在poj2900ms卡时过，在hdu 4125 1800ms过
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 7 #define N 750010 8 9 using namespace std; 10 11 struct PO 12 { 13 int a,w; 14 }po[N]; 15 16 struct TR 17 { 18 int u,l,r; 19 }tr[N]; 20 21 struct Q 22 { 23 int bh,l,r; 24 }q[N],wc; 25 26 struct QQ 27 { 28 int bh,pd; 29 }qq[N],we; 30 31 int s[N],p,pos,n,cnt,tt,next[N],b[N],len,mx[N*2]; 32 33 char str[N]; 34 35 inline bool cmp(const PO &a,const PO &b) 36 { 37 return a.a<b.a; 38 } 39 40 inline int jmin(int x,int y) 41 { 42 if(po[x].w<po[y].w) return x; 43 return y; 44 } 45 46 void build(int u,int l,int r) 47 { 48 if(l==r) {mx[u]=l;return;} 49 int mid=(l+r)>>1; 50 build(u<<1,l,mid); 51 build(u<<1|1,mid+1,r); 52 mx[u]=jmin(mx[u<<1],mx[u<<1|1]); 53 } 54 55 void query(int u,int L,int R,int l,int r) 56 { 57 if(L<=l&&r<=R) {pos=jmin(pos,mx[u]);return;} 58 int mid=(l+r)>>1; 59 if(L<=mid) query(u<<1,L,R,l,mid); 60 if(R>mid) query(u<<1|1,L,R,mid+1,r); 61 } 62 63 void read() 64 { 65 scanf("%d",&n); 66 for(int i=1;i<=n;i++) 67 { 68 scanf("%d",&po[i].a); 69 po[i].w=i; 70 } 71 po[0].w=0x7f7f7f7f; 72 sort(po+1,po+1+n,cmp); 73 build(1,1,n); 74 } 75 76 void create() 77 { 78 cnt=1; 79 int size=1; 80 q[size].bh=1; q[size].l=1; q[size].r=n; 81 while(size) 82 { 83 wc=q[size--]; 84 pos=0; 85 query(1,wc.l,wc.r,1,n); 86 tr[wc.bh].u=po[pos].a; 87 if(wc.l<=pos-1) 88 { 89 tr[wc.bh].l=++cnt; 90 q[++size].bh=cnt; 91 q[size].l=wc.l; 92 q[size].r=pos-1; 93 } 94 if(wc.r>=pos+1) 95 { 96 tr[wc.bh].r=++cnt; 97 q[++size].bh=cnt; 98 q[size].l=pos+1; 99 q[size].r=wc.r; 100 } 101 } 102 } 103 104 void dfs() 105 { 106 int size=1; 107 qq[size].bh=1; qq[size].pd=0; 108 while(size) 109 { 110 we=qq[size]; 111 if(we.pd==0) 112 { 113 s[++p]=tr[we.bh].u&1; 114 if(tr[we.bh].l!=-1) 115 { 116 qq[size].pd=1; 117 qq[++size].bh=tr[we.bh].l; 118 qq[size].pd=0; 119 continue; 120 } 121 if(tr[we.bh].r!=-1) 122 { 123 qq[size].pd=2; 124 qq[++size].bh=tr[we.bh].r; 125 qq[size].pd=0; 126 continue; 127 } 128 } 129 if(we.pd==1) 130 { 131 s[++p]=tr[we.bh].u&1; 132 if(tr[we.bh].r!=-1) 133 { 134 qq[size].pd=2; 135 qq[++size].bh=tr[we.bh].r; 136 qq[size].pd=0; 137 continue; 138 } 139 } 140 if(we.pd==2) s[++p]=tr[we.bh].u&1; 141 size--; 142 } 143 } 144 145 void getnext() 146 { 147 next[1]=0; 148 int i,j=0; 149 for(i=2;i<=len;i++) 150 { 151 while(j>0&&b[j+1]!=b[i]) j=next[j]; 152 if(b[j+1]==b[i]) j+=1; 153 next[i]=j; 154 } 155 } 156 157 int kmp() 158 { 159 int i,j=0,num=0; 160 for(i=1;i<=p;i++) 161 { 162 while(j>0&&b[j+1]!=s[i]) j=next[j]; 163 if(b[j+1]==s[i]) j+=1; 164 if(j==len) 165 { 166 num++; 167 j=next[j]; 168 } 169 } 170 return num; 171 } 172 173 void go() 174 { 175 memset(tr,-1,sizeof tr); 176 create(); 177 p=0; 178 dfs(); 179 scanf("%s",str+1); 180 len=strlen(str+1); 181 for(int i=1;i<=len;i++) b[i]=str[i]-'0'; 182 getnext(); 183 printf("%d\n",kmp()); 184 } 185 186 int main() 187 { 188 scanf("%d",&tt); 189 for(int i=1;i<=tt;i++) 190 { 191 read(); 192 printf("Case #%d: ",i); 193 go(); 194 } 195 //system("pause"); 196 return 0; 197 }