題意就不描述了。 主要說一下我的構造第一個串的過程
對給出的序列，比如5 1 3 2 7 8 4 6
給每個數按輸入的順序對應一個編號
5 1 3 2 7 8 4 6
1 2 3 4 5 6 7 8
然後我們手動建這顆二叉搜索樹。觀察它，可以發現，每個結點的編號是滿足堆的性質。
也就是如果把這個編號當做每個結點的第二個關鍵字，這就是一個笛卡爾樹了
而建立笛卡爾樹的方法，如果以前做過POJ 2201的話，應該明白
首先按照第一個關鍵字排序
變為
第一關鍵字：1 2 3 4 5 6 7 8
第二關鍵字：2 4 3 7 1 8 5 6
然後我們找到那個第二關鍵字最小的結點，上面的例子的話就是第一關鍵字為5的結點
那麼我們首先經過的就是5.
然後看5的左孩子區間[1,4]，同理找最小，就是第一關鍵字為1的結點，此時要經過的就是1.然後發現1沒有左孩子
就進入右孩子[2,4]去找，找到第一關鍵字為3的點，那麼經過的就是3了，再找左孩子，經過了2，此時要退回去，又經過了3，然後找3的右孩子
經過了4，再退回去，又經過了3，再往回退，然後經過3的父親就是1，再退回去就經過了5，同理處理5的右孩子區間
就這樣，記錄經過的結點，串就構造出來了，然後KMP就行了
加完輸入優化後，這種方法用線段樹實現後的速度是1900ms+
當然，必須自己手寫堆棧 很蛋疼
當然此題可以用RMQ,但對於此題來講，RMQ有點卡空間 畢竟60W*log(60W) 不小，不過我寫了一遍後發現，竟然卡著空間過了，不過竟然比線段樹還慢，而且是我預處理log的情況下，真是神奇了。
下面代碼中的solve函數是我剛開始寫的遞歸，只不過爆棧了，改成手寫堆棧後，起到的作用也就是看起來容易明白
[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int inf = 111111111;
const int maxn = 1009;
const double esp = 1e-6;
const int N = 600009;
int n;
int st[N];
int now[N];
struct point
{
int a, b;
int id;
} pp[N];
struct node
{
int x, id;
} p[N];
int hash[N];
bool cmp(node x, node y)
{
return x.x < y.x;
}
int mi[4*N];
void build(int l, int r, int rt)
{
if(l == r)
{
mi[rt] = p[l].id;
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
mi[rt] = min(mi[lch(rt)], mi[rch(rt)]);
}
int query(int L, int R, int l, int r, int rt)
{
if(L <= l && R >= r) return mi[rt];
int ret = inf;
int m = (l + r) >> 1;
if(L <= m) ret = min(ret, query(L, R, lson));
if(R > m) ret = min(ret, query(L, R, rson));
return ret;
}
int len;
char s1[1888888], s2[7777];
int solve(int s, int t)
{
if(s > t) return 0;
int id = query(s, t, 1, n, 1);
int k = hash[id] % 2;
s1[len++] = k + '0';
if(solve(s, hash[id] - 1))
{
s1[len++] =k + '0';
}
if(solve(hash[id] + 1, t))
{
s1[len++] =k + '0';
}
return 1;
}
int next[11111];
void get_next(char *str)
{
int i = 0, j = -1, l = strlen (str);
next[0] = j;
while(i < l)
{
if(j == -1 || str[j] == str[i])
{
i++, j++;
next[i]= j;
}
else j = next[j];
}
}
int KMP(char *str1, char *str2)
{
int ans = 0;
int i = -1, j = -1, l1 = strlen(str1), l2 = strlen(str2);
while(i < l1)
{
if(j == -1 || str1[i] == str2[j])
{
i++, j++;
}
else j = next[j];
if(j == l2)
ans++;
}
return ans;
}
int in()
{
char ch;
int a = 0;
while((ch = getchar()) == ' ' || ch == '\n');
a += ch - '0';
while((ch = getchar()) != ' ' && ch != '\n')
{
a *= 10;
a += ch - '0';
}
return a;
}
int main()
{
int ca, tt=0;
scanf("%d", &ca);
while(ca--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) p[i].x = in(), p[i].id = i;
sort(p + 1 ,p + n + 1, cmp);
for(int i = 1; i <= n; i++) hash[p[i].id] = i;
build(1, n, 1);
len = 0;
//solve(1, n);
memset(now, 0, sizeof(now));
pp[0].a = 1;
pp[0].b = n;
pp[0].id = 1;
st[0] = 0;
int top = 0; //模擬棧st的坐標
len = 0; //串長
int cnt = 0; //棧裡存的結構體point的坐標
while(top>=0)
{
int num = st[top];
int a = pp[num].a;
int b = pp[num].b;
int id = pp[num].id;
char k = hash[id] % 2+'0';
//s1[len++] = k;
if(now[num]==0) //第一次
{
if(hash[id]>a) //有左孩子
{
pp[++cnt].a = a;
pp[cnt].b = hash[id]-1;
pp[cnt].id = query(a, hash[id]-1, 1, n, 1);
st[++top] = cnt;
s1[len++] = k;
}
now[num] = 1;
}
else if(now[num]==1) //第二次，處理完左孩子了
{
if(hash[id]<b) //有右孩子
{
pp[++cnt].a = hash[id]+1;
pp[cnt].b = b;
pp[cnt].id = query(hash[id]+1, b, 1, n, 1);
st[++top] = cnt;
s1[len++] = k;
}
now[num] = 2;
}
else if(now[num]==2) //第三次，兩個孩子都處理完了
{
s1[len++] = k;
--top;
}
}
s1[len] = '\0';
// cout<<s1<<endl;
scanf("%s", s2);
get_next(s2);
printf("Case #%d: %d\n", ++tt, KMP(s1, s2));
}
return 0;
}
