HDU 4125 2011福州现场赛E题 KMP+笛卡尔树

题意就不描述了。 主要说一下我的构造第一个串的过程
 
对给出的序列，比如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; 补充：软件开发 , C++ ,